The typical structure of graphs with no large cliques

József Balogh, Neal Bushaw, Maurício Collares, Hong Liu, Robert Morris, Maryam Sharifzadeh

Research output: Contribution to journalArticlepeer-review


In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex Kr+1-free graph is r-partite. In this paper we extend this result to all functions r = r(n) with r ⩽ (logn)1/4. The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits.

Original languageEnglish (US)
Pages (from-to)617-632
Number of pages16
Issue number4
StatePublished - Aug 1 2017


  • 05C30
  • 05C35
  • 05C75
  • 05D40

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics


Dive into the research topics of 'The typical structure of graphs with no large cliques'. Together they form a unique fingerprint.

Cite this