On the upper tail of subgraph counts

Speaker(s)

Matas Šileikis

Affiliation

UAM

Date

May 17, 2012, 12:15 p.m.

Room

room 3260

Seminar

Seminar of Probability Group

---

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.

---