## The Evolution of Random Subgraphs of the Cube

### Authors:

- B. Bollobás,
- Y. Kohayakawa,
- Tomasz Łuczak

### Abstract

be a random Q^{n}”‐process, that is let Q_{0} be the empty spanning subgraph of the cube Q^{n} and, for 1 ⩽ t ⩽ M = nN/2 = n2^{n−1}, let the graph Q_{t} be obtained from Q_{t−1} by the random addition of an edge of Q_{n} not present in Q_{t−1}. When t is about N/2, a typical Q_{t} undergoes a certain “phase transition'': the component structure changes in a sudden and surprising way. Let t = (1 + ϵ) N/2 where ϵ is independent of n. Then all the components of a typical Q_{t} have o(N) vertices if ϵ < 0, while if ϵ > 0 then, as proved by Ajtai, Komlós, and Szemerédi, a typical Q_{t} has a “giant” component with at least α(ϵ)N vertices, where α(ϵ) > 0. In this note we give essentially best possible results concerning the emergence of this giant component close to the time of phase transition. Our results imply that if η > 0 is fixed and t ⩽ (1 − n^{−η}) N/2, then all components of a typical Q_{t} have at most n^{β(η)} vertices, where β(η) > 0. More importantly, if 60(log n)^{3}/n ⩽ ϵ = ϵn = o(1), then the largest component of a typical Q_{t} has about 2ϵN vertices, while the second largest component has order O(nϵ^{−2}). Loosely put, the evolution of a typical Q^{n} process is such that shortly after time N/2 the appearance of each new edge results in the giant component acquiring 4 new vertices. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company

- Record ID
- UAMc231cd257da54db59b7bffc06fc4ec86
- Author
- Journal series
- Random Structures & Algorithms, ISSN 1042-9832
- Issue year
- 1992
- Vol
- 3
- Pages
- 55-90
- ASJC Classification
- ; ; ;
- DOI
- DOI:10.1002/rsa.3240030106 opening in a new tab
- Language
- en English
- Score (nominal)
- 35
- Score source
- journalList
- Publication indicators
- = 39.000; : 1999 = 1.557; : 2006 = 1.167 (2) - 2007=1.115 (5)

- Uniform Resource Identifier
- https://researchportal.amu.edu.pl/info/article/UAMc231cd257da54db59b7bffc06fc4ec86/

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perishopening in a new tab system.

Back