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+ε) E[ξn,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.