{"id":"6ffc1e32-c902-474d-9a5a-e3c9fe8752c0","arxiv_id":"2412.00635","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For quasi-transitive d-regular graphs, only trees have the minimal percolation threshold 1/(d-1), but without quasi-transitivity cyclic d-regular graphs with this threshold exist.","lead":"This paper asks when a regular graph has the same percolation threshold as a regular tree. It shows that among quasi-transitive regular graphs only trees attain the minimal threshold, and it constructs non-symmetric cyclic graphs that also attain it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 8's non-trivial-fibre proof has an unproved uniform-cycle bound and an unverified shortcut construction, but the main theorem is independently supported by Grimmett–Li.","rationale":"The central claim of the paper, Theorem 2, is true and is in fact already established by the route the paper itself points out in Section 1.1: Lemma 3 gives pc(G) ≥ 1/µ(G), and the Grimmett–Li theorem [GL15, Thm 4.2] gives µ(G) < d−1 for every d-regular quasi-transitive graph with cycles, so pc(G) > 1/(d−1); trees are the only equality cases. Thus the main theorem does not depend on the covering-map proof. The genuine weakness is in the independent proof of Proposition 8: the uniform bound K is asserted rather than derived from quasi-transitivity, and the construction of y can fail to be non-backtracking unless an additional condition such as x_{n+2} ≠ x_{n-2} is verified. The reader identified this same paragraph as the weakest assumption. These are fixable presentation gaps, not fatal errors, because the theorem has independent support and the gaps have natural repairs. The counterexample in Section 2 is correct in its threshold calculation, though the claim that G is not quasi-transitive is justified by an appeal to Theorem 2 rather than directly; this is circular in exposition but easily repaired. Therefore the conditional verdict is appropriate, and the reader's verdict should remain unchanged.","tokens_in":5575,"tokens_out":22933,"duration_ms":237132,"concrete_test":"One concrete check: in the 'Uniformly non-trivial fibres' step, replace the asserted K by an explicit derivation: let Q = H/Aut(H) be finite; lift a cycle in Q to a closed non-backtracking walk through each orbit representative, and obtain a uniform K. Then test the x_{n-1}=x_{n+1} case on a small graph (e.g., two triangles joined by a bridge) with a path entering the bridge endpoint: verify that the proposed y is a non-backtracking path for every order of the cycle; if it is not, modify the construction (e.g., reverse the cycle). If neither the K bound nor the modified y can be produced, the covering proof of Theorem 2 is incomplete and should be rewritten or replaced by the Grimmett–Li route.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The advertised independent proof of Theorem 2 via covering maps rests on Proposition 8. Its 'Uniformly non-trivial fibres' paragraph asserts: 'By quasi-transitivity, we can find a K (independent of xn) such that there is a cycle C=... of length m ≤ K.' This is not immediate: quasi-transitivity gives finitely many automorphism orbits, so one must first prove that every vertex lies on a closed non-backtracking walk of length at most K. This is true but requires the finite quotient argument the paper omits. The subsequent construction of y is also unchecked. In the case x_{n-1}=x_{n+1}, the proposed path y = <x0,...,x_{n-1}, x_{n+2},...,x_n> is only non-backtracking if x_{n+2} ≠ x_{n-2}; non-backtracking of C gives x_{n+2} ≠ x_n, not x_{n-2}. So as written the proof can fail even when the claimed covering map exists. The gap is repairable (e.g., choose a simple cycle through π(x) and use the orientation whose first edge avoids x_{n-1}, or derive the bound from the finite quotient), and the main theorem is not endangered because Section 1.1 already derives it from Lemma 3 and [GL15, Thm 4.2]. The concern is therefore a correctness gap in the covering proof, not in the central result.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":5842,"tokens_out":5994,"duration_ms":113616,"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":[{"comment":"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":"Section 3.1, Proposition 8, 'Uniformly non-trivial fibres'"},{"comment":"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":"Section 3.1, Proposition 8, construction of y when x_{n-1}=x_{n+1}"},{"comment":"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.","section":"Section 4, concluding remarks on bounded local girth"}],"minor_comments":[{"comment":"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":"Section 2.2, heading and notation"},{"comment":"The footnote reads 'This also showspc(G) >= ...' with a missing space between 'shows' and 'pc'.","section":"Section 1.1, footnote 2"},{"comment":"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":"Section 2.3, paragraph on subperiodicity"},{"comment":"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.","section":"Section 2.3, final sentence"}],"recommendation":"major_revision","confidential_remarks":"The main theorem of the paper is a direct corollary of Lemma 3 and [GL15, Thm 4.2], as the authors themselves note in Section 1.1. The genuinely new elements are the counterexample family in Section 2 and the attempted covering-map proof in Section 3. The counterexample is correct and nice, but the covering-map proof currently has a substantive gap that needs repair before the manuscript can be accepted. The novelty is modest, and the editor may wish to consider whether the covering-map proof, once fixed, adds enough to justify publication. The author should also be asked to repair the bounded local girth claim in Section 4, which inherits the flaw in Proposition 8."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nWho 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.","headline":"True but known central theorem; the counterexample is the real contribution, and the covering proof has a fixable gap.","tokens_in":6389,"tokens_out":4504,"would_cite":false,"duration_ms":40085,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K35","05C05","05C25"],"pacs":[],"model":"deepseek-v4-flash","headline":"A quasi-transitive d-regular graph attains the minimum bond-percolation threshold 1/(d-1) if and only if it is a tree.","keywords":["percolation threshold","d-regular graphs","quasi-transitive graphs","universal cover","branching number","subperiodic trees","connective constant","strict monotonicity"],"falsifier":"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.","tokens_in":5322,"feed_emoji":"🌳","tokens_out":11203,"duration_ms":93431,"temperature":0.7,"pith_summary":"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.","feed_headline":"Only trees hit the minimum percolation threshold","feed_subtitle":"Quasi-transitive d-regular graphs with cycles have critical probability strictly above 1/(d-1).","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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$."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the strict monotonicity theorem for critical thresholds under strong covering maps with uniformly non-trivial fibres, the engine of the main proof.","marker":"[MS19]"},{"why":"Provides the background on trees, branching number, subperiodicity, and the theorem that subperiodic trees satisfy br T = gr T, used for the counterexample.","marker":"[LP17]"},{"why":"States the result p_c(T)=1/br(T) used to compute the threshold of the counterexample tree.","marker":"[Lyo90]"},{"why":"Gives the classical first- and second-moment argument showing the d-regular tree has threshold 1/(d-1), the baseline for the equality case.","marker":"[Roc24]"}],"fun_headline_variants":["Cycles block optimal percolation in d-regular graphs","Regular trees alone hit the minimum percolation threshold","Non-tree quasi-transitive graphs raise p_c above 1/(d-1)","Percolation minimum reserved for regular trees","Cycles in regular graphs push threshold above tree value"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Cycles block optimal percolation in d-regular graphs","Regular trees alone hit the minimum percolation threshold","Non-tree quasi-transitive graphs raise p_c above 1/(d-1)","Percolation minimum reserved for regular trees","Cycles in regular graphs push threshold above tree value"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000173,"raw_usage":{"total_tokens":1285,"prompt_tokens":957,"completion_tokens":328,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":573,"completion_tokens_details":{"reasoning_tokens":246}},"tokens_in":573,"tokens_out":328,"duration_ms":3980,"temperature":1.0,"reasoning_tokens":246,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T05:10:59.088327+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}