Random Structures & Algorithms

Slightly subcritical hypercube percolation

Early View

We study bond percolation on the hypercube {0,1}m in the slightly subcritical regime where p = pc(1 − εm) and εm = o(1) but εm ≫ 2−m/3 and study the clusters of largest volume and diameter. We establish that with high probability the largest component has cardinality , that the maximal diameter of all clusters is , and that the maximal mixing time of all clusters is . These results hold in different levels of generality, and in particular, some of the estimates hold for various classes of graphs such as high‐dimensional tori, expanders of high degree and girth, products of complete graphs, and infinite lattices in high dimensions.

Related Topics

Related Publications

Related Content

Site Footer

Address:

This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on StatisticsViews.com are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and StatisticsViews.com express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.