A counterexample to the DeMarco-Kahn Upper Tail Conjecture
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F19%3A00505189" target="_blank" >RIV/67985807:_____/19:00505189 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1002/rsa.20859" target="_blank" >http://dx.doi.org/10.1002/rsa.20859</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1002/rsa.20859" target="_blank" >10.1002/rsa.20859</a>
Alternative languages
Result language
angličtina
Original language name
A counterexample to the DeMarco-Kahn Upper Tail Conjecture
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
<a href="/en/project/GJ16-07822Y" target="_blank" >GJ16-07822Y: Extremal graph theory and applications</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Random Structures and Algorithms
ISSN
1042-9832
e-ISSN
—
Volume of the periodical
55
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
20
Pages from-to
775-794
UT code for WoS article
000491480300001
EID of the result in the Scopus database
2-s2.0-85066469003