Critical threshold for regular graphs

Ishaan Bhadoo

REVIEW 3 major objections 4 minor 10 references

Critical threshold for regular graphs

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quasi-transitive d-regular graph attains the minimum bond-percolation threshold 1/(d-1) if and only if it is a tree.

desk verdict True but known central theorem; the counterexample is the real contribution, and the covering proof has a fixable gap. read the letter →

arxiv 2412.00635 v2 pith:W3D5K7GA submitted 2024-12-01 math.PR math.CO

Ishaan Bhadoo This is my paper · ORCID

classification math.PRmath.CO MSC 60K3505C0505C25

keywords percolationthresholdd-regulargraphsquasi-transitiveuniversalcoverbranchingnumbersubperiodictreesconnectiveconstantstrictmonotonicity

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Bernoulli bond percolation keeps each edge of an infinite graph with probability $p$; the critical threshold $p_c(G)$ is the value of $p$ at which an infinite connected component first appears. This paper asks which $d$-regular graphs achieve the smallest possible threshold $1/(d-1)$, the value already known for the $d$-regular tree. The main theorem says that among quasi-transitive $d$-regular graphs — graphs whose automorphism group has only finitely many vertex orbits — the tree is the only minimizer: any such graph containing a cycle has $p_c(G) > 1/(d-1)$. The paper also constructs, for every $d \ge 3$, a $d$-regular graph with cycles for which $p_c(G) = 1/(d-1)$, showing the quasi-transitive assumption is necessary. The importance is that it identifies exactly when the universal lower bound is tight in a broad symmetry class.

What carries the argument

The central object is the universal cover of a $d$-regular graph $H$: the graph $X$ whose vertices are non-backtracking paths $\langle x_0,x_1,\dots,x_n\rangle$ in $H$ starting at a fixed basepoint, with two paths adjacent when one extends the other by one edge. For $d$-regular $H$, this $X$ is the $d$-regular tree $T_d$, and the projection $\pi$ sending a path to its last vertex is a strong covering map, meaning it is 1-Lipschitz and has the strong lifting property. The argument's second ingredient is uniform non-triviality of the fibres: quasi-transitivity gives a uniform bound $K$ such that every vertex of $H$ lies on a closed non-backtracking walk of length at most $K$, so every path in $X$ has a distinct nearby path projecting to the same vertex. These two properties make the paper's Theorem 7 applicable, which states that a strong covering map with uniformly non-trivial fibres from $G$ to $H$ forces $p_c(G) < p_c(H)$ whenever $p_c(G) < 1$, and that yields the strict inequality.

What would settle it

One concrete check: take a quasi-transitive $d$-regular graph with cycles, such as a finite-sheeted quotient of the $d$-regular tree, and determine whether every vertex lies on a closed non-backtracking walk of uniformly bounded length; if some vertex has no such walk below a growing bound, the proof's uniform-fibre step fails. A more decisive test is to compute $p_c$ for such a quotient and see whether it is strictly above $1/(d-1)$ as Theorem 2 predicts.

Watch

Extended reading notes

Core claim

The paper proves Theorem 2: for a quasi-transitive $d$-regular graph $G$, one has $p_c(G) \ge 1/(d-1)$, with equality if and only if $G$ is a tree. Since the inequality is classical, the new content is the strict inequality $p_c(G) > 1/(d-1)$ whenever $G$ contains a cycle. The proof realizes $G$ as the target of a strong covering map from the $d$-regular tree $T_d$: vertices of the cover are non-backtracking paths in $G$, and the map sends a path to its terminal vertex. Quasi-transitivity gives this map uniformly non-trivial fibres, and the strict monotonicity theorem for critical thresholds under strong covering maps (Theorem 7 of the paper) then forces $p_c(T_d) < p_c(G)$. The counterexample section builds $G$ from a subperiodic tree — one whose rooted subtrees all embed near the root within a uniform distance — with two degree-$(d-1)$ vertices next to the root, then adds one edge between them; using the fact that for this subperiodic tree the branching number equals its exponential growth rate $d-1$, the paper shows $p_c(G) = 1/(d-1)$ even though $G$ has cycles, and Theorem 2 implies such a $G$ cannot be quasi-transitive. The closing remarks note that the same fibre argument works for any $d$-regular graph with bounded local girth, so for those graphs with cycles the threshold is also strictly above $1/(d-1)$.

Load-bearing premise

The proof depends on the assertion that quasi-transitivity (finitely many vertex types up to symmetry) supplies one fixed bound $K$ such that every vertex of the graph lies on a closed walk of length at most $K$; if that uniform bound fails, the covering map may lack uniformly non-trivial fibres and the strict monotonicity theorem would not apply.

Editorial extensions

If this is right

In the class of quasi-transitive $d$-regular graphs, the $d$-regular tree is the unique graph with threshold $1/(d-1)$; every other graph in the class has a strictly larger critical probability.
For every $d \ge 3$, there is a $d$-regular graph with cycles whose threshold is still $1/(d-1)$, and Theorem 2 shows any such example must fail quasi-transitivity.
The same covering argument gives $p_c(G) > 1/(d-1)$ for every $d$-regular graph with bounded local girth and at least one cycle, extending the main result beyond the quasi-transitive setting.
Since $p_c(G) \ge 1/\mu(G)$, the strict inequality for quasi-transitive non-tree graphs is compatible with the known bound $\mu(G) < d-1$ for their connective constants, so the two results are consistent.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Beyond the paper, the proof identifies a sufficient condition — uniformly non-trivial fibres for the universal-cover projection — so one could look for other graph classes with that property and expect the same strict inequality.
A natural quantitative extension would be to measure how close $p_c$ gets to $1/(d-1)$ in families of graphs with cycles growing farther from a root, using the one-edge construction as the limiting case.
The final remark on $p_u$ points to an open question: whether any quasi-transitive graph with cycles can have a uniqueness threshold as small as the tree's; the covering argument used for $p_c$ does not transfer directly because $p_u(T_d)=1$.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things to know. The main theorem—quasi-transitive d-regular graphs have p_c = 1/(d−1) only if they are trees—is true but not new. The paper says so itself in Section 1.1: Theorem 2 follows from Lemma 3 (standard first-moment bound) plus Grimmett–Li's Theorem 4.2 on connective constants. What is genuinely new is the Section 2 counterexample: for every d ≥ 3 a d-regular graph with cycles and p_c = 1/(d−1), showing the quasi-transitive assumption in Theorem 2 is necessary. That example is correct; the branching-number calculation is clean and the subperiodicity argument works. The bounded-local-girth remark in Section 4 is also a true and useful observation.

The soft spot is Proposition 8, the covering-map route to Theorem 2. In the 'uniformly non-trivial fibres' paragraph, the paper asserts that quasi-transitivity gives a K such that every vertex lies on a closed non-backtracking walk of length at most K. This is true but it needs the finite-quotient argument, and the paper does not supply it. The construction of y in the case x_{n−1}=x_{n+1} is also off: the proposed path is non-backtracking only if x_{n+2} ≠ x_{n−2}, which the cycle condition does not guarantee. So as written, that proof does not go through. It is repairable—use a simple cycle and an orientation that avoids the previous step, or get the uniform bound from the finite quotient—but it needs work. The main result is not in danger, because Section 1.1 already derives it from Grimmett–Li. The sentence in Section 2.3 saying the counterexample is not quasi-transitive 'follows from Theorem 2' is not circular, but the wording invites confusion.

Who gets value: percolation folks who want a sharpness example, and anyone teaching the enhancement technique. It deserves a serious referee; the counterexample is publishable on its own, and the covering proof can be fixed. If you referee it, ask for the Proposition 8 fix or for Section 3 to be labeled a sketch, and make the GL derivation the official proof of Theorem 2.

Referee Report

3 major / 4 minor

Summary. The paper studies Bernoulli bond percolation on infinite, locally finite, connected d-regular graphs and addresses the question of when the critical threshold attains the universal lower bound 1/(d-1). The main theorem (Theorem 2) states that for a quasi-transitive d-regular graph G, pc(G) >= 1/(d-1) and equality holds if and only if G is a tree. The paper gives two proofs of this statement: first, in Section 1.1, by combining the general lower bound pc >= 1/mu with the theorem of Grimmett and Li [GL15] that the connective constant mu of a d-regular quasi-transitive graph with cycles is strictly less than d-1; second, in Section 3, by constructing a strong covering map from the d-regular tree T_d to any quasi-transitive d-regular graph with cycles and invoking the Martineau-Severo strict monotonicity theorem. The paper also constructs, for each d >= 3, a d-regular graph with cycles for which pc = 1/(d-1), demonstrating that the quasi-transitive assumption is necessary.

Significance. If correct, the characterization of equality in the lower bound pc >= 1/(d-1) is a natural and useful result, and the counterexamples are explicit and verifiable. The paper correctly identifies that the main theorem is already obtainable from existing results: Lemma 3 together with [GL15, Thm 4.2] yields Theorem 2 directly. The genuinely new potential contribution is the covering-map proof of Theorem 2 and the family of non-quasi-transitive counterexamples. The counterexample construction in Section 2 is sound and clearly written. However, the covering-map proof in Section 3 is currently incomplete: the proof of Proposition 8 contains an unjustified quasi-transitivity assertion and a flaw in the construction of the non-backtracking path. Since the main theorem is independently supported by Section 1.1, the flaw does not invalidate the paper's central claim, but it does undermine the advertised independent proof and the extension to bounded local girth in Section 4.

major comments (3)

[Section 3.1, Proposition 8, 'Uniformly non-trivial fibres'] The sentence 'By quasi-transitivity, we can find a K (independent of xn) such that there is a cycle C=... of length m <= K' is not justified as written. Quasi-transitivity gives finitely many automorphism orbits, but one must first argue that every vertex of a quasi-transitive d-regular graph with cycles lies on a closed non-backtracking walk of uniformly bounded length. This is true (e.g., by passing to the finite quotient and taking a cycle in the quotient that lifts to a closed walk through the given vertex), but the argument is omitted. Since this uniform bound is exactly what is needed to make the fibers uniformly non-trivial, the proof of Proposition 8 is incomplete without it.
[Section 3.1, Proposition 8, construction of y when x_{n-1}=x_{n+1}] In the case x_{n-1}=x_{n+1}, the proposed path y = <x0,...,x_{n-1}, x_{n+2},...,x_n> is not necessarily non-backtracking. Non-backtracking of the cycle C gives x_{n+2} != x_n, but the validity of the step from x_{n-1} to x_{n+2} requires x_{n+2} != x_{n-2}; this is not guaranteed. Thus the proof that the fibre point y exists fails as written. The argument can be repaired, for instance by choosing a simple cycle through pi(x) and using an orientation whose first edge avoids x_{n-1}, or by deriving the uniform bound from the finite quotient and then picking an appropriate closed walk, but the current text does not provide such a construction.
[Section 4, concluding remarks on bounded local girth] The claim that the same proof extends to graphs with bounded local girth depends on the proof of Proposition 8. Even if the uniform cycle-length bound is replaced by bounded local girth, the flawed y-construction in the x_{n-1}=x_{n+1} case must be fixed before the extension is valid. As written, Section 4 overstates the confidence in the extension.

minor comments (4)

[Section 2.2, heading and notation] The heading 'Superiodic trees' appears to be a typo for 'Subperiodic trees'. In addition, the definitions of the upper and lower exponential growth rates both use the symbol grT, which is ambiguous; using distinct symbols such as \overline{gr} and \underline{gr} would improve clarity.
[Section 1.1, footnote 2] The footnote reads 'This also showspc(G) >= ...' with a missing space between 'shows' and 'pc'.
[Section 2.3, paragraph on subperiodicity] The phrase 'for all x such that dT(x,O) >= 2, we have Tx is exactly TA' is slightly imprecise: the subtree Tx depends on whether the path from the root to x passes through X or Y, and the isomorphism may require choosing A depending on x. The intended meaning is clear, but the wording could be made more precise.
[Section 2.3, final sentence] The statement 'the fact that G is not quasi-transitive follows from Theorem 2' is logically acceptable because Theorem 2 is already proved in Section 1.1 via [GL15]. However, if the authors intend Section 3 to be the primary proof, this sentence would be circular; clarifying that Section 1.1 establishes Theorem 2 independently would remove any ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorem rests on external results (Grimmett–Li, Martineau–Severo) and no fitted input or self-citation chain is load-bearing.

full rationale

The paper's central result, Theorem 2, is supported by at least two independent routes. Section 1.1 derives it from Lemma 3, a standard first-moment bound, together with Grimmett and Li's external combinatorial theorem [GL15, Thm 4.2] giving mu(G) < d-1 for quasi-transitive d-regular graphs with cycles. Section 3 gives a separate covering-map proof using the strict monotonicity theorem of Martineau and Severo [MS19]. Neither [GL15] nor [MS19] is authored by the present author, and neither result is shown to be equivalent to the theorem being proved. There are no fitted parameters, no data-fitting steps, and no quantity is renamed as a prediction. The sentence in Section 2.3, 'the fact that G is not quasi-transitive follows from Theorem 2,' is a forward consequence rather than a load-bearing premise: the counterexample's value pc(G)=1/(d-1) is established independently via the branching number of subperiodic trees and the first-moment bound, and the theorem is not used to prove that value. The proof of Proposition 8 contains an unproved assertion, 'By quasi-transitivity, we can find a K ... such that there is a cycle ... of length m <= K,' which is a correctness gap in the covering-map argument rather than a circularity: the assertion does not assume Theorem 2 or define the conclusion as an input, and it is separately repairable from the finite quotient of a quasi-transitive graph. Therefore no step in the derivation reduces to its own input, and the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted constants and no new postulated entities. It relies on standard percolation facts and external theorems from [LP17], [Lyo90], [GL15], and [MS19]. The only new unproved ingredient is the uniform closed-walk assertion in Proposition 8, which is needed to establish uniformly non-trivial fibers.

assumptions (5)

standard math First-moment bound: pc(G) >= 1/(d-1) for graphs of maximum degree d (Lemma 3 via self-avoiding walks).
Used for the lower bound in the counterexample and for the base inequality in Theorem 2; cited to [LP17].
domain assumption Lyons theorem: for a locally finite infinite tree T, pc(T)=1/br(T).
Used to compute pc(T)=1/(d-1) for the modified tree in Section 2; cited to [Lyo90] and [LP17].
domain assumption For subperiodic trees, br(T)=gr(T) (Theorem 6).
Used to identify br(T)=d-1 for the counterexample tree; cited to [LP17].
domain assumption Martineau-Severo strict monotonicity: a strong covering map with uniformly non-trivial fibers and pc(G)<1 implies pc(G)<pc(H).
The engine of the proof of Theorem 2; quoted as Theorem 7 from [MS19].
ad hoc to paper Every vertex of a quasi-transitive d-regular graph with cycles lies on a closed non-backtracking walk of length at most a uniform K.
Asserted without proof in Proposition 8; it is true via the finite quotient, but the paper provides no derivation, which is the main gap in the covering proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Critical threshold for regular graphs." pith.science (2026). https://pith.science/paper/W3D5K7GA

@misc{pith2026241200635,
  author       = {Pith},
  title        = {Pith review of: Critical threshold for regular graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W3D5K7GA}},
  note         = {Machine review of arXiv:2412.00635}
}

abstract

In this article, we study the critical percolation threshold $p_c$ for $d$-regular graphs. It is well-known that $p_c \geq \frac{1}{d-1}$ for such graphs, with equality holding for the $d$-regular tree. We prove that among all quasi-transitive $d$-regular graphs, the equality $p_c(G) = \frac{1}{d-1}$ holds if and only if $G$ is a tree. Furthermore, we provide counterexamples that illustrate the necessity of the quasi-transitive assumption.

Figures

Figures reproduced from arXiv: 2412.00635 by the authors.

**Figure 1.** On removing the edge e we get a sub-periodic tree T with grT = brT = d − 1 2.3 Non quasi-transitive counter-examples We are now ready to give our counterexamples. Let T be a tree with root O such that every vertex in T has degree d, except two vertices X, Y that are adjacent to the root having degree d − 1. Hence, T = (V, E) is the graph formed by all black edges shown in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 8 canonical work pages

[1]

Strict monotonicity for critical points in percolation and ferromagnetic models

Michael Aizenman and Geoffrey Grimmett. Strict monotonicity for critical points in percolation and ferromagnetic models. Journal of Statistical Physics , 63:817--835, 1991

work page 1991
[2]

Essential enhancements revisited

Paul Balister, B \'e la Bollob \'a s, and Oliver Riordan. Essential enhancements revisited. arXiv preprint arXiv:1402.0834 , 2014

arXiv 2014
[3]

Percolation beyond Z ^d , many questions and a few answers

Itai Benjamini and Oded Schramm. Percolation beyond Z ^d , many questions and a few answers. 1996

work page 1996
[4]

Bounds on connective constants of regular graphs

Geoffrey R Grimmett and Zhongyang Li. Bounds on connective constants of regular graphs. Combinatorica , 35(3):279--294, 2015

work page 2015
[5]

Probability on trees and networks , volume 42

Russell Lyons and Yuval Peres. Probability on trees and networks , volume 42. Cambridge University Press, 2017

2017
[6]

Random walks and percolation on trees

Russell Lyons. Random walks and percolation on trees. The Annals of Probability , 18(3):931--958, 1990

work page 1990
[7]

Random walks, capacity and percolation on trees

Russell Lyons. Random walks, capacity and percolation on trees. The Annals of Probability , pages 2043--2088, 1992

work page 1992
[8]

Strict monotonicity of percolation thresholds under covering maps

S \'e bastien Martineau and Franco Severo. Strict monotonicity of percolation thresholds under covering maps. 2019

work page 2019

Show all 10 references

[9]

Modern discrete probability: An essential toolkit

Sebastien Roch. Modern discrete probability: An essential toolkit . Cambridge University Press, 2024

2024
[10]

Interpolation schemes in percolation theory

Franco Severo. Interpolation schemes in percolation theory . PhD thesis, Universit \'e Paris-Saclay; Universit \'e de Gen \`e ve, 2020

2020

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Strict monotonicity for critical points in percolation and ferromagnetic models

Michael Aizenman and Geoffrey Grimmett. Strict monotonicity for critical points in percolation and ferromagnetic models. Journal of Statistical Physics , 63:817--835, 1991

work page 1991

[2] [2]

Essential enhancements revisited

Paul Balister, B \'e la Bollob \'a s, and Oliver Riordan. Essential enhancements revisited. arXiv preprint arXiv:1402.0834 , 2014

arXiv 2014

[3] [3]

Percolation beyond Z ^d , many questions and a few answers

Itai Benjamini and Oded Schramm. Percolation beyond Z ^d , many questions and a few answers. 1996

work page 1996

[4] [4]

Bounds on connective constants of regular graphs

Geoffrey R Grimmett and Zhongyang Li. Bounds on connective constants of regular graphs. Combinatorica , 35(3):279--294, 2015

work page 2015

[5] [5]

Probability on trees and networks , volume 42

Russell Lyons and Yuval Peres. Probability on trees and networks , volume 42. Cambridge University Press, 2017

2017

[6] [6]

Random walks and percolation on trees

Russell Lyons. Random walks and percolation on trees. The Annals of Probability , 18(3):931--958, 1990

work page 1990

[7] [7]

Random walks, capacity and percolation on trees

Russell Lyons. Random walks, capacity and percolation on trees. The Annals of Probability , pages 2043--2088, 1992

work page 1992

[8] [8]

Strict monotonicity of percolation thresholds under covering maps

S \'e bastien Martineau and Franco Severo. Strict monotonicity of percolation thresholds under covering maps. 2019

work page 2019