Mantel's theorem for random graphs
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 Turn'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-Rnyi 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, 5972, 2015
mantel's theorem random graph threshold max cut