Proposed topics for student talks in the Mittagsseminar

For more information, visit the Mittagsseminar website.

A counterexample to the DeMarco-Kahn Upper Tail Conjecture

Matas Šileikis and Lutz Warnke, A counterexample to the DeMarco-Kahn Upper Tail Conjecture, arXiv preprint arXiv:1809.09595, 2018.

Given a fixed graph H, what is the probability that the number of copies of H in the binomial random graph G(n, p) is at least twice its mean? This intensively studied upper tail problem remains a challenge for researchers still. DeMarco and Kahn proposed a conjecture in 2011 about the exponential rate of decay of the probability above. However, in this manuscript the authors give a surprisingly simple counterexample to the conjecture of DeMarco and Kahn as well as several extensions and generalisations.

Contact: Miloš Trujić, mtrujic@inf.ethz.ch, CAB G 33.2