TY - JOUR
T1 - Extremal subgraphs of random graphs
AU - Babai, László
AU - Simonovits, Miklós
AU - Spencer, Joel
PY - 1990/11
Y1 - 1990/11
N2 - We shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and —Rn is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bn is a bipartite subgraph of Rn of maximum size, —Fn is an L‐free subgraph of Rn of maximum size, then (in some sense) Fn and Bn are very near to each other: almost surely they have almost the same number of edges, and one can delete Op(1) edges from Fn to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fn is almost surely bipartite.
AB - We shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and —Rn is a random graph on n vertices, whose edges are chosen independently, with probability p, and —Bn is a bipartite subgraph of Rn of maximum size, —Fn is an L‐free subgraph of Rn of maximum size, then (in some sense) Fn and Bn are very near to each other: almost surely they have almost the same number of edges, and one can delete Op(1) edges from Fn to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, Fn is almost surely bipartite.
UR - http://www.scopus.com/inward/record.url?scp=84986469590&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84986469590&partnerID=8YFLogxK
U2 - 10.1002/jgt.3190140511
DO - 10.1002/jgt.3190140511
M3 - Article
AN - SCOPUS:84986469590
SN - 0364-9024
VL - 14
SP - 599
EP - 622
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 5
ER -