Pith. sign in

REVIEW 1 major objections 3 minor 25 references

Meeting and coalescence times for random walks in the largest component of the Erd\H{o}s-R\'enyi random graph

T0 review · 1 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read Two independent random walks on the largest component of an Erdős–Rényi random graph meet in expected time of order n, the ambient vertex count, across strictly supercritical, slightly supercritical, and critical regimes; the same linear sc

desk verdict New Θ(n) meeting/coalescence results on the Erdős–Rényi giant across all three regimes; referee must check the unproved uniform expansion lemma. read the letter →

arxiv 2607.13183 v1 pith:CV7MBUZT submitted 2026-07-14 math.PR

Vyacheslav Koval , Yuval Peres , Pieter Trapman This is my paper
classification math.PR MSC 05C8160J2705C8060K35
keywords Erdős–RényirandomgraphmeetingtimewalksongraphscoalescingvotermodelcriticalwindoweffectiveresistanceKemeny'sconstant
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

The paper proves that two independent continuous-time simple random walks on the largest component of an Erdős–Rényi random graph meet in expected time that grows linearly with the number of vertices n, from both stationary and worst-case starting positions. This linear scale holds throughout the strictly supercritical (fixed λ>1), slightly supercritical (ε→0 with ε^3 n→∞), and critical-window (|n^{1/3}(np_n−1)|≤A_0) regimes. The same order-n bound is then shown for the full coalescence time of walks started at every vertex and for voter-model consensus time with all opinions distinct. The result matters because meeting, coalescence, and consensus are fundamental dynamical processes on random networks; establishing a sharp scale across the phase transition clarifies how connectivity controls their speed.

What carries the argument

The central object is the random target time t_⊙(G)=|E(G)| Σ_{u,v} π(u)π(v) R_eff(u,v), which equals Kemeny's constant and is the degree-weighted average effective resistance. The proof bounds this quantity uniformly in each regime—using the core-and-attached-trees structure of the contiguous configuration-model surrogate for the supercritical giant, and using volume, diameter, mixing, and resistance estimates in the critical window—then converts it to a worst-case meeting-time bound via a general comparison inequality. The lower bound rests on the variational extremal characterization of hitting times: a low-energy test function that vanishes except when the two walks are close on the core

What would settle it

Find a sequence (n, ε_n) with ε_n^3 n → ∞ such that the degree-weighted average effective resistance of the largest component of G(n,(1+ε_n)/n) is not of order ε_n^{-1} while its edge count is of order ε_n n; then the random target time would not be O(n) and the meeting-time upper bound would fail. Numerically, computing E_{π⊗π} τ_meet for such sequences and checking that the ratio to n stays within fixed positive bounds would provide evidence; a clear divergence from linear scaling would refute the claim.

Watch

Extended reading notes

Core claim

The central claim is that with high probability, for the largest component C_1 of G(n,p) in any of the three regimes, c n ≤ E_{π⊗π} τ_meet ≤ t_meet(C_1) ≤ C n, where c,C are absolute constants in the supercritical cases and may depend on the window parameter in the critical case; a corollary extends the same order to expected coalescence and voter consensus time. The upper bound follows by showing that the random target time (Kemeny's constant) is O(n), using degree-weighted average effective-resistance estimates on the auxiliary configuration-model decomposition of the giant component, and then applying a general comparison between worst-case meeting time and the sum of mixing time and rand

Load-bearing premise

The supercritical proofs rely on transferring estimates from the auxiliary configuration-model decomposition to the actual Erdős–Rényi giant via contiguity; if a high-probability property of the auxiliary model fails to hold for the actual giant in the required direction, the linear meeting-time bounds would not apply to G(n,p).

Editorial extensions

If this is right

  • Two-walk meeting time on the giant component is Θ(n) even at criticality, where the component has only n^{2/3} vertices, so the ambient scale n is the correct normalization.
  • Coalescence of one walk per vertex and voter-model consensus inherit the same Θ(n) scale, so opinion dynamics on these networks reach consensus in linear time.
  • The constants in the supercritical regimes are independent of the edge probability parameter over a wide range, indicating a robust universal scale.
  • The proof strategy—resistance-based target-time bounds plus variational lower bounds—may transfer to other random graph models with a similar core-and-trees decomposition.
  • The critical-window result closes the gap between known subcritical and supercritical behaviors, giving a complete picture across the phase transition.

Reading between the lines

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

  • The linear meeting-time scale likely extends to other two-particle quantities, such as the expected number of meetings by time t, which would behave as t/n.
  • A testable extension: in the supercritical regimes the meeting-time distribution may be approximately exponential with rate Θ(1/n) because the process mixes on a much shorter time scale.
  • The resistance-based techniques could give sharp bounds on cover times or other additive functionals on the critical component, where the ambient n scale emerges from the edge count times resistance.
  • The contiguity transfer suggests that any high-probability, isomorphism-invariant resistance or mixing estimate that holds in the auxiliary configuration model will also hold in the actual Erdős–Rényi giant, which may simplify future analyses of random-graph walks.
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.

Referee Report

1 major / 3 minor

Summary. The paper proves that the stationary and worst-case expected meeting times of two independent continuous-time simple random walks on the largest component of the Erdős–Rényi random graph G(n,p) are of order n in three regimes: fixed supercritical (p=λ/n, λ>1), slightly supercritical (p=(1+ε)/n with ε→0 and ε^3 n→∞), and the critical window (|n^{1/3}(np_n−1)|≤A_0). The proof combines the DKLP/DLP contiguous configuration-model decomposition with electrical-resistance identities for Kemeny's constant, Aldous's meeting-time comparison, variational lower-bound test functions, and, in the critical window, the Nachmias–Peres estimates. The meeting-time bounds are then extended to coalescence times and voter-model consensus times via comparison results of Oliveira and Kanade–Mallmann-Trenn–Sauerwald.

Significance. If the result holds, it is a substantial contribution: it establishes a uniform Θ(n) scale for two-walk meeting times across the entire supercritical-to-critical transition, with constants that are absolute in the supercritical regimes, and it transfers this to coalescence and voter consensus. The paper is well organized, gives self-contained proofs of the electrical and variational estimates, and makes clever use of existing random-graph structure results. The main proof strategy is convincing and the parameter-uniform formulations are carefully stated. However, the upper bounds rely on an unproved 'uniform form' of an external lemma, which is load-bearing and must be resolved.

major comments (1)
  1. [Section 5, Lemma 10 (after Eq. (25))] The proof of the upper bound rests on the assertion that 'the uniform form of Benjamini–Kozma–Wormald [5, Lemma 5.3] applies: it covers every even degree sequence satisfying 3≤min_i d_i ≤ max_i d_i ≤ N^{0.02}.' No statement or proof of this uniform version is provided, and the cited reference is not shown to contain it. This is not a cosmetic issue: Lemma 10 is used to obtain the spectral-gap bounds (23)–(24), which drive Lemma 11, Lemma 13, Lemma 14, and Lemma 17, and hence the upper bounds in Theorem 1(i)–(ii). Please supply a proof of the uniform extension or an exact reference with a theorem statement. This is a missing-support concern and should be resolved before acceptance.
minor comments (3)
  1. [Section 5, proof of Lemma 10] The parity argument for the small-Λ range (0<Λ<1) is terse: the constants c, C in 'cΛ≤P(Y_Λ is odd)≤CΛ' are not tracked, and the relation between the conditioned-Poisson variable D_Λ and Y_Λ could be made more explicit. Since the lemma claims uniformity, please spell out the constants.
  2. [Section 8, proof of Lemma 28] The inequality 't^{ct}_{meet} ≤ δ t^Q_{meet} ≤ C(t^{ct}_{meet}+δ)' is stated without referencing the two displayed inequalities (108)–(109) from the proof of Lemma 26. Adding the explicit cross-references would aid readability.
  3. [General] The paper is long and the exploration argument in Lemma 15 is intricate. A short intuitive summary of the 'arrival-ticket' coupling, or a figure analogous to Figure 1, would help readers follow the proof.

Circularity Check

0 steps flagged · score 0.0 of 10

Meeting-time bounds are derived from independent structural and Markov-chain estimates; no prediction reduces to its fitted input or to a self-citation chain.

full rationale

The paper's central meeting-time result is not circular. The upper bound for the slightly supercritical giant is obtained by combining Kemeny's identity (Lemma 5), Aldous's meeting-time comparison (Lemma 6), and random-graph estimates: the DKLP auxiliary model, kernel expansion (Lemma 10), weighted core resistance (Lemma 13), and average target time (Lemma 14). These lemmas are proved from stated graph-theoretic and Markov-chain inputs, not from the meeting time itself. The lower bound uses the variational Lemma 7 with an explicitly constructed core-projection test function, whose stationary mean and Dirichlet energy are bounded via Lemmas 16 and 9; it does not presume the desired bound. The critical-window and fixed-supercritical regimes are handled by independent estimates from Nachmias–Peres [20] and by the DLP/DKLP decompositions, with no parameter fitted to meeting-time data. The coalescence/voter corollary is derived from meeting-time bounds through Oliveira's and KMS comparison inequalities, which are external results applied to the already-established meeting-time scale, not definitions of the meeting time in terms of coalescence. The paper's use of self-citations (DKLP, DLP, Nachmias–Peres) is to import prior structural theorems about component sizes, mixing times, diameters, and contiguity; these are independent of the meeting-time conclusion and do not constitute a uniqueness argument or an ansatz that presupposes the result. The only notable support gap is Lemma 10's invocation of a 'uniform form' of Benjamini–Kozma–Wormald [5, Lemma 5.3] for every degree sequence satisfying max degree ≤ N^{0.02}; the paper does not prove this uniform extension, and it is load-bearing for the kernel spectral gap. This is a question of unverified external support, not circularity, since even if the uniform form fails the argument does not reduce to assuming its own conclusion. No step was found in which a 'prediction' is equivalent by construction to a fitted input or to the defining assumption of an auxiliary model.

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

There are no fitted free parameters: the constants c,C,C_A0,η are existential proof constants, not numerical values fitted to data. There are no newly postulated physical or mathematical entities; the DKLP model is an auxiliary construction taken from prior literature. The central claim rests on published structural theorems about the Erdős–Rényi giant, none of which already contains the meeting-time result, so the circularity burden is low.

assumptions (6)
  • domain assumption DKLP contiguity theorem for the slightly supercritical giant [9, Theorem 2]
    Used in §5 and §7 to transfer Lemma 3 from the auxiliary DKLP model to G(n,(1+ε)/n). Published, but load-bearing for the slightly supercritical regime.
  • domain assumption Strictly supercritical contiguous decomposition of Ding–Lubetzky–Peres [13, Theorem 1]
    Used in Lemma 17 and Lemma 19 for fixed λ>1 to transfer resistance and meeting bounds from the contiguous model to the actual giant.
  • standard math Mixing-time bounds for near-critical and strictly supercritical giants [12, Theorem 1; 5, Theorem 1.1]
    Used to control t_mix in Lemma 6 and in the proof of Theorem 1(ii). These are external published theorems, not proved in this paper.
  • domain assumption Nachmias–Peres critical-window estimates [20, Theorems 1.1–1.2, Lemma 5.4, Propositions 5.5–5.7]
    The entire critical-window upper and lower bounds in Theorem 1(iii) and Corollary 2(iii) rest on these volume, diameter, mixing, and resistance estimates.
  • standard math Comparison inequalities of Aldous, Oliveira, and Kanade–Mallmann-Trenn–Sauerwald [1; 22; 16]
    Used to convert meeting-time bounds into coalescence and voter-consensus bounds. These are external published theorems; the paper extends them to the needed continuous-time and small-particle forms.
  • standard math Standard electrical-network and Markov-chain identities: commute-time identity, Kemeny constant resistance formula, Nash–Williams inequality, variational hitting-time characterization
    Used throughout; these are textbook facts from [17, 19, 21] and are not proved in full.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Meeting and coalescence times for random walks in the largest component of the Erd\H{o}s-R\'enyi random graph." pith.science (2026). https://pith.science/paper/CV7MBUZT

@misc{pith2026260713183,
  author       = {Pith},
  title        = {Pith review of: Meeting and coalescence times for random walks in the largest component of the Erd\Hos-R\'enyi random graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CV7MBUZT}},
  note         = {Machine review of arXiv:2607.13183}
}
abstract

We prove that the stationary and worst-case expected meeting times of two independent continuous-time random walks on the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ have order $n$ throughout the strictly supercritical, the slightly supercritical and the critical regimes. Using these bounds along with a fine-tuned combination of comparison inequalities due to Oliveira (2012) and Kanade-Mallmann-Trenn-Sauerwald (KMS, 2023), we deduce that expected coalescence time and full voter-model consensus also have order $n$ throughout these three regimes.

Figures

Figures reproduced from arXiv: 2607.13183 by the authors.

Figure 1
Figure 1. Schematic of the Ding–Kim–Lubetzky–Peres configuration-model construction [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 2 canonical work pages

  1. [1]

    Aldous,Meeting times for independent Markov chains, Stochastic Processes and their Applications38(1991), no

    D. Aldous,Meeting times for independent Markov chains, Stochastic Processes and their Applications38(1991), no. 2, 185–193. doi:10.1016/0304-4149(91)90090-Y

    doi:10.1016/0304-4149(91)90090-y 1991

  2. [2]

    Aldous and J

    D. Aldous and J. A. Fill,Reversible Markov Chains and Random Walks on Graphs, unfinished monograph, 2002; recompiled version, 2014. Available at https://www.stat.berkeley.edu/~aldous/RWG/book.html

    2002

  3. [3]

    Avena, F

    L. Avena, F. Capannoli, R. S. Hazra and M. Quattropani,Meeting, coalescence and consensus time on random directed graphs, Annals of Applied Probability34(2024), no. 5, 4940–4997.doi:10.1214/24-AAP2087. arXiv:2308.01832

    arXiv 2024

  4. [4]

    M. T. Barlow, J. Ding, A. Nachmias and Y. Peres,The evolution of the cover time, Combinatorics, Probability and Computing20(2011), no. 3, 331–345. doi:10.1017/S0963548310000489. arXiv:1001.0609

    arXiv 2011

  5. [5]

    Benjamini, G

    I. Benjamini, G. Kozma and N. C. Wormald,The mixing time of the giant component of a random graph, Random Structures & Algorithms45(2014), no. 3, 383–407. doi:10.1002/rsa.20539. arXiv:math/0610459. 44

    arXiv 2014

  6. [6]

    Cooper and A

    C. Cooper and A. M. Frieze,The cover time of the giant component of a random graph, Random Structures & Algorithms32(2008), no. 4, 401–439. doi:10.1002/rsa.20201. arXiv:0803.0929

    arXiv 2008

  7. [7]

    Cooper, A

    C. Cooper, A. M. Frieze and T. Radzik,Multiple random walks in random regu- lar graphs, SIAM Journal on Discrete Mathematics23(2009), no. 4, 1738–1761. doi:10.1137/080729542

    doi:10.1137/080729542 2009

  8. [8]

    J. T. Cox,Coalescing random walks and voter model consensus times on the torus in Zd, Annals of Probability17(1989), no. 4, 1333–1366. doi:10.1214/aop/1176991158

    arXiv 1989

Show all 25 references
  1. [9]

    J. Ding, J. H. Kim, E. Lubetzky and Y. Peres,Anatomy of a young giant component in the random graph, Random Structures & Algorithms39(2011), no. 2, 139–178. doi:10.1002/rsa.20342. arXiv:0906.1839

    2011 arXiv

  2. [10]

    J. Ding, J. H. Kim, E. Lubetzky and Y. Peres,Diameters in supercritical random graphs via first passage percolation, Combinatorics, Probability and Computing19 (2010), no. 5–6, 729–751.doi:10.1017/S0963548310000301. arXiv:0906.1840

    2010 arXiv

  3. [11]

    J. Ding, J. R. Lee and Y. Peres,Cover times, blanket times, and ma- jorizing measures, Annals of Mathematics (2)175(2012), no. 3, 1409–1471. doi:10.4007/annals.2012.175.3.8. arXiv:1004.4371

    2012 arXiv

  4. [12]

    J. Ding, E. Lubetzky and Y. Peres,Mixing time of near-critical random graphs, Annals of Probability40(2012), no. 3, 979–1008.doi:10.1214/11-AOP647. arXiv:0908.3870

    2012 arXiv

  5. [13]

    J. Ding, E. Lubetzky and Y. Peres,Anatomy of the giant component: The strictly supercritical regime, European Journal of Combinatorics35(2014), 155–168. doi:10.1016/j.ejc.2013.06.004. arXiv:1202.6112

    2014 arXiv

  6. [14]

    van der Hofstad,Random Graphs and Complex Networks

    R. van der Hofstad,Random Graphs and Complex Networks. Volume 1, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 43, Cambridge University Press, Cambridge, 2017.doi:10.1017/9781316779422

    2017 doi

  7. [15]

    T. E. Harris,Additive set-valued Markov processes and graphical methods, Annals of Probability6(1978), no. 3, 355–378.doi:10.1214/aop/1176995523

    1978

  8. [16]

    Kanade, F

    V. Kanade, F. Mallmann-Trenn and T. Sauerwald,On coalescence time in graphs: When is coalescing as fast as meeting?, ACM Transactions on Algorithms19(2023), no. 2, Article 18, 46 pp.doi:10.1145/3576900. arXiv:1611.02460

    2023 arXiv

  9. [17]

    D. A. Levin and Y. Peres,Markov Chains and Mixing Times, 2nd ed., with contributions by E. L. Wilmer, American Mathematical Society, Providence, RI, 2017. doi:10.1090/mbk/107

    2017 doi

  10. [18]

    T. M. Liggett,Stochastic Interacting Systems: Contact, Voter and Exclusion Pro- cesses, Grundlehren der Mathematischen Wissenschaften, vol. 324, Springer, Berlin, 1999.doi:10.1007/978-3-662-03990-8

    1999 doi

  11. [19]

    Lyons and Y

    R. Lyons and Y. Peres,Probability on Trees and Networks, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 42, Cambridge University Press, Cambridge, 2016.doi:10.1017/9781316672815. 45

    2016 doi

  12. [20]

    Nachmias and Y

    A. Nachmias and Y. Peres,Critical random graphs: Diameter and mixing time, Annals of Probability36(2008), no. 4, 1267–1286. doi:10.1214/07-AOP358. arXiv:math/0701316

    2008 arXiv

  13. [21]

    C. St. J. A. Nash-Williams,Random walk and electric currents in net- works, Proceedings of the Cambridge Philosophical Society55(1959), 181–194. doi:10.1017/S0305004100033879

    1959 doi

  14. [22]

    R. I. Oliveira,On the coalescence time of reversible random walks, Trans- actions of the American Mathematical Society364(2012), no. 4, 2109–2128. doi:10.1090/S0002-9947-2011-05523-6. arXiv:1009.0664

    2012 arXiv

  15. [23]

    R. I. Oliveira,Mean field conditions for coalescing random walks, Annals of Probability 41(2013), no. 5, 3420–3461.doi:10.1214/12-AOP813. arXiv:1109.5684

    2013 arXiv

  16. [24]

    Penrose,A generalized inverse for matrices, Proceedings of the Cambridge Philosophical Society51(1955), 406–413.doi:10.1017/S0305004100030401

    R. Penrose,A generalized inverse for matrices, Proceedings of the Cambridge Philosophical Society51(1955), 406–413.doi:10.1017/S0305004100030401

    1955 doi

  17. [25]

    X. Wang, J. L. A. Dubbeldam and P. Van Mieghem,Kemeny’s constant and the effective graph resistance, Linear Algebra and its Applications535(2017), 231–244. doi:10.1016/j.laa.2017.09.003. 46

    2017 doi

Pith tools

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