Počet záznamů: 1
A counterexample to the DeMarco-Kahn Upper Tail Conjecture
- 1.
SYSNO ASEP 0505189 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A counterexample to the DeMarco-Kahn Upper Tail Conjecture Tvůrce(i) Šileikis, Matas (UIVT-O) RID, ORCID, SAI
Warnke, L. (US)Zdroj.dok. Random Structures and Algorithms. - : Wiley - ISSN 1042-9832
Roč. 55, č. 4 (2019), s. 775-794Poč.str. 20 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova concentration inequalities ; large deviations ; random graphs ; subgraph counts ; upper tail Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics CEP GJ16-07822Y GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora UIVT-O - RVO:67985807 UT WOS 000491480300001 EID SCOPUS 85066469003 DOI 10.1002/rsa.20859 Anotace 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. Pracoviště Ústav informatiky Kontakt Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Rok sběru 2020 Elektronická adresa http://dx.doi.org/10.1002/rsa.20859
Počet záznamů: 1