## Abstract

Two central topics of study in combinatorics are the so-called evolution of random graphs, introduced by the seminal work of Erdős and Rényi, and the family of H-free graphs, that is, graphs which do not contain a subgraph isomorphic to a given (usually small) graph H. A widely studied problem that lies at the interface of these two areas is that of determining how the structure of a typical H-free graph with n vertices and m edges changes as m grows from 0 to ex(n, H). In this paper, we resolve this problem in the case when H is a clique, extending a classical result of Kolaitis, Prömel, and Rothschild. In particular, we prove that for every r ≥ 2 there is an explicit constant θ_{γ} such that, letting (Formula Precented) the following holds for every positive constant ε. If m ≥ (1 + ε)m_{γ} then almost all K_{γ+1}-free n-vertex graphs with m edges are γ-partite, whereas if n ≪ m ≼ (1 + ε)m_{γ} then almost all of them are not γ-partite.

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

Pages (from-to) | 6439-6485 |

Number of pages | 47 |

Journal | Transactions of the American Mathematical Society |

Volume | 368 |

Issue number | 9 |

DOIs | |

State | Published - 2016 |

## ASJC Scopus subject areas

- General Mathematics
- Applied Mathematics

## Fingerprint

Dive into the research topics of 'The typical structure of sparse k_{r+1}-free graphs'. Together they form a unique fingerprint.