Universal Density Parameter Determines Graph Percolation Thresholds
Unfolding and refolding witness graphs lets the authors characterize critical activation density for every fixed graph H, including witnesses larger than the host graph.
Underlying Paper
The critical activation density in graph bootstrap percolation
In graph bootstrap percolation, edges of an Erd\H{o}s-R\'enyi random graph ${\mathcal G}_{n,p}$ are initially active, and activation spreads to other edges of $K_n$ via the combinatorics of a fixed graph $H$: an edge becomes active whenever it is the unique inactive edge in a copy of $H$. The process $H$-percolates if all edges of $K_n$ are eventually activated. While classical cases such as $H=K_3$ (connectivity) and $H=K_4$ (related to $2$-neighbor bootstrap percolation) have been studied extensively, general graphs $H$ can exhibit wildly different behaviors. In this work, we determine the critical $H$-percolation threshold $p_c(n,H)$ for every graph $H$, fully resolving a longstanding open question of Balogh, Bollob\'as, and Morris. The location of $p_c(n,H)$ is governed by a new, universal parameter $\rho(H)$, which measures the maximal efficiency of witness graphs that activate an edge. To achieve this, we introduce a novel framework based on the unfolding and refolding of witness graphs. While previous works were restricted to specific families of $H$, our approach provides a unified strategy for all $H$. Inspired by algebraic topology, we lift witness graphs to covering graphs and algorithmically embed folded versions into ${\mathcal G}_{n,p}$ via a sequence of extensions. Crucially, this allows us to incorporate highly efficient witness graphs of unbounded size, which are potentially far larger than ${\mathcal G}_{n,p}$ itself. Beyond resolving $p_c(n,H)$, our framework recovers and strengthens several existing bounds in the literature. Finally, we initiate the study of the universal density parameter $\rho(H)$ and pose central open questions regarding its computability and its exact correspondence with the sharpness of the $H$-percolation threshold.
Graph bootstrap percolation asks when a sparse set of initially active edges can trigger activation of all edges of . For a fixed graph , an inactive edge becomes active when it is the only missing edge of a copy of . The familiar case reduces to connectivity, but the general process is much less uniform: different graphs admit very different activation structures. This paper gives a general characterization of the critical activation density for every fixed , resolving the question posed by Balogh, Bollobás, and Morris.
Core Contribution
The paper identifies a universal graph parameter, , based on the density efficiency of witness graphs for activating one edge. A witness graph records a possible causal history: its initially active edges, through repeated completions of copies of , eventually activate a designated target edge. The authors’ central claim is that the critical -percolation threshold is governed by the most efficient such witnesses, rather than by a small fixed template or by a case-specific feature of .
That shift matters because an optimal witness need not have bounded size. Earlier arguments that search only among local or finite configurations can therefore miss the structures determining the threshold. The result is a classification principle for arbitrary fixed activation graphs, not another calculation for a restricted family.
Technical Approach
The technical obstacle is that a witness can be folded: repeated uses of may identify vertices or edges that were distinct in an unfolded activation history. The paper separates these two views. It lifts witness graphs to covering graphs, where the activation construction is unfolded into a more tractable object, then refolds and embeds the relevant structure into the random graph through a controlled sequence of extensions.
The ladder in Figure 1 is the basic visual example. Consecutive copies of share the structure needed for activation to propagate toward the final edge. It illustrates why a long witness can be efficient even though its causal construction is assembled from copies of one fixed graph.
The extension framework must also control collisions created by refolding. The accompanying combinatorial lemmas track vertices outside partial cores and charge them to edges with limited overlap. This supplies the sparsity needed to embed witness structures probabilistically while retaining the activation sequence. The construction is algorithmic in the sense that folded witnesses are placed through explicit extensions, rather than treated only as existential subgraphs.
The paper’s contribution is therefore not merely a new density definition. It provides the machinery required to turn a potentially unbounded witness optimization into a threshold argument in .
Results and Analysis
The main theorem determines the critical threshold location for every fixed graph in terms of . This includes the classical setting and the substantially more involved setting, while not assuming that the relevant witness has a size bounded independently of . The result also recovers and strengthens prior bounds that applied only to particular graph families.
The evidence is theoretical rather than experimental: the paper gives a general construction for the upper-threshold direction and witness-based obstructions for the lower-threshold direction. For this subject, that is the appropriate form of validation. The important advance is the match between the probabilistic threshold question and a single structural quantity defined through witnesses. If the proof’s density parameter is computable for a given , it turns a global dynamical process into a graph-structural calculation.
There is a practical qualification. The paper initiates, rather than completes, the study of . Its computability and the exact relation between and sharp threshold behavior remain open. Thus the theorem settles the general threshold-location problem, but it does not automatically provide an easy numerical threshold calculation for every input graph. The framework is strongest as a unifying theorem and a route to future graph-specific analyses.
Evidence Box
theoreticalKey Claims
- •A universal witness-density parameter ρ(H) governs critical H-percolation
- •Unfolding and refolding handle efficient witnesses of unbounded size
- •A unified threshold framework applies to every fixed graph H
Key Results
- •Critical threshold location characterized for every fixed H, including K3 and K4 cases
- •Witness constructions may exceed the n-vertex host graph in size
- •A K6 ladder of height 3 illustrates chained activation by consecutive copies of K6
Limitations & Caveats
- •Computability of ρ(H) remains open
- •Exact correspondence between ρ(H) and sharp-threshold behavior remains unresolved
- •The result is theoretical, with no finite-n empirical threshold study
- •Graph-specific threshold evaluation may still require difficult witness optimization
