Extremal subgraphs of random graphs

László Babai, Miklós Simonovits, Joel Spencer

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)599-622
Number of pages24
JournalJournal of Graph Theory
Volume14
Issue number5
DOIs
StatePublished - Nov 1990

ASJC Scopus subject areas

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Extremal subgraphs of random graphs'. Together they form a unique fingerprint.

Cite this