A counterexample to the DeMarco-Kahn Upper Tail Conjecture

0505189 - ÚI 2020 RIV US eng J - Journal Article
Šileikis, Matas - Warnke, L.
A counterexample to the DeMarco-Kahn Upper Tail Conjecture.
Random Structures and Algorithms. Roč. 55, č. 4 (2019), s. 775-794. ISSN 1042-9832. E-ISSN 1098-2418
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : concentration inequalities * large deviations * random graphs * subgraph counts * upper tail
OECD category: Pure mathematics
Impact factor: 1.047, year: 2019
Method of publishing: Limited access
http://dx.doi.org/10.1002/rsa.20859

Given a fixed graph H, what is the (exponentially small) probability that the number XH of copies of H in the binomial random graph Gn,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 urn:x-wiley:rsa:media:rsa20859:rsa20859-math-0001 for fixed ε > 0. We show that this upper tail conjecture is false, by exhibiting an infinite family of graphs violating the conjectured bound.
Permanent Link: http://hdl.handle.net/11104/0296681