Large components in random induced subgraphs of n-cubes

Simple item page
dc.creatorReidys, Christian M.
dc.date2007-04-22
dc.date2008-03-07
dc.date.accessioned2026-07-07T09:25:02Z
dc.date.available2026-07-07T09:25:02Z
dc.descriptionIn 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 $λ_n$. Using a novel construction of subcomponents we study the largest component for $λ_n=\frac{1+χ_n}{n}$, where $ε\ge χ_n\ge n^{-{1/3}+ δ}$, $δ>0$. We prove that there exists a.s. a unique largest component $C_n^{(1)}$. We furthermore show that $χ_n=ε$, $| C_n^{(1)}|\sim α(ε) \frac{1+χ_n}{n} 2^n$ and for $o(1)=χ_n\ge n^{-{1/3}+δ}$, $| C_n^{(1)}| \sim 2 χ_n \frac{1+χ_n}{n} 2^n$ holds. This improves the result of \cite{Bollobas:91} where constant $χ_n=χ$ is considered. In particular, in case of $λ_n=\frac{1+ε} {n}$, our analysis implies that a.s. a unique giant component exists.
dc.description18 Pages
dc.identifierhttps://arxiv.org/abs/0704.2868
dc.identifierhttp://arxiv.org/abs/0704.2868
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/156276
dc.subjectCombinatorics
dc.subjectProbability
dc.subject46N30
dc.titleLarge components in random induced subgraphs of n-cubes
dc.typetext

Files

Collections

arXiv