Almost all C4-free graphs have fewer than (1 - ε)ex(n, C4) edges

Jozsef Balog, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review


A graph is called H-free if it contains no copy o f H. Let ex(n, H) denote the Turán number for H, i.e., the maximum number of edges that an n-vertex H-free graph may have. An old result of Kleitman and Winston states that there are 2o(ex(n,C4)) C4-free graphs on n vertices. Füredi showed that almost all C4-free graphs of order n have at least cex(n, C4) edges for some positive constant c. We prove that there is a positive constant e such that almost all C 4-free graphs have at most (1 - ε) ex(n, C4) edges. This resolves a conjecture of Balogh, Bollobás, and Simonovits for the 4-cycle.

Original languageEnglish (US)
Pages (from-to)1011-1018
Number of pages8
JournalSIAM Journal on Discrete Mathematics
Issue number3
StatePublished - Oct 26 2010


  • Asymptotic graph enumeration
  • Asymptotic graph structure
  • C-free
  • Extremal graphs
  • Turán's problem

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Almost all C4-free graphs have fewer than (1 - ε)ex(n, C4) edges'. Together they form a unique fingerprint.

Cite this