Premium
Mantel's theorem for random graphs
Author(s) -
DeMarco B.,
Kahn J.
Publication year - 2015
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20535
Subject(s) - mathematics , combinatorics , bipartite graph , robertson–seymour theorem , random graph , discrete mathematics , graph , line graph , pathwidth
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 / 2log 1 / 2 n 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