The diameter of a random subgraph of the hypercube

In this paper we present an estimation for the diameter of random subgraph of a hypercube. In the article by A. V. Kostochka (Random Struct Algorithms 4 (1993) 215–229) the authors obtained lower and upper bound for the diameter. According to their work, the inequalities n + m_p ≤ D(G_n) ≤ n + m_p + 8 almost surely hold as n → ∞, where n is dimension of the hypercube and m_p depends only on sampling probabilities. It is not clear from their work, whether the values of the diameter are really distributed on these 9 values, or whether the inequality can be sharpened. In this paper we introduce several new ideas, using which we are able to obtain an exact result: D(G_n) = n + m_p (almost surely). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012