## 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 2^{o(ex(n,C4))} C_{4}-free graphs on n vertices. Füredi showed that almost all C_{4}-free graphs of order n have at least cex(n, C_{4}) 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, C_{4}) edges. This resolves a conjecture of Balogh, Bollobás, and Simonovits for the 4-cycle.

Original language | English (US) |
---|---|

Pages (from-to) | 1011-1018 |

Number of pages | 8 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 24 |

Issue number | 3 |

DOIs | |

State | Published - 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_{4}-free graphs have fewer than (1 - ε)ex(n, C

_{4}) edges'. Together they form a unique fingerprint.