Mantel's theorem for random graphs |
| |
| Authors: | B DeMarco J Kahn |
| |
| Affiliation: | Department of Mathematics, Rutgers University, Piscataway, New Jersey |
| |
| Abstract: | For a graph G, denote by t(G) (resp. b(G)) the maximum size of a triangle‐free (resp. bipartite) subgraph of G. Of course  for any G, and a classic result of Mantel from 1907 (the first case of Turán's Theorem) says that equality holds for complete graphs. A natural question, first considered by Babai, Simonovits and Spencer about 20 years ago is, when (i.e., for what p = p(n)) is the “Erd?s‐Rényi” random graph G = G(n,p) likely to satisfy t(G) = b(G)? We show that this is true if  for a suitable constant C, which is best possible up to the value of C. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 59–72, 2015 |
| |
| Keywords: | Mantel's theorem random graph threshold max cut |
|
|
