A counterexample to the DeMarco-Kahn Upper Tail Conjecture

Abstract

Given a fixed graph H, what is the (exponentially small) probability that the number X_H of copies of H in the binomial random graph G_{n,p} is at least twice its mean? Studied intensively since the mid 1990s, this so-called infamous upper tail problem remains a challenging testbed for concentration inequalities. In 2011 DeMarco and Kahn formulated an intriguing conjecture about the exponential rate of decay of \Pr(X_H \ge (1+ε) \E X_H) for fixed ε>0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.

arXiv comment15 pages; minor edits; to appear in Random Structures and Algorithms (RSA)

References in corpus (9)

• Upper tails for triangles
• Upper tails and independence polynomials in random graphs
• On the variational problem for upper tails in sparse random graphs
• Upper Tails for Cliques
• Upper tails for arithmetic progressions in random subsets
• The lower tail: Poisson approximation revisited
• The Janson inequalities for general up-sets
• Upper tail bounds for Stars
• Counting extensions revisited

Cited by in corpus (7)

• Nonlinear large deviation bounds with applications to traces of Wigner matrices and cycles counts in Erdös-Renyi graphs
• On the missing log in upper tail estimates
• Upper tail bounds for Stars
• Counting extensions revisited
• Bounds on Ramsey Games via Alterations
• Upper Tails of Subgraph Counts in Sparse Regular Graphs
• A large deviation principle for block models