Simple versus nonsimple loops on random regular graphs

DOI10.1002/JGT.23056MaRDI QIDQ6199381zbMATH OpenOpenAlexFDO

Authors Benjamin Dozier, Jenya Sapir

Publication date 23 February 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.11218

zbMATH Keywords

nonbacktracking walkrandom graphsregular graphsspectral graph theory

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In this note we solve the ``birthday problem for loops on random regular graphs. Namely, for fixed $dge3$, we prove that on a random $d$-regular graph with $n$ vertices, as $n$ approaches infinity, with high probability: (i) almost all primitive non-backtracking loops of length $kprecsqrtn$ are simple, i.e. do not self-intersect, (ii) almost all primitive non-backtracking loops of length $ksuccsqrtn$ self-intersect.

Recommendations

• Short cycles in random regular graphs
• Circuits in random graphs: from local trees to global loops
• scientific article; zbMATH DE number 1335045
• Cycle lengths in sparse random graphs
• scientific article; zbMATH DE number 909704

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Cutoff on all Ramanujan graphs
• Cutoff phenomena for random walks on random regular graphs
• scientific article; zbMATH DE number 1495995 (Why is no real title available?)
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• On discrete subgroups of the two by two projective linear group over \(p\)-adic fields
• On the minimal diameter of closed hyperbolic surfaces
• On the second eigenvalue and random walks in random d-regular graphs
• Random construction of Riemann surfaces
• The non-backtracking spectrum of the universal cover of a graph

This page was built for publication: Simple versus nonsimple loops on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6199381)