## On the diameter and radius of randon subgraphs of the cube

### Authors:

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

### Abstract

The n‐dimensional cube Q^{n} is the graph whose vertices are the subsets of {1,…n}, with two vertices adjacent if and only if their symmetric difference is a singleton. Clearly Q^{n} has diameter and radious n. Write M = n2^{n‐1} = e(Q^{n}) for the size of Q^{n}. Let Q = (Q_{t})_{o}^{M} be a random Q^{n}‐process. Thus Q^{t} is a spanning subgraph of Q^{n} of size t, and Q_{t} is obtained from Q_{t–1} by the random addition of an edge of Q^{n} not in Q_{t–1}, Let t^{(k)} = τ(Q;δ⩾k) be the hitting time of the property of having minimal degree at least k. We show that the diameter d_{t} = diam (Q_{t}) of Q_{t} in almost every Q̃ behaves as follows: d_{t} starts infinite and is first finite at time t^{1}, it equals n + 1 for t^{1} ⩽ t^{2} and d_{t}, = n for t ⩾ t^{2}. We also show that the radius of Q_{t}, is first finite for t = t^{1}, when it assumes the value n. These results are deduced from detailed theorems concerning the diameter and radius of the almost surely unique largest component of Q_{t}, for t = Ω(M). © 1994 John Wiley & Sons, Inc. Copyright © 1994 Wiley Periodicals, Inc., A Wiley Company

- Record ID
- UAM432dbbde94214744b46d5de2d06aecdc
- Author
- Journal series
- Random Structures & Algorithms, ISSN 1042-9832
- Issue year
- 1994
- Vol
- 5
- No
- 5
- Pages
- 627-648
- ASJC Classification
- ; ; ;
- DOI
- DOI:10.1002/rsa.3240050503 Opening in a new tab
- URL
- https://onlinelibrary.wiley.com/doi/10.1002/rsa.3240050503 Opening in a new tab
- Language
- (en) English
- Score (nominal)
- 0
- Score source
- journalList
- Publication indicators
- = 6; = 5; = 16; : 1999 = 1.557; : 2006 (2 years) = 1.167 - 2007 (5 years) =1.115
- Citation count
- 16

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

- URN
`urn:amu-prod:UAM432dbbde94214744b46d5de2d06aecdc`

* 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.