pith. sign in

arxiv: 1206.1016 · v1 · pith:YXARJWFDnew · submitted 2012-06-05 · 🧮 math.PR · cs.DM· math.CO

Mantel's Theorem for random graphs

classification 🧮 math.PR cs.DMmath.CO
keywords firstgraphgraphsmantelrandomresptheorembabai
0
0 comments X
read the original 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 $t(G) \geq b(G)$ for any $G$, and a classic result of Mantel from 1907 (the first case of Tur\'an'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\H{o}s-R\'enyi" random graph $G=G(n,p)$ likely to satisfy $t(G) = b(G)$? We show 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.