Simple versus nonsimple loops on random regular graphs
Open accessAbstract
In this note, we solve the “birthday problem” for loops on random regular graphs. Namely, for fixed , we prove that on a random ‐regular graph with vertices, as approaches infinity, with high probability: (i) almost all primitive nonbacktracking loops of length are simple, that is, do not self‐intersect, and (ii) almost all primitive nonbacktracking loops of length self‐intersect.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
A Probabilistic Proof of an Asymptotic Formula for the Number of Labelled Regular Graphs
Bollobás, B. (1980) · European Journal of Combinatorics · doi:10.1016/s0195-6698(80)80030-8 · Cited by 1,204 · see citing works
A proof of Alon’s second eigenvalue conjecture and related problems
Friedman, J. (2008) · Memoirs of the American Mathematical Society · doi:10.1090/memo/0910 · Cited by 341 · see citing works
On discrete subgroups of the two by two projective linear group over $\mathfrak{p}$ -adic fields
Ihara, Y. (1966) · Journal of the Mathematical Society of Japan · doi:10.2969/jmsj/01830219 · Cited by 330 · see citing works
On the second eigenvalue and random walks in randomd-regular graphs
Friedman, J. (1991) · COMBINATORICA · doi:10.1007/bf01275669 · Cited by 169 · see citing works
Zeta Functions of Finite Graphs
Kotani, M., & Sunada, T. (2000) · Institutional Repositories DataBase (IRDB) · Cited by 169 · see citing works
NON-BACKTRACKING RANDOM WALKS MIX FASTER
ALON, N., BENJAMINI, I., LUBETZKY, E., et al. (2007) · Communications in Contemporary Mathematics · doi:10.1142/s0219199707002551 · Cited by 126 · see citing works
On the second eigenvalue of random regular graphs
Broder, A., & Shamir, E. (1987) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1987.45 · Cited by 106 · see citing works
Cutoff phenomena for random walks on random regular graphs
Lubetzky, E., & Sly, A. (2010) · Duke Mathematical Journal · doi:10.1215/00127094-2010-029 · Cited by 102 · see citing works
Random Construction of Riemann Surfaces
Brooks, R. M., & Makover, E. (2004) · Journal of Differential Geometry · doi:10.4310/jdg/1102536712 · Cited by 94 · see citing works
The non-backtracking spectrum of the universal cover of a graph
Angel, O., Friedman, J., & Hoory, S. (2014) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-2014-06255-7 · Cited by 80 · see citing works
Cutoff on all Ramanujan graphs
Lubetzky, E., & Peres, Y. (2016) · Geometric and Functional Analysis · doi:10.1007/s00039-016-0382-7 · Cited by 57 · see citing works
On the minimal diameter of closed hyperbolic surfaces
Budzinski, T., Curien, N., & Petri, B. (2020) · Duke Mathematical Journal · doi:10.1215/00127094-2020-0083 · Cited by 11 · see citing works
Flagged first, then by citations
Research works printed but not linked: 2
- B Bollobás, Random graphs, 2nd ed. Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001.
- M. Lipnowski and A. Wright, Towards optimal spectral gaps in large genus, Annal. of Prob. (2021). https:// imstat.org/journals-and-publications/annals-of-probability/annals-of-probability-future-papers/
Cited by
Sorted by citations
Beyond-classical computation in quantum simulation
King, A. D., Nocera, A., Rams, M. M., Dziarmaga, J., Wiersema, R., Bernoudy, W., Raymond, J., Kaushal, N., Heinsdorf, N., Harris, R., et al. (2025) · Science · doi:10.1126/science.ado6285 · Cited by 138 · see citing works
- Authors
- Dozier, B., & Sapir, J.
- Affiliations
- Cornell University (US)
- Binghamton University (US)
- Corresponding author
- Dozier, Benjamin
- Venue
- Journal of Graph Theory
- Publisher
- Wiley
- Published
- 2023-11-21
- Volume
- 105
- Issue
- 4
- Pages
- 562-579
- ISSN
- 0364-9024 (ISSN-L)
- 1097-0118
- OpenAlex
- W4388850633
- Cited by
- 1
- References
- 12
- Citations by year
- 2025: 1
- FWCI
- 0.57
- Type
- journal article
- Language
- en
- Open access
- bronze
- dx.doi.org
- Locations
- Journal of Graph Theory (publishedVersion)
- Topics
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Limits and Structures in Graph Theory
- Physical Sciences › Mathematics › Mathematical Physics › Stochastic processes and statistical mechanics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Advanced Graph Theory Research
- Keywords
- random regular graphs, loops, self-intersection, simple loops, birthday problem, asymptotic probability
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
