Mantel's theorem for random graphs1. Issue 1 (28th March 2014) - DeMarco, B.; Kahn, J.
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqk94h" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />t(G)≥b(G)</alternatives> 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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj14cqk91v" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />p>Cn−1/2log⁡1/2n</alternatives> 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