On the upper tail of subgraph counts

Prelegent(ci)

Matas Šileikis

Afiliacja

UAM

Termin

17 maja 2012 12:15

Pokój

p. 3260

Seminarium

Seminarium Zakładu Rachunku Prawdopodobieństwa

---

Let G(n,p) be the (binomial) random subgraph of the complete graph on n vertices, every edge being included independently with probability p. Given a fixed graph H, let X be the number of copies of H in G(n,p). It is known that X is sharply concentrated around its expectation EX. Optimal bounds for the lower tail P(X < tEX), 0 < t < 1, were determined by Janson in 1990. For the upper tail P(X > tEX), t >1, "almost" optimal bounds were determined by Janson, Oleszkiewicz and Rucinski only in 2004. These bounds differ by a factor log 1/p in the exponent. We discuss recent progress that has been made in an attempt to remove this logarithmic term.

---