Short cycles in random regular graphs
From MaRDI portal
Consider random regular graphs of order \(n\) and degree \(d = d(n)\) with \(g = g(n)\) such that \((d - 1)^{2g-1} = o(n)\). It is shown that the number of cycles of lengths up to \(g\) has a distribution similar to independent Poisson variables. More specifically, let \(\{c_1, c_2, \dots, c_t\}\) be a subset of \(\{3, 4, \dots, g\}\) and define \( \mu_i = (d-1)^{c_i}/(2c_i)\) for \(3 \leq i \leq g\). It is shown that the probabilty that a random \(d\)-regular graph of order \(n\) has no cycles of length \(c_i\) for \(1 \leq i \leq t\) is \[ \exp\left(-\sum^t_{i=1} \mu_i + o(1) \right) \] as \(n \rightarrow \infty\).
Recommendations
Cited in
(57)- On the number of paths and cycles for almost all graphs and digraphs
- Size biased couplings and the spectral gap for random regular graphs
- ``Immunetworks, intersecting circuits and dynamics
- Non-localization of eigenfunctions on large regular graphs
- Cycles of given lengths in unicyclic components in sparse random graphs
- Kissing numbers of regular graphs
- Evaluations of Tutte polynomials of regular graphs
- Threshold functions for small subgraphs in simple graphs and multigraphs
- Limiting distribution of short cycles in inhomogeneous random uniform hypergraph
- Exchangeable pairs, switchings, and random regular graphs
- L^p norms and support of eigenfunctions on graphs
- Quantum ergodicity on large regular graphs
- On coupon colorings of graphs
- Local Kesten-McKay law for random regular graphs
- The length of closed geodesics on random Riemann surfaces
- Two notions of unit distance graphs
- Random cluster model on regular graphs
- The Marčenko-Pastur law for sparse random bipartite biregular graphs
- Quantum ergodicity for quantum graphs without back-scattering
- Geodesics and almost geodesic cycles in random regular graphs
- Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees
- Circuits in random graphs: from local trees to global loops
- Regular graphs whose subgraphs tend to be acyclic
- Short cycle distribution in random regular graphs recursively generated by pegging
- Functional limit theorems for random regular graphs
- scientific article; zbMATH DE number 1174626 (Why is no real title available?)
- Poisson eigenvalue statistics for random Schrödinger operators on regular graphs
- Poisson approximation of the length spectrum of random surfaces
- Bipartite independence number in graphs with bounded maximum degree
- Counting short cycles of \((c,d)\)-regular bipartite graphs
- Discrete graphs -- a paradigm model for quantum chaos
- Exactly solvable random graph ensemble with extensively many short cycles
- (Dis)assortative partitions on random regular graphs
- Expanders with respect to Hadamard spaces and random graphs
- Cycle lengths in sparse random graphs
- A randomized construction of high girth regular graphs
- The number of perfect matchings, and the nesting properties, of random regular graphs
- Global eigenvalue fluctuations of random biregular bipartite graphs
- Subgraph distributions in dense random regular graphs
- Causal Structural Learning via Local Graphs
- Triangles and subgraph probabilities in random regular graphs
- Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs
- On the second eigenvalue of random bipartite biregular graphs
- Simple versus nonsimple loops on random regular graphs
- Predicting Feynman periods in ^4-theory
- The systole of random hyperbolic 3-manifolds
- Dark matter and dark energy in combinatorial quantum gravity
- Sparse regular random graphs: spectral density and eigenvectors
- Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
- High-dimensional structure estimation in Ising models: local separation criterion
- Length spectrum of large genus random metric maps
- Spectrum preserving short cycle removal on regular graphs
- Limit vectors of the top k eigenvalues of d-regular graphs
- Edge universality of random regular graphs of growing degrees
- An optimal error-correcting reduction for matrix multiplication
- Counting triangles in power-law uniform random graphs
- On quantum percolation in finite regular graphs
This page was built for publication: Short cycles in random regular graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773189)
