Number of the records: 1  

A counterexample to the DeMarco-Kahn Upper Tail Conjecture

  1. 1.
    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

    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:

    0505189-afin.pdf11549.6 KBPublisher’s postprintrequire
Number of the records: 1