A randomized construction of high girth regular graphs

DOI10.1002/rsa.20976zbMath1522.05470arXiv1911.09640OpenAlexW3103406641MaRDI QIDQ6073632

Michael Simkin, Nathan Linial

Publication date: 11 October 2023

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

graph processeshigh-girth graphsrandom greedy algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Eulerian and Hamiltonian graphs (05C45)

Related Items

Kissing numbers of regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular graphs of large girth and arbitrary degree
• Enumerating all Hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs
• The triangle-free process
• The sextet construction for cubic graphs
• Girths of bipartite sextet graphs
• Ramanujan graphs
• Cubic Ramanujan graphs
• On tail probabilities for martingales
• Constructions for cubic graphs with large girth
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• On random greedy triangle packing
• Short cycles in random regular graphs
• Constrainted graph processes
• The Final Size of the $C_{\ell}$-free Process
• On the girth of random Cayley graphs
• The Final Size of theC₄-Free Process
• A proof of Alon’s second eigenvalue conjecture and related problems
• Random Graph Processes with Degree Restrictions
• A new series of dense graphs of high girth
• A High Girth Graph Construction
• The random k‐matching‐free process
• On the size of a random maximal graph
• Random maximalH-free graphs
• Large girth approximate Steiner triple systems
• On the Method of Typical Bounded Differences
• The C_ℓ‐free process
• Concentration of multivariate polynomials and its applications