Abstract
LetC k denote the graph with vertices (ɛ 1, ...,ɛ k ),ɛ i =0,1 and vertices adjacent if they differ in exactly one coordinate. We callC k thek-cube.
LetG=G k, p denote the random subgraph ofC k defined by letting
for alli, j ∈ C k and letting these probabilities be mutually independent.
We show that forp=λ/k, λ>1,G k, p almost surely contains a connected component of sizec2k,c=c(λ). It is also true that the second largest component is of sizeo(2k).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
M. Ajtai, J. Komlós andE. Szemerédi, The longest path in a random graph,Combinatorica 1 (1981) 1–12.
P. Erdős andJ. Spencer. Evolution of the n-cube,Computers and Math. with Applications 5 (1979) 33–40.
L. H. Harper, Optimal numberings and isoperimetric problems on graphs,Journal of Comb. Th. 1 (1966) 358–394.
T. E. Harris,The theory of branching processes, Springer (1963).
J. Komlós, M. Sulyok andE. Szemerédi. Underdogs in a random graph,submitted to Studia Sci. Math. Hung.