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ⁿ 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ⁿ has diameter and radious n. Write M = n2^n‐1 = e(Qⁿ) for the size of Qⁿ. Let Q = (Q_t)_o^M be a random Qⁿ‐process. Thus Q^t is a spanning subgraph of Qⁿ of size t, and Q_t is obtained from Q_t–1 by the random addition of an edge of Qⁿ 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¹, it equals n + 1 for t¹ ⩽ t² and d_t, = n for t ⩾ t². We also show that the radius of Q_t, is first finite for t = t¹, 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