2015/01/12 by József Balogh, Hong Liu, Balogh, József +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1501.02849
17 pages
arxiv created 2015/01/12 · arxiv updated 2016/08/07
Recently, settling a question of Erdős, Balogh and Petříčková showed that there are at most 2n2/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 G[X] is a perfect matching and Y is an independent set. Our proof uses the Ruzsa-Szemerédi removal lemma, the Erdős-Simonovits stability theorem, and recent results of Balogh-Morris-Samotij and Saxton-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 P3's, which is of independent interest.