Number of the records: 1
A counterexample to the DeMarco-Kahn Upper Tail Conjecture
- 1.
SYSNO ASEP 0505189 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title A counterexample to the DeMarco-Kahn Upper Tail Conjecture Author(s) Šileikis, Matas (UIVT-O) RID, ORCID, SAI
Warnke, L. (US)Source Title Random Structures and Algorithms. - : Wiley - ISSN 1042-9832
Roč. 55, č. 4 (2019), s. 775-794Number of pages 20 s. Language eng - English Country US - United States Keywords concentration inequalities ; large deviations ; random graphs ; subgraph counts ; upper tail Subject RIV BA - General Mathematics OECD category Pure mathematics R&D Projects GJ16-07822Y GA ČR - Czech Science Foundation (CSF) Method of publishing Limited access Institutional support UIVT-O - RVO:67985807 UT WOS 000491480300001 EID SCOPUS 85066469003 DOI 10.1002/rsa.20859 Annotation 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. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2020 Electronic address http://dx.doi.org/10.1002/rsa.20859
Number of the records: 1