Computer Science/Discrete Mathematics Seminar I

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 (i.e. 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 this is true if $p > Cn^{-1/2}\log^{1/2}(n)$ for a suitable constant $C$, which is best possible up to the value of $C$. (Joint with Bobby DeMarco.)