Diameter and mixing time of the giant component in the percolated hypercube

Basic Information

• Paper ID: 2510.13348
• Title: Diameter and mixing time of the giant component in the percolated hypercube
• Authors: Michael Anastos, Sahar Diskin, Lyuben Lichev, Maksim Zhukovskii
• Classification: math.PR (Probability Theory), math.CO (Combinatorics)
• Publication Date: October 15, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2510.13348

Abstract

This paper investigates bond percolation on the $d$-dimensional binary hypercube with parameter $p=c/d$ (fixed $c>1$). It is proven that the typical diameter of the giant connected component $L_1$ is of order $\Theta(d)$, and the typical mixing time of lazy random walks on it is of order $\Theta(d^2)$. This resolves long-standing open problems posed by Bollobás, Kohayakawa, and Łuczak in 1994, as well as by Benjamini and Mossel in 2003.

Key components of the methodology include novel tight large deviation estimates for the number of vertices in $L_1$, whose proof contains several novel elements: a structural description of the residual components outside the giant component after sprinkling, tight quantitative estimates of the giant component's expansion in the hypercube, and a stability principle excluding the decomposition of large connected sets under sparsification. This toolkit further allows us to obtain optimal bounds on the expansion properties of $L_1$.

Research Background and Motivation

Problem Background

1. Percolation Theory Foundation: The $d$-dimensional binary hypercube $Q_d$ is the graph with vertex set $\{0,1\}^d$, where two vertices are adjacent if and only if they differ in exactly one coordinate. The $p$-percolated hypercube $Q_d^p$ is obtained by independently retaining each edge with probability $p$.
2. Critical Phenomena: When $p=c/d$ with $c<1$, $Q_d^p$ typically contains only components of order $O(d)$; when $c>1$, there exists a linearly-sized giant connected component $L_1$ containing approximately $y \cdot 2^d$ vertices, where $y=y(c)$ is the survival probability of a Galton-Watson process with Poisson$(c)$ offspring distribution.
3. Unresolved Problems:
   • Diameter Problem (1994): Bollobás et al. asked whether the typical diameter of the giant component is polynomial in $d$, particularly whether it is $\Theta_c(d)$
   • Mixing Time Problem (2003): Benjamini and Mossel asked whether the asymptotic mixing time of lazy random walks is $\Theta_c(d^2)$

Research Motivation

1. Theoretical Importance: These problems concern fundamental geometric properties of high-dimensional random graphs and are crucial for understanding critical phenomena in percolation theory
2. Technical Challenges: Unlike the Erdős-Rényi random graph $G(n,c/n)$, the non-homogeneous structure of the hypercube makes direct methods difficult to apply
3. Existing Limitations:
   • Erde et al. (2021) proved diameter is $O(d^3)$
   • Diskin et al. (2024) improved to $O(d(\log d)^2)$
   • Mixing time bounds improved from $O(d^{11})$ to $O(d^2(\log d)^2)$

Core Contributions

1. Resolution of Long-Standing Open Problems:
   • Prove that the diameter of giant component $L_1$ is $\Theta(d)$
   • Prove that the mixing time of lazy random walks is $\Theta(d^2)$
2. Establishment of Tight Large Deviation Estimates: Provide precise upper and lower tail probability bounds for $|V(L_1)|$
3. Development of Novel Technical Tools:
   • Structural description after sprinkling
   • Quantitative estimates of giant component expansion
   • Stability principle under sparsification
4. Optimal Expansion Bounds: Prove expansion properties of connected sets in $L_1$

Methodology Details

Main Theorems

Theorem 1: Fix $c>1$ and let $p=c/d$. Then with high probability, the giant component $L_1$ satisfies:

• (a) The diameter of $L_1$ is $\Theta_c(d)$
• (b) The mixing time of lazy random walks on $L_1$ is $\Theta_c(d^2)$

Theorem 2 (Large Deviation Estimates): There exists a constant $\varepsilon=\varepsilon(c)>0$ such that for all $t \geq 2^d/d^{0.1}$:

$P(|V(L_1)| \geq y2^d + t) \leq \exp\left(-\frac{\varepsilon t^2}{2^d(\log(2^d/t))^2}\right)$

$P(|V(L_1)| \leq y2^d - t) \leq \exp\left(-\frac{\varepsilon t \log(2^d/t)}{d}\right)$

Technical Framework

1. Multi-Stage Sprinkling

Set $p_1 = (c-\delta)/d$ and $p_2$ such that $(1-p_1)(1-p_2) = 1-p$, define:

• $G_1 = Q_d^{p_1}$
• $G_2 = G_1 \cup Q_d^{p_2}$ (independently sampled)

Note that $G_2$ has the same distribution as $Q_d^p$.

2. Stability Principle (Theorem 5.6)

For sufficiently small $\eta=\eta(c)>0$, there exists $\varepsilon=\varepsilon(c,\delta,\eta)>0$ such that the probability that a vertex set $S$ simultaneously satisfies the following conditions is at most $\exp(-\varepsilon k)$:

• $|S|=k \in [d^{51}, n]$
• Each connected component of $G_2[S]$ has size at least $d^{10}$
• No edges between $S$ and $V(Q_d)\setminus S$ in $G_1$
• $|V(M_{[0,2)}^-) \cap S| \geq (1-\eta)k$

3. Good Expansion (Theorem 5.4)

For sufficiently small constants $\varepsilon,\gamma,\nu>0$ and $t \in [n^{1-\gamma}, n]$: $P(|V_{\text{bad}}(\varepsilon)| \geq t) \leq e^{-\nu t}$ where $V_{\text{bad}}(\varepsilon)$ is the set of "bad" vertices in the giant component with fewer than $\varepsilon d$ neighbors.

Technical Innovations

1. Structural Decomposition: Large components outside the giant component are classified into two types:
   • Type-1: Formed by merging many small $G_1$-components
   • Type-2: Aggregating with few large $G_1$-components
2. Weighted Decomposition and Sparsification: Use Theorem 3.11 to handle Type-1 vertices by isolating highly unlikely events to control probabilities
3. Quantitative Good Expansion: Prove that almost all vertices outside large $G_1$-components have many neighbors in the giant component

Experimental Setup

Theoretical Analysis Framework

This is purely theoretical work with no numerical experiments, establishing results through rigorous mathematical proofs.

Proof Strategy

1. Upper Tail Estimate (Section 4): Via bounded differences inequality, leveraging the observation that small component vertices are significantly below expectation
2. Lower Tail Estimate (Section 5): Using multi-stage sprinkling and stability principle
3. Mixing Time (Section 6): Via expansion properties and Fountoulakis-Reed theorem
4. Diameter (Section 7): Constructing specific path types and switching arguments

Experimental Results

Main Theoretical Results

Expansion Properties (Theorem 3)

There exists a constant $\varepsilon=\varepsilon(c)>0$ such that with high probability:

• For each $S \subseteq V(L_1)$ with $|S| \leq |V(L_1)|/2$ where $L_1[S]$ is connected, there are at least $\varepsilon|S|/d$ edges between $S$ and $L_1 \setminus S$
• For any constant $\delta \in (0,1)$, there exists $\eta=\eta(c,\delta)>0$ such that for any $S \subseteq V(L_1)$ with $|S| \in [\delta y2^d, (1-\delta)y2^d]$, there are at least $\eta|S|/d$ edges between $S$ and $L_1 \setminus S$

Key Lemma for Diameter (Lemma 7.1)

There exist constants $K_1=K_1(c)>0$ and $K_2=K_2(c)>0$ such that vertices $0$ and $1$ in $Q_d^p$ are connected by a path of length at most $K_1 d$ with probability at least $d^{-K_2}$.

Technical Achievements

1. Tightness: Lower tail estimates are tight (up to constant factors) for $t \in [2^d/d^{0.1}, y2^d]$
2. Optimality: Expansion bound $\Omega(1/d)$ is tight, as shown in literature 24, Claim 5.2
3. Universality: Techniques do not depend on the product structure of the hypercube and can be applied to other sparse high-dimensional percolation models

Related Work

Historical Development

1. Early Work:
   • Burtin (1977), Sapoženko (1967): $p=1/2$ is the sharp threshold for connectivity
   • Erdős-Spencer (1979): Only $O(d)$-sized components when $p<1/d$
   • Ajtai-Komlós-Szemerédi (1982): Giant component exists when $p>1/d$
2. Precise Results:
   • Bollobás-Kohayakawa-Łuczak (1992): Giant component size is $y2^d + o(2^d)$
   • van der Hofstad-Nachmias (2017): Comprehensive survey
3. Geometric Properties:
   • Erde-Kang-Krivelevich (2021): Diameter $O(d^3)$, mixing time $O(d^{11})$
   • Diskin-Erde-Kang-Krivelevich (2024): Improved to $O(d(\log d)^2)$ and $O(d^2(\log d)^2)$

Comparative Analysis

Compared to Erdős-Rényi random graph $G(n,c/n)$:

• Similarities: Both have linearly-sized giant components with other components of size $O(\log n)$ or $O(d)$
• Differences: The non-homogeneity of the hypercube makes direct techniques inapplicable
• This Paper's Contribution: First to achieve the same optimal orders as $G(n,c/n)$

Conclusions and Discussion

Main Conclusions

1. Complete Resolution of Open Problems: Prove that the diameter of the giant component in percolated hypercube is $\Theta(d)$ and mixing time is $\Theta(d^2)$
2. Establish Precise Theory: Provide tight large deviation estimates for giant component size
3. Develop General Techniques: Stability principle and expansion analysis applicable to other models

Limitations

1. Parameter Range: Results apply only to the supercritical regime $c>1$
2. Constant Dependence: Implicit constants depend on $c$ without explicit expressions
3. Dimension Requirements: Requires $d$ sufficiently large to ensure asymptotic behavior

Future Directions

1. Critical Regime: Study the nearly supercritical regime $dp = 1+o(1)$
2. Other Models: Extend techniques to other high-dimensional random graphs
3. Algorithmic Applications: Explore applications in algorithms and computer science

In-Depth Evaluation

Strengths

1. Theoretical Breakthrough: Resolves core open problems in the field spanning 25 years, marking a milestone
2. Technical Innovation:
   • Stability principle provides new tools for handling large connected sets
   • Multi-scale analysis techniques are elegant and general
   • Probability estimates achieve optimal orders
3. Rigorous Proofs:
   • Complete and detailed mathematical arguments
   • Sophisticated and correct technical handling
   • Tightness of results verified
4. Far-Reaching Impact:
   • Provides new perspective for percolation theory
   • Techniques likely to influence related fields
   • Resolves long-standing problems troubling experts

Weaknesses

1. Technical Complexity: Proofs are extremely complex, requiring specialized background for understanding and verification
2. Non-Constructive Constants: While existence is proven, constant values remain unclear
3. Limited Scope: Main results restricted to hypercube model

Impact

1. Academic Value:
   • Top-tier journal quality theoretical contribution
   • Will become important reference in the field
   • Likely to catalyze subsequent research
2. Methodological Contribution:
   • Stability principle has broad applicability
   • Provides new tools for handling high-dimensional random structures
   • Technical framework generalizable to other problems

Applicable Scenarios

1. Theoretical Research: Percolation theory, random graph theory, probability theory
2. Related Models: Other sparse high-dimensional random graphs, network science
3. Application Fields: Potential insights for statistical physics and computer science

References

The paper cites 54 important references, with key ones including:

1. Ajtai, M., Komlós, J., Szemerédi, E. (1982): Foundational work on giant component existence
2. Bollobás, B., Kohayakawa, Y., Łuczak, T. (1994): Original paper posing the diameter problem
3. Benjamini, I., Mossel, E. (2003): Proposing the mixing time conjecture
4. Erde, J., Kang, M., Krivelevich, M. (2021): Important earlier progress
5. van der Hofstad, R., Nachmias, A. (2017): Authoritative survey of the field

Overall Assessment: This is an outstanding theoretical paper resolving important open problems with significant technical innovations and rigorous complete proofs, representing a major advancement in percolation theory. Despite high technical complexity, its theoretical value and methodological contributions make it an important milestone in the field.