A counterexample to the DeMarco‐Kahn upper tail conjecture. Issue 4 (14th June 2019)

• Record Type: Journal Article
• Authors: Šileikis, Matas; Warnke, Lutz
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 775
• Page End: 794
• Publication Date: 2019-06-14
• Subjects: concentration inequalities -- large deviations -- random graphs -- subgraph counts -- upper tail; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20859
• Languages: English
• ISSNs: 1042-9832

Abstract

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 P ( X H ⩾ ( 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.