A counterexample to the DeMarco‐Kahn upper tail conjecture. Issue 4 (14th June 2019) - Šileikis, Matas; Warnke, Lutz
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.