Turan's theorem for random graphs

Turan's theorem for random graphs

-
Jeff Kahn, Rutgers University
Fine Hall 224

PLEASE NOTE DIFFERENT TIME.  CLICK ON SEMINAR TITLE FOR COMPLETE ABSTRACT.   Write t_r(G) (resp. b_r(G)) for the maximum size of a K_r-free (resp. (r-1)-partite) subgraph of a graph G. Of course t_r(G) is at least b_r(G) for any G, while Turan's Theorem (or Mantel's Theorem if r = 3) says that equality holds if G = K_n.  We are interested in a question first considered by Babai, Simonovits and Spencer about 25 years ago: for what p=p(n) is it true that t_r(G_{n,p}) = b_r(G_{n,p})  w.h.p.? (Here G_{n,p} is the usual ``binomial" random graph and an event holds ``w.h.p.'' if its probability tends to 1 as n tends to infinity.) Less precise versions of this have been the subject of intense efforts over the last decade or two and, more recently, of some spectacular successes, though this work seems largely orthogonal to the problem under discussion.  The theorem of the title proves the natural guess that the ``threshold" function p(n) for equality to hold is the same as that for the property that every edge lies in a copy of $K_r$. More precisely: For each fixed r there is a C such that if p > Cn^{-\tfrac{2}{r+1}}\log^{\tfrac{2}{(r+1)(r-2)}}n, then w.h.p. every maximum K_r-free subgraph of G_{n,p} is (r-1)-partite.   I will say a little about some of these developments and maybe about some of the difficulties presented by the above theorem.  Joint with Bobby DeMarco.