## Abstract

Recently, settling a question of Erdos, Balogh, and Petřríčková showed that there are at most 2
^{n2/8+o(n2)} n-vertex maximal triangle-free graphs, matching the previously known lower bound. Here, we characterize the typical structure of maximal triangle-free graphs. We show that almost every maximal triangle-free graph G admits a vertex partition X ∪ Y such that GTXU is a perfect matching and Y is an independent set. Our proof uses the Ruzsa-Szemerédi removal lemma, the Erdos-Simonovits stability theorem, and recent results of Balogh, Morris, and Samotij and Saxton and Thomason on characterization of the structure of independent sets in hypergraphs. The proof also relies on a new bound on the number of maximal independent sets in triangle-free graphs with many vertex-disjoint P
_{3}s, which is of independent interest.

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

Article number | e20 |

Pages (from-to) | e20, 19 |

Journal | Forum Math. Sigma |

Volume | 3 |

DOIs | |

State | Published - 2015 |

## ASJC Scopus subject areas

- Analysis
- Theoretical Computer Science
- Algebra and Number Theory
- Statistics and Probability
- Mathematical Physics
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Mathematics