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

Abstract:

Let ξ_{n,p} be the number of copies of K_{3} (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.