What question did this study set out to answer?

To establish conditions for a regular graph to guarantee a phase transition in its random subgraph.

July 5, 2026Transactions of the American Mathematical Society0 citationsOpen Access

Components, large and small, are as they should be I: Supercritical percolation on regular graphs of growing degree

SDSahar DiskinTel Aviv University MKMichael KrivelevichTel Aviv University

Key Points

To establish conditions for a regular graph to guarantee a phase transition in its random subgraph.
Analyzed regular graphs of growing degree d, ensuring p·d≈1 for phase transition.
Studied specific well-known graph classes like complete graphs, hypercubes, and regular expanders.
Provided a unified proof for phase transitions in these graph types.
Identified conditions allowing phase transitions in complete graph K_n and hypercube Q^d.
Proved that d-regular expanders exhibit similar phase transition behaviors.
Conditions verified extend to general d-regular graphs.

Abstract

We provide sufficient conditions for a regular graph G G of growing degree d d, guaranteeing a phase transition in its random subgraph G p Gₚ similar to that of G (n, p) G (n, p) when p ⋅ d ≈ 1 p d 1. These conditions capture several well-studied graphs, such as (percolation on) the complete graph K n Kₙ, the binary hypercube Q d Qᵈ, d d -regular expanders, and random d d -regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that G G is a d d -regular graph on n n vertices, with d = ω (1) d= (1). Let ϵ > 0 >0 be a small constant, and let p = 1 + ϵ

Ask AI

Helpful

Bookmark

View Full Paper