TY - JOUR

T1 - The typical structure of maximal triangle-free graphs

AU - Balogh, József

AU - Liu, Hong

AU - Petv ri v cková, v Sárka

AU - Sharifzadeh, Maryam

N1 - Funding Information:
The authors would like to thank the anonymous referee for useful comments and suggestions, particularly on the simplification of the proof of Lemma 4.5. The first author's research is partially supported by a Simons Fellowship, NSF CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763, and Arnold O. Beckmann Research Award RB15006.
Publisher Copyright:
© 2015 The Author(s).

PY - 2015

Y1 - 2015

N2 - 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
3s, which is of independent interest.

AB - 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
3s, which is of independent interest.

UR - http://www.scopus.com/inward/record.url?scp=85029035659&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029035659&partnerID=8YFLogxK

U2 - 10.1017/fms.2015.22

DO - 10.1017/fms.2015.22

M3 - Article

VL - 3

SP - e20, 19

JO - Forum of Mathematics, Pi

JF - Forum of Mathematics, Pi

SN - 2050-5094

M1 - e20

ER -