Large components in random induced subgraphs of n-cubes

Details Large components in random induced subgraphs of n-cubes Large components in random induced subgraphs of n-cubes

2007-04-22

arxiv.org/abs/0704.2868v3

Mathematics

Combinatorics

18 Pages

Scientific paper

In this paper we study random induced subgraphs of the binary $n$-cube, $Q_2^n$. This random graph is obtained by selecting each $Q_2^n$-vertex with independent probability $\lambda_n$. Using a novel construction of subcomponents we study the largest component for $\lambda_n=\frac{1+\chi_n}{n}$, where $\epsilon\ge \chi_n\ge n^{-{1/3}+ \delta}$, $\delta>0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that $\chi_n=\epsilon$, $| C_n^{(1)}|\sim \alpha(\epsilon) \frac{1+\chi_n}{n} 2^n$ and for $o(1)=\chi_n\ge n^{-{1/3}+\delta}$, $| C_n^{(1)}| \sim 2 \chi_n \frac{1+\chi_n}{n} 2^n$ holds. This improves the result of \cite{Bollobas:91} where constant $\chi_n=\chi$ is considered. In particular, in case of $\lambda_n=\frac{1+\epsilon} {n}$, our analysis implies that a.s. a unique giant component exists.

Affiliated with

Also associated with

No associations

Rating

Large components in random induced subgraphs of n-cubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Large components in random induced subgraphs of n-cubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large components in random induced subgraphs of n-cubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-466582