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

This paper resolves long-standing open problems by proving that in the supercritical percolated hypercube, the giant component has a typical diameter of order $\Theta(d)$ and a mixing time of order $\Theta(d^2)$, achieved through novel large deviation estimates and structural insights into the component's stability and expansion.

The Gist

Imagine a giant, multi-dimensional cube made of light switches. This is the hypercube. In a standard $d$-dimensional version of this cube, every corner (vertex) is connected to $d$ other corners. If you have 10 dimensions, every corner has 10 neighbors. If you have 100 dimensions, every corner has 100 neighbors.

Now, imagine we play a game of "random destruction" on this cube. We flip a coin for every single connection (edge) between the corners. If it's heads, the connection stays; if it's tails, the connection is cut. We do this with a specific probability: $p = c/d$ (where $c$ is a number slightly larger than 1).

Because $c > 1$, we are in a "supercritical" state. This means that while many small islands of connected corners will form and float around, one massive "continent" of connected corners will also emerge. This is called the Giant Component.

This paper solves two long-standing mysteries about this Giant Continent:

1. How big is the island? (Specifically, what is the maximum distance you have to walk from one side to the other?)
2. How fast does a random walker get lost? (If you start walking randomly on this island, how long until you could be anywhere on it with equal probability?)

Here is the breakdown of their findings using simple analogies.

1. The Size of the Journey (Diameter)

The Question: If you are standing on one corner of this Giant Continent and want to walk to the furthest possible corner, how many steps will it take?

The Old Guess: For a long time, mathematicians weren't sure. They knew it wasn't infinite, but they didn't know if it was a short trip (like the size of the dimension $d$) or a very long, winding trip (like $d^3$ or $d^2$).

The New Discovery: The authors prove that the distance is proportional to $d$.

• The Analogy: Imagine the Giant Continent is a city. In a normal city, the distance across town might grow slowly as the city gets bigger. Here, the "city" is a hypercube. Even though it has billions of corners, the "traffic" is so efficient that the longest trip across the city is only about $d$ steps.
• Why it matters: It turns out the Giant Component is surprisingly compact. It's not a sprawling, messy maze; it's a tight, efficient network where you can get from point A to point B in a number of steps roughly equal to the number of dimensions.

2. The Random Walker's Confusion (Mixing Time)

The Question: Imagine a drunk person (a "random walker") starting at a specific corner. They take steps randomly, choosing any connected neighbor with equal chance. How long does it take until their location is completely unpredictable? In other words, how long until they are equally likely to be at any corner of the Giant Component?

The New Discovery: The time it takes for the walker to "forget" where they started is proportional to $d^2$.

• The Analogy: Think of the Giant Component as a giant, multi-layered ballroom. The drunk walker is spinning in circles.
  • The Diameter ($d$) is how long it takes to walk from one side of the ballroom to the other.
  • The Mixing Time ($d^2$) is how long it takes for the walker to have visited enough random spots that you can't guess where they are anymore.
• The Connection: The paper shows that because the "walk" is so efficient (the diameter is small), the "forgetting" process happens relatively quickly, specifically at a rate of $d$ squared. This matches what happens in other famous random graph models, confirming that the hypercube behaves in a very "standard" way despite its high-dimensional complexity.

How Did They Solve It? (The Secret Sauce)

The authors didn't just guess; they built a new toolkit to look inside the structure of this Giant Component.

1. The "Sprinkling" Technique: Imagine you have a dry sponge (the graph). You pour a little water on it (add a few random edges). This helps connect small islands into a big one. The authors used a clever version of this called "reverse sprinkling" or "thinning." They imagined taking a fully formed giant component and carefully removing edges to see if it would break apart. They proved that the Giant Component is stable—it's very hard to break it into small pieces just by removing a few edges.
2. The "Spread" Property: They showed that the Giant Component is "well-spread." It doesn't have huge, dense clumps that are hard to escape from. Instead, it expands evenly in all directions.
   • Analogy: If you drop a drop of ink into a sponge, it spreads out evenly. If the sponge had a "dead zone" where the ink got stuck, the spread would be slow. The authors proved this Giant Component has no "dead zones"; it spreads out efficiently.
3. The Stability Principle: They proved that if you have a large, connected group of vertices, it is extremely unlikely that this group will suddenly fall apart into tiny, disconnected pieces if you randomly remove some connections. This stability is what allows them to calculate the exact speed of the random walker.

Summary

Before this paper, mathematicians were arguing about whether the Giant Component in a high-dimensional cube was a compact city or a sprawling, confusing maze.

• Verdict on Distance: It is a compact city. The longest trip is about $d$ steps.
• Verdict on Random Walking: It is easy to get lost in. A random walker forgets their starting point in about $d^2$ steps.

The authors resolved a debate that had been going on since 1994 and 2003, proving that this complex, high-dimensional structure behaves with surprising simplicity and order.

Technical Summary

Technical Summary: Diameter and Mixing Time of the Giant Component in the Percolated Hypercube

Problem Statement
This paper investigates the structural and dynamic properties of the giant component, denoted $L_1$, in the bond-percolated $d$-dimensional binary hypercube $Q_d^p$. The study focuses on the regime where the edge retention probability is $p = c/d$ for a fixed constant $c > 1$ (the barely supercritical regime). Specifically, the authors address two long-standing open problems regarding the asymptotic order of:

1. The typical diameter of $L_1$.
2. The typical mixing time of a lazy simple random walk on $L_1$.

While the behavior of the giant component in the Erdős-Rényi random graph $G(n, c/n)$ is well-understood (with diameter $\Theta(\log n)$ and mixing time $\Theta((\log n)^2)$), the analogous behavior in the hypercube (where $n = 2^d$) remained unresolved. Previous work established polynomial upper bounds ($O(d^3)$ and $O(d^{11})$ respectively, later improved to $O(d(\log d)^2)$ and $O(d^2(\log d)^2)$), but it was unknown whether the tight dependencies were $\Theta(d)$ and $\Theta(d^2)$.

Methodology and Approach
The authors employ a multi-stage approach combining probabilistic methods, structural graph theory, and branching process approximations. The core of their methodology relies on a "sprinkling" argument (multi-stage exposure) combined with novel quantitative estimates on the expansion and stability of connected sets.

1. Large Deviation Estimates for $|V(L_1)|$:
   A central technical contribution is the derivation of tight large deviation bounds for the number of vertices in the giant component (Theorem 2). The authors establish that $|V(L_1)|$ concentrates sharply around its expectation $y(c)2^d$, where $y(c)$ is the survival probability of a Galton-Watson process with Poisson($c$) offspring.

   • Upper Tail: Proved using the bounded difference inequality, observing that an unusually large giant implies an unusually small number of vertices in small components.
   • Lower Tail: This is the more challenging component. The authors adapt the sprinkling technique by introducing a "reverse sprinkling" (thinning) perspective. They develop a stability principle (Theorem 5.6) which asserts that it is highly unlikely for a large connected set in the final graph $G_2$ to disintegrate into mostly small components in the intermediate graph $G_1$. This principle is coupled with a weighted decomposition and sparsification arguments to handle "type-1" (small components merging) and "type-2" (vertices attaching to large components) structures outside the giant.

2. Expansion Properties:
   To bound the mixing time, the authors utilize the connection between mixing time and graph conductance (via the theorem of Fountoulakis and Reed). They prove that large connected subsets of $L_1$ exhibit strong edge expansion (Theorem 3 and Theorem 6.3).

   • They show that for any connected set $S \subseteq V(L_1)$ of size up to half the giant, the number of edges leaving $S$ is at least $\Omega(|S|/d)$.
   • Crucially, they refine previous expansion results by providing tight quantitative estimates for sets of linear size, overcoming the difficulty that standard sprinkling arguments do not immediately yield tight bounds for the expansion of specific connected sets.

3. Diameter Analysis:
   For the diameter, the authors combine the expansion properties with a probabilistic construction of paths. They prove that for any pair of vertices, there is a non-negligible probability of a short path existing between them. By constructing many vertex-disjoint subcubes and using the expansion of the giant to ensure connectivity to these subcubes, they "bootstrap" a polynomial probability bound into a high-probability statement that the distance between any two vertices is $O(d)$.

Key Results
The paper resolves the open questions posed by Bollobás, Kohayakawa, and Łuczak (1994) and Benjamini and Mossel (2003) with the following main theorems:

• Theorem 1 (Diameter and Mixing Time): For $c > 1$ and $p = c/d$, with high probability (whp):

  • The diameter of $L_1$ is $\Theta_c(d)$.
  • The mixing time of the lazy simple random walk on $L_1$ is $\Theta_c(d^2)$.
  • These bounds are tight, matching the order of magnitude of the host hypercube's dimension and the square of the dimension, respectively.

• Theorem 2 (Large Deviations): The authors provide precise tail bounds for the size of the giant component. For $t \ge 2^d/d^{0.1}$:

  • $P(|V(L_1)| \ge y2^d + t) \le \exp\left(-\frac{\varepsilon t^2}{2^d (\log(2^d/t))^2}\right)$.
  • $P(|V(L_1)| \le y2^d - t) \le \exp\left(-\varepsilon t \log(2^d/t)/d\right)$.
    These bounds are shown to be tight for the lower tail in the specified range.

• Theorem 3 (Expansion): The giant component $L_1$ is an expander with conductance $\Omega(1/d)$. Specifically, for any connected subset $S \subseteq V(L_1)$ with $|S| \le |V(L_1)|/2$, the edge boundary is at least $\varepsilon |S|/d$. For sets of linear size, the expansion is even stronger, involving logarithmic factors.

Significance and Claims
The authors claim that this work resolves the quantitative behavior of the giant component in the percolated hypercube, confirming that it behaves similarly to the giant component in the Erdős-Rényi graph $G(n, c/n)$ when the dimension $d$ is treated as the logarithm of the number of vertices ($d = \log_2 |V|$).

The paper emphasizes that the resolution of these problems required overcoming the lack of a "homogeneous" host graph structure (unlike the complete graph in $G(n,p)$). The key innovation lies in the stability principle and the quantitative analysis of small perturbations (thinning) on the edges of the giant component. The authors note that their toolkit, particularly the stability principle and the tight expansion estimates, does not rely on the specific product structure of the hypercube. Consequently, they suggest these methods could be adapted to other sparse high-dimensional percolation models and settings where the conductance of large sets governs mixing behavior.

The paper concludes by identifying the barely-supercritical regime ($dp = 1 + o(1)$) as a natural next step for future research, where the mixing time behavior remains an intriguing open question.