Počet záznamů: 1
A counterexample to the DeMarco-Kahn Upper Tail Conjecture
- 1.0505189 - ÚI 2020 RIV US eng J - Článek v odborném periodiku
Š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
Grant CEP: GA ČR GJ16-07822Y
Institucionální podpora: RVO:67985807
Klíčová slova: concentration inequalities * large deviations * random graphs * subgraph counts * upper tail
Obor OECD: Pure mathematics
Impakt faktor: 1.047, rok: 2019
Způsob publikování: Omezený přístup
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.
Trvalý link: http://hdl.handle.net/11104/0296681
Název souboru Staženo Velikost Komentář Verze Přístup 0505189-afin.pdf 13 549.6 KB Vydavatelský postprint vyžádat
Počet záznamů: 1