arxiv: 2603.29561 · v2 · submitted 2026-03-31 · 🧮 math.PR

Recognition: 2 theorem links

· Lean Theorem

Accessibility Percolation with Rough Mount Fuji labels

Diana De Armas Bellon , Matthew I. Roberts

Authors on Pith no claims yet

Pith reviewed 2026-05-15 06:29 UTC · model grok-4.3

classification 🧮 math.PR

keywords accessibility percolationBienaymé-Galton-Watson treesphase transitionoriented percolationincreasing pathsrandom labelsdrift models

0 comments

The pith

On Bienaymé-Galton-Watson trees, accessibility percolation occurs with positive probability precisely when the drift parameter θ exceeds an exactly characterizable critical value θ_c.

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

The paper examines infinite rooted graphs where each vertex receives an i.i.d. uniform label plus a linear drift term proportional to its graph distance from the root. It establishes that, for Bienaymé-Galton-Watson trees, an infinite strictly increasing path from the root exists with positive probability if and only if the drift parameter θ lies above a critical threshold θ_c that can be described exactly in terms of the offspring distribution. The same lower bound on θ_c applies to a broader class of trees. On the integer lattice Z^n for n at least 2, the model exhibits a non-trivial phase transition between no percolation and percolation, with the transition proved via a coupling to oriented percolation that yields initial bounds on the critical value.

Core claim

When the graph is a Bienaymé-Galton-Watson tree, there is a critical value θ_c such that accessibility percolation occurs with positive probability if and only if θ > θ_c; the value θ_c admits an exact characterization, and explicit bounds are derived that hold more generally for other trees. On Z^n, n ≥ 2, a non-trivial phase transition exists and the critical value satisfies explicit inequalities obtained from a coupling with oriented percolation.

What carries the argument

The label X_v = U_v + θ d(ρ, v) with U_v i.i.d. Uniform(0,1), together with the event that there exists an infinite path from the root along which the labels are strictly increasing.

If this is right

If θ exceeds the characterized θ_c on a Bienaymé-Galton-Watson tree, then an infinite increasing path from the root exists with positive probability.
If θ lies below θ_c, then every path from the root eventually decreases and no infinite increasing path exists almost surely.
The lower bound on θ_c derived for Bienaymé-Galton-Watson trees continues to hold for a wider family of infinite trees.
On Z^n for n ≥ 2 the model undergoes a phase transition at some finite positive critical value whose bounds follow from the oriented-percolation coupling.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The exact characterization for branching-process trees suggests that similar closed-form thresholds may be derivable for other Galton-Watson-type models with varying offspring distributions.
The oriented-percolation coupling introduced for lattices could be adapted to prove phase transitions on other periodic graphs with drift.
Numerical evaluation of the exact θ_c expression for specific branching laws would allow direct comparison with Monte-Carlo estimates of percolation probability.

Load-bearing premise

The labels added to the distance term are i.i.d. uniform random variables independent of the graph structure, and the graph is an infinite rooted tree or lattice.

What would settle it

For a concrete offspring distribution such as Poisson with mean 1, compute the explicit θ_c and verify whether the probability of an infinite increasing path jumps from zero to positive exactly at that value.

Figures

Figures reproduced from arXiv: 2603.29561 by Diana De Armas Bellon, Matthew I. Roberts.

**Figure 2.** Figure 2: Accessible paths from the origin without backsteps. The left-hand image uses the [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

**Figure 3.** Figure 3: One brick, with the horizontal edges drawn in red, the left-vertical edges drawn in [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗

**Figure 4.** Figure 4: A small portion of the bricklayer lattice with each vertex replaced by a brick. Only [PITH_FULL_IMAGE:figures/full_fig_p028_4.png] view at source ↗

read the original abstract

Consider an infinite, rooted, connected graph where each vertex is labelled with an independent and identically distributed Uniform(0,1) random variable, plus a parameter $\theta$ times its distance from the root $\rho$. That is, we label vertex $v$ with $X_v = U_v + \theta d(\rho,v)$. We say that accessibility percolation occurs if there is an infinite path started from $\rho$ along which the vertex labels are increasing. When the graph is a Bienaym\'e-Galton-Watson tree, we give an exact characterisation of the critical value $\theta_c$ such that there is accessibility percolation with positive probability if and only if $\theta>\theta_c$. We also give more explicit bounds on the value of $\theta_c$. The lower bound holds for a much more general class of trees. When the graph is the lattice $\mathbb{Z}^n$ for $n\ge 2$, we show that there is a non-trivial phase transition and give some first bounds on $\theta_c$. To do this we introduce a novel coupling with oriented percolation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Exact critical value for accessibility percolation on BGWT trees via branching-process reduction, plus a new coupling that gives first bounds on the lattice.

read the letter

The main thing here is an exact characterization of the critical theta for accessibility percolation on Bienaymé-Galton-Watson trees. The labels are i.i.d. uniform plus theta times distance from the root, and an increasing path exists with positive probability precisely when theta exceeds the value that makes the mean number of good children equal to one in an auxiliary branching process. The same comparison argument supplies a lower bound that works on general trees. On Z^n they couple the problem to oriented percolation to prove the transition is non-trivial and to extract initial bounds on theta_c. That coupling is new and avoids some of the usual obstacles with monotone paths in higher dimensions. The tree reduction is standard in form but applied precisely, and the fixed-point analysis has no visible gaps in the recursion or measurability. The lattice bounds are loose, as expected for a first rigorous treatment, but the argument itself is consistent with the i.i.d. labels and additive drift. No free parameters or circular fitting appear. This is for percolation people working on trees or random media with drift. The exact tree result is concrete enough to be useful on its own, and the coupling is a tool others can adapt. I would bring the branching-process calculation to a reading group. It deserves a serious referee.

Referee Report

0 major / 3 minor

Summary. The manuscript studies accessibility percolation on infinite rooted connected graphs with vertex labels given by i.i.d. Uniform(0,1) random variables plus a linear height term θ times graph distance from the root. For Bienaymé-Galton-Watson trees it supplies an exact characterization of the critical threshold θ_c such that an infinite increasing path from the root exists with positive probability if and only if θ > θ_c; the characterization is obtained by reducing the problem to survival of an auxiliary branching process whose offspring law is determined by the probability that a child label exceeds the parent's effective value. Explicit bounds on θ_c are derived, with the lower bound holding for a broader class of trees. For the lattice Z^n (n ≥ 2) the paper establishes a non-trivial phase transition and supplies initial bounds on θ_c by means of a coupling to oriented percolation.

Significance. If the central claims hold, the work advances percolation theory on random graphs and lattices by furnishing an exact, computable threshold on branching-process trees via a fixed-point analysis of an effective offspring distribution. The reduction to an auxiliary branching process and the novel oriented-percolation coupling for the lattice case are technically clean contributions that should be of interest to researchers in probability theory. The lower bound that applies to general trees further broadens the reach of the results.

minor comments (3)

[Section 3] In the statement of the exact characterization for BGWT (presumably Theorem 3.1 or equivalent), the fixed-point equation for the survival probability is presented without an explicit remark on uniqueness of the solution; adding a short sentence confirming that the mean-offspring function is continuous and strictly increasing would clarify the argument.
[Section 4] The coupling construction for the Z^n case (Section 4) is sketched at a high level; a brief diagram or one-sentence description of how the oriented edges are defined from the label comparisons would improve readability for readers unfamiliar with oriented percolation.
[Section 2] Notation for the effective label threshold U_v + θ d(ρ,v) is introduced early but reused with slight variations in the branching-process offspring formula; a single consolidated definition in a preliminary subsection would reduce minor notational friction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. The assessment accurately captures the main results on the exact characterization of θ_c for BGWT trees, the bounds for general trees, and the oriented-percolation coupling for Z^n. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity in the derivation

full rationale

The paper characterizes θ_c for Bienaymé-Galton-Watson trees by mapping accessibility percolation to the survival probability of an auxiliary branching process, where the offspring distribution is derived from the probability that a child's label exceeds the parent's effective value (U_v + θ d(ρ,v)). This is a standard fixed-point analysis on the mean offspring exceeding 1, consistent with the i.i.d. Uniform(0,1) labels and additive distance term. No reduction to fitted parameters, self-definitional loops, or load-bearing self-citations is present. The lower bound on general trees follows from comparison arguments. The lattice case introduces a coupling with oriented percolation, which is an independent construction. The derivation is self-contained against the given probabilistic inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard properties of i.i.d. uniform random variables, branching-process trees, and oriented percolation; no free parameters or invented entities are introduced.

axioms (2)

domain assumption Vertex labels are i.i.d. Uniform(0,1) independent of the graph.
Stated in the model definition; required for the monotonicity and percolation arguments.
standard math The graph is infinite, rooted, and connected (BGWT or Z^n).
Background assumption for defining infinite paths and distance.

pith-pipeline@v0.9.0 · 5488 in / 1188 out tokens · 38235 ms · 2026-05-15T06:29:51.877664+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.2: Q_θ(m) = sum_{j=0}^{⌊1/θ⌋+1} (-m)^j / j! * (1-(j-1)θ)^j =0 defines m_c(θ); percolation iff m > m_c(θ) on BGWT
IndisputableMonolith/Foundation/BranchSelection.lean branch_selection unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proposition 1.8 and Theorem 1.6: first-moment + branching-number lower bound θ_c ≥ 1/(e br_T)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages · 1 internal anchor

[1]

Analysis of a local fitness landscape with a model of the rough mt

Takuyo Aita, Hidefumi Uchiyama, Tetsuya Inaoka, Motowo Nakajima, Toshio Kokubo, and Yuzuru Husimi. Analysis of a local fitness landscape with a model of the rough mt. fuji-type landscape: application to prolyl endopeptidase and thermolysin.Biopolymers: Original Research on Biomolecules, 54(1):64–79, 2000. 30

work page 2000
[2]

Long monotone trails in random edge-labellings of random graphs.Combinatorics, Probability and Computing, 29(1):22–30, 2020

Omer Angel, Asaf Ferber, Benny Sudakov, and Vincent Tassion. Long monotone trails in random edge-labellings of random graphs.Combinatorics, Probability and Computing, 29(1):22–30, 2020

work page 2020
[3]

Athreya and P.E

K.B. Athreya and P.E. Ney.Branching Processes. Springer-Verlag, New York, 1972

work page 1972
[4]

Upper bounds for the critical probability of oriented percolation in two dimensions.Proceedings of the Royal Society of London

Paul Balister, Bela Bollobas, and Alan Stacey. Upper bounds for the critical probability of oriented percolation in two dimensions.Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 440(1908):201–220, 1993

work page 1908
[5]

The number of accessible paths in the hypercube.Bernoulli, 22(2):653–680, 2016

Julien Berestycki, Eric Brunet, and Zhan Shi. The number of accessible paths in the hypercube.Bernoulli, 22(2):653–680, 2016

work page 2016
[6]

Accessibility percolation with backsteps

Julien Berestycki, Eric Brunet, and Zhan Shi. Accessibility percolation with backsteps. Latin American Journal of Probability and Mathematical Statistics, 14:45–62, 2017

work page 2017
[7]

Biggins and Andreas E

John D. Biggins and Andreas E. Kyprianou. Measure change in multitype branching. Advances in Applied Probability, 36(2):544–581, 2004

work page 2004
[8]

Increasing paths in random temporal graphs.The Annals of Applied Probability, 34(6):5498–5521, 2024

Nicolas Broutin, Nina Kamčev, and Gábor Lugosi. Increasing paths in random temporal graphs.The Annals of Applied Probability, 34(6):5498–5521, 2024

work page 2024
[9]

Sharp thresholds in random simple temporal graphs.SIAM Journal on Computing, 53(2):346–388, 2024

Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev. Sharp thresholds in random simple temporal graphs.SIAM Journal on Computing, 53(2):346–388, 2024

work page 2024
[10]

Increasing paths on N-ary trees

Xinxin Chen. Increasing paths on n-ary trees.arXiv preprint arXiv:1403.0843, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014
[11]

Valencia

Frank Duque, Daniel Ramirez-Gomez, Alejandro Roldán-Correa, and Leon A. Valencia. Rmf accessibility percolation on oriented graphs.Journal of Statistical Mechanics: Theory and Experiment, 2023(2):023203, 2023

work page 2023
[12]

Robert Hardy and Simon C. Harris. A spine approach to branching diffusions with applica- tions toLp-convergence of martingales. InSéminaire de probabilités XLII, pages 281–330. Springer, 2009

work page 2009
[13]

On the existence of accessible paths in various models of fitness landscapes.Annals of Applied Probability, 24(4):1375–1395, 2014

Peter Hegarty and Anders Martinsson. On the existence of accessible paths in various models of fitness landscapes.Annals of Applied Probability, 24(4):1375–1395, 2014

work page 2014
[14]

John F. Kingman. A simple model for the balance between selection and mutation.Journal of Applied Probability, 15(1):1–12, 1978

work page 1978
[15]

Kyprianou

Andreas E. Kyprianou. Travelling wave solutions to the KPP equation: alternatives to simon harris’ probabilistic analysis.Annales de l’Institut Henri Poincare (B) Probability and Statistics, 40(1):53–72, 2004

work page 2004
[16]

Conceptual proofs oflloglcriteria for mean behavior of branching processes.The Annals of Probability, pages 1125–1138, 1995

Russell Lyons, Robin Pemantle, and Yuval Peres. Conceptual proofs oflloglcriteria for mean behavior of branching processes.The Annals of Probability, pages 1125–1138, 1995

work page 1995
[17]

Cambridge University Press, New York, 2016

Russell Lyons and Yuval Peres.Probability on Trees and Networks, volume 42 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, 2016

work page 2016
[18]

Accessibility percolation onn-trees.Europhysics Letters, 101(6):66004, 2013

Stefan Nowak and Joachim Krug. Accessibility percolation onn-trees.Europhysics Letters, 101(6):66004, 2013

work page 2013
[19]

A remark on Stirling’s formula.The American Mathematical Monthly, 62(1):26–29, 1955

Herbert Robbins. A remark on Stirling’s formula.The American Mathematical Monthly, 62(1):26–29, 1955. 31

work page 1955
[20]

Roberts and Lee Zhuo Zhao

Matthew I. Roberts and Lee Zhuo Zhao. Increasing paths in regular trees.Electronic Communications in Probability, 18:1–10, 2013. 32

work page 2013