DIMACS - Graduate Student Combinatorics Seminar

Title: Upper Tails for Triangles

Speaker: Robert DeMarco, Rutgers University

Date: Wednesday, October 20, 2010 12:10pm

Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ


Let ξn,p be the number of copies of K3 (triangles) in G(n,p). I will discuss various methods that have been used to bound the upper tail of this random variable, meaning to bound

Pr( ξn,p > (1+ε) En,p] ).

The last method discussed will be the one developed by myself and Professor Kahn to find an upper bound that is tight up to a constant factor in the exponent for all values of p. If time permits, I will briefly discuss extensions of this final method to the general clique case.