Mantel's Theorem for random graphs

2012/06/05 by Bobby DeMarco, Jeff Kahn, DeMarco, Bobby +1 · 2 citations
Computer Science · Mathematics · #05C35 #05C80 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1206.1016

openalex publication_date 2012/06/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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) ≥ b(G) 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 p>C n^-1/2 log^1/2n for a suitable constant C, which is best possible up to the value of C.

Cited by

• On the stability of the Erdős-Ko-Rado theorem
• When does a tree activate the random graph?

Related

• Turán's Theorem for random graphs
• Sabotage the Mantel Theorem
• Mantel's Theorem for Random Hypergraphs
• An analogue of the Erdős-Gallai theorem for random graphs
• Triangle-free subgraphs of random graphs