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