Title: Mantel's Theorem for random graphs
Speaker: Bobby DeMarco, Rutgers University
Date: Tuesday, October 4, 2011 2:00pm
Location: Hill Center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
For a graph G, let t(G) (resp. b(G)) denote the maximum size of a triangle-free (resp. bipartite) subgraph of G. Of course t(G) geq b(G) for any G, and a classic result of Mantel from 1907 (the first case of Turan's Theorem) says t(K_n)=b(K_n) (where K_n is the complete graph on n vertices). A natural question first considered by Babai, Simonovits and Spencer about 20 years ago is, when does equality hold for a random graph? That is, for what p=p(n) is the Erdos-Renyi random graph G=G(n,p) likely to satisfy t(G) = b(G)? We show that that this is true if p>C n^{-1/2} log^{1/2}(n) for a suitable constant C, which is best possible up to the value of C. (Joint with Jeff Kahn)
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math