On the phase transition for the number of collisions on comb graphs
Abstract
We consider collisions of simple random walks on comb graphs Comb(ℤ,H), which are obtained by attaching vertical segments of the form [0,Hx] ∩ ℤ to any point x of the integer axis. For Comb(ℤ,H) with profile Hx(x) = |x| logγ(|x| ∨ 1), we show that two independent simple random walks starting from the same site collide infinitely often almost surely if γ≤ 2. If the tooth profile is taken as a typical realization of i.i.d. heavy-tailed random variables with P(Hx > z) ∼ Cz−γ (with some C > 0) as z tends to infinity, we show that infinitely many collisions occur almost surely for two independent random walks if γ> 1/3, whereas finitely many collisions occur almost surely if γ∈ (0,1/3), and for any γ∈ (0,1], three independent random walks only collide finitely many times, almost surely.
Related
- A first order phase transition for lower tails in sparse random graphs
- Phase Transition and Fluctuation Results for First-Passage Percolation on Spread-Out Cycle Graphs
- On the k-Distance Chromatic Number of Unicyclic Graphs
- Minimal Cayley graphs with large chromatic number
- Geometric triangle-free graphs of large chromatic number
BibTeX
@misc{ambroggio2026phase,
title = {{On the phase transition for the number of collisions on comb graphs}},
author = {Umberto De Ambroggio and Jenson Ng and Maximilian Nitzschner and Carlo Scali},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05343},
eprint = {2609.05343},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05343},
}
RIS
TY - UNPB
TI - On the phase transition for the number of collisions on comb graphs
AU - Umberto De Ambroggio
AU - Jenson Ng
AU - Maximilian Nitzschner
AU - Carlo Scali
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05343
UR - https://arxiv.org/abs/2609.05343
AB - We consider collisions of simple random walks on comb graphs Comb(ℤ,H), which are obtained by attaching vertical segments of the form [0,H_x] ∩ ℤ to any point x of the integer axis. For Comb(ℤ,H) with profile H_x(x) = |x| log^γ(|x| ∨ 1), we show that two independent simple random walks starting from the same site collide infinitely often almost surely if γ≤ 2. If the tooth profile is taken as a typical realization of i.i.d. heavy-tailed random variables with P(H_x > z) ∼ Cz^−γ (with some C > 0) as z tends to infinity, we show that infinitely many collisions occur almost surely for two independent random walks if γ> 1/3, whereas finitely many collisions occur almost surely if γ∈ (0,1/3), and for any γ∈ (0,1], three independent random walks only collide finitely many times, almost surely.
ER -