Upper tails for subgraph counts in random graphs

DOI10.1007/BF02771528zbMath1055.05136WikidataQ105583332 ScholiaQ105583332MaRDI QIDQ1881736

Krzysztof Oleszkiewicz, Svante Janson, Andrzej Ruciński

Publication date: 15 October 2004

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

subgraph countsexponential bounds of tail probabilities

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Approximations to statistical distributions (nonasymptotic) (62E17)

Related Items

Nonlinear large deviations, The missing log in large deviations for triangle counts, Upper tails for triangles, On replica symmetry of large deviations in random graphs, Combinatorial theorems in sparse random sets, Upper tails via high moments and entropic stability, Upper tails and independence polynomials in random graphs, Applications of Stein's method for concentration inequalities, Localization in random geometric graphs with too many edges, Upper tails for arithmetic progressions in random subsets, Threshold functions for small subgraphs in simple graphs and multigraphs, Upper tail for homomorphism counts in constrained sparse random graphs, Large deviations for subcomplex counts and Betti numbers in multiparameter simplicial complexes, Threshold functions for small subgraphs: an analytic approach, Exponential inequalities for the number of subgraphs in the Erdös-Rényi random graph, Nonlinear large deviations: beyond the hypercube, The upper tail problem for induced 4‐cycles in sparse random graphs, Upper Tail Large Deviations of Regular Subgraph Counts in Erdős‐Rényi Graphs in the Full Localized Regime, Large deviations of subgraph counts for sparse Erdős-Rényi graphs, Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs, Detecting local network motifs, Unnamed Item, Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs, Upper Tail Bounds for Cycles, On the number of weakly connected subdigraphs in random \(k\)NN digraphs, On the KŁR conjecture in random graphs, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs, On limits of sparse random graphs, When does the K₄‐free process stop?, Subhypergraph counts in extremal and random hypergraphs and the fractional \(q\)-independence, On the variational problem for upper tails in sparse random graphs, CLT-related large deviation bounds based on Stein's method, Moment inequalities for functions of independent random variables, The lower tail: Poisson approximation revisited, On the missing log in upper tail estimates, Bivariate fluctuations for the number of arithmetic progressions in random sets, Sub-Gaussian Tails for the Number of Triangles inG(n, p), Many \(T\) copies in \(H\)-free graphs, A counterexample to the DeMarco‐Kahn upper tail conjecture, Vertex Ramsey properties of randomly perturbed graphs, Limit laws for the number of triangles in the generalized random graphs with random node weights, An introduction to large deviations for random graphs, Upper tail bounds for stars, Divide and conquer martingales and the number of triangles in a random graph, An improved upper bound on the density of universal random graphs, Regular graphs with many triangles are structured, A concentration result with application to subgraph count, On a Conjecture of Nagy on Extremal Densities, Rate of Convergence to the Poisson Law of the Numbers of Cycles in the Generalized Random Graphs, Tight upper tail bounds for cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• When are small subgraphs of a random graph normally distributed?
• Some intersection theorems for ordered sets and graphs
• On the number of subgraphs of prescribed type of graphs with a given number of edges
• On the number of copies of one hypergraph in another
• The number of large graphs with a positive density of triangles
• The deletion method for upper tail estimates
• Counting extensions
• On the Choice Number of Random Hypergraphs
• A sharp threshold for random graphs with a monochromatic triangle in every edge coloring
• Threshold functions for small subgraphs
• Poisson approximation for large deviations
• Random graphs with monochromatic triangles in every edge coloring
• Deviation inequality for monotonic Boolean functions with application to the number ofk-cycles in a random graph
• Divide and conquer martingales and the number of triangles in a random graph
• The infamous upper tail
• Threshold Functions for Ramsey Properties
• The strange logic of random graphs