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 journalArticle


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

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

  • Cite this

    Balogh, J., Bushaw, N., Collares, M., Liu, H., Morris, R., & Sharifzadeh, M. (2017). The typical structure of graphs with no large cliques. Combinatorica, 37(4), 617-632.