Premium
Extremal subgraphs of random graphs
Author(s) -
Babai László,
Simonovits Miklós,
Spencer Joel
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140511
Subject(s) - combinatorics , mathematics , bipartite graph , complete bipartite graph , graph , random graph , induced subgraph , discrete mathematics , vertex (graph theory)
We shall prove that if L is a 3‐chromatic (so called “forbidden”) graph, and — R n is a random graph on n vertices, whose edges are chosen independently, with probability p , and — B n is a bipartite subgraph of R n of maximum size, — F n is an L ‐free subgraph of R n of maximum size, then (in some sense) F n and B n are very near to each other: almost surely they have almost the same number of edges, and one can delete O p (1) edges from F n to obtain a bipartite graph. Moreover, with p = 1/2 and L any odd cycle, F n is almost surely bipartite.