A counterexample to the DeMarco‐Kahn upper tail conjecture

DOI10.1002/rsa.20859zbMath1433.05285arXiv1809.09595OpenAlexW2893988561WikidataQ122898101 ScholiaQ122898101MaRDI QIDQ5216176

Matas Šileikis, Lutz Warnke

Publication date: 14 February 2020

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

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

zbMATH Keywords

random graphslarge deviationsconcentration inequalitiessubgraph countsupper tail

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30)

Related Items

Upper tails via high moments and entropic stability, Large deviation for uniform graphs with given degrees, Counting extensions revisited, Bounds on Ramsey games via alterations, 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, Nonlinear large deviation bounds with applications to Wigner matrices and sparse Erdős-Rényi graphs, On the missing log in upper tail estimates, Upper tail bounds for stars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the upper tail of counts of strictly balanced subgraphs
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• The large deviation principle for the Erdős-Rényi random graph
• Poisson convergence and Poisson processes with applications to random graphs
• Gaussian-width gradient complexity, reverse log-Sobolev inequalities and nonlinear large deviations
• Upper tails for arithmetic progressions in random subsets
• Upper tails for subgraph counts in random graphs
• On the missing log in upper tail estimates
• Upper tails and independence polynomials in random graphs
• The deletion method for upper tail estimates
• Nonlinear large deviations
• On the Choice Number of Random Hypergraphs
• The lower tail: Poisson approximation revisited
• The missing log in large deviations for triangle counts
• Upper tails for triangles
• Introduction to Random Graphs
• Tight upper tail bounds for cliques
• Threshold functions for small subgraphs
• Poisson approximation for large deviations
• Random graphs with monochromatic triangles in every edge coloring
• On the concentration of multivariate polynomials with small expectation
• Concentration of non‐Lipschitz functions and applications
• The infamous upper tail
• The Janson inequalities for general up‐sets
• On the variational problem for upper tails in sparse random graphs