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

Jozsef Balog, Wojciech Samotij

Research output: Contribution to journalArticle

Abstract

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
Volume24
Issue number3
DOIs
StatePublished - Oct 26 2010

Keywords

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

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Almost all C<sub>4</sub>-free graphs have fewer than (1 - ε)ex(n, C<sub>4</sub>) edges'. Together they form a unique fingerprint.

  • Cite this