Moderate deviations in cycle count

DOI10.1002/RSA.21147MaRDI QIDQ6076734zbMATH OpenOpenAlexFDO

Authors Joe Neeman, Charles Radin, Lorenzo Sadun

Publication date 17 October 2023

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

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

zbMATH Keywords

large deviationsmoderate deviationsrandom graphssubgraph countsubgraph density

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove moderate deviations bounds for the lower tail of the number of odd cycles in a $calG(n,m)$ random graph. We show that the probability of decreasing triangle density by $t^3$, is $exp(-Theta(n^2{t}^2))$ whenever $n^{-3/4}ll{t}^{3}ll1$, while for $kge5$ we give the same estimate for the probability of decreasing the $k$-cycle density by $t^k$, but for the larger range $n^{-1}ll{t}^{k}ll1$. When $$, we also find the leading coefficient in the exponent. This complements results of Goldschmidt et al., who showed that for $n^{-3/2}ll{t}^{k}ll{n}^{-1}$, the probability is $exp(-Theta(n^3{t}^{2k}))$. That is, deviations of order smaller than $n^{-1}$ behave like small deviations, and deviations of order larger than $n^{-3/4}$ (for triangles) or $n^{-1}$ (for $k$-cycles with $kge5$) behave like large deviations. For triangles, we conjecture that a sharp change between the two regimes occurs for deviations of size $n^{-3/4}$, which we associate with a single large negative eigenvalue of the adjacency matrix becoming responsible for almost all of the cycle deficit. Our results can be interpreted as finite size effects in phase transitions in constrained random graphs.

Recommendations

• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Moderate deviations in a random graph and for the spectrum of Bernoulli random matrices
• Moderate deviation in colored random graphs
• Sub-Gaussian tails for the number of triangles in G( n, p)
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs

Cites work

• A large deviation principle for the Erdős-Rényi uniform random graph
• A Note on von Neumann's Trace Inequalitv
• A symmetry breaking transition in the edge/triangle network model
• An introduction to large deviations for random graphs
• Bipodal structure in oversaturated random graphs
• Concentration inequalities using the entropy method
• Concentration of the spectral measure for large matrices
• Large deviations for the largest eigenvalue of Rademacher matrices
• Large deviations for the largest eigenvalue of sub-Gaussian matrices
• Large deviations of subgraph counts for sparse Erdős-Rényi graphs
• Large deviations principle for the largest eigenvalue of Wigner matrices without Gaussian tails
• Large deviations techniques and applications.
• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Multipodal structure and phase transitions in large constrained graphs
• Nonlinear large deviations
• On replica symmetry of large deviations in random graphs
• On the lower tail variational problem for random graphs
• On the variational problem for upper tails in sparse random graphs
• Orthogonal decompositions and functional limit theorems for random graph statistics
• Phase transitions in a complex network
• Phase transitions in finite random networks
• Poisson approximation for large deviations
• Singularities in the entropy of asymptotically large simple graphs
• The asymptotics of large constrained graphs
• The infamous upper tail
• The large deviation principle for the Erdős-Rényi random graph
• The lower tail: Poisson approximation revisited
• The missing log in large deviations for triangle counts
• The phases of large networks with edge and triangle constraints
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements
• Upper tails and independence polynomials in random graphs
• Upper tails for edge eigenvalues of random graphs
• Vertex order in some large constrained random graphs

Cited in

(7)

• Moderate deviations of subgraph counts in the Erdős-Rényi random graphs \(G(n,m)\) and \(G(n,p)\)
• Existence of a symmetric bipodal phase in the edge-triangle model
• Optimal graphons in the edge-2star model
• Tripodal structure in undersaturated random graphs
• Large deviations of the largest eigenvalue of supercritical sparse Wigner matrices
• Moderate deviations of triangle counts in the Erdős-Rényi random graph G (n, m): the lower tail
• Moderate deviations of triangle counts in sparse Erdős-Rényi random graphs G(n, m) and G(n, p)

This page was built for publication: Moderate deviations in cycle count

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