The typical structure of maximal triangle-free graphs

DOI10.1017/FMS.2015.22MaRDI QIDQ3449989zbMATH OpenOpenAlexFDO

Authors József Balogh, Hong Liu, Šárka Petříčková, Maryam Sharifzadeh

Publication date 2 November 2015

Published in Forum of Mathematics, Sigma (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1501.02849

zbMATH Keywords

hypergraphsstructure of independent sets

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Recently, settling a question of ErdH{o}s, Balogh and Petv{r}'{i}v{c}kov'{a} showed that there are at most $2^{n^2/8+o(n^2)}$ $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 $XcupY$ such that $G[X]$ is a perfect matching and $Y$ is an independent set. Our proof uses the Ruzsa-Szemer'{e}di removal lemma, the ErdH{o}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 $P_3$'s, which is of independent interest.

Recommendations

• The number of the maximal triangle-free graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• A note on triangle-free and bipartite graphs
• On the structure of clique-free graphs
• On the Structure of Dense Triangle-Free Graphs

Cites work

• A Szemerédi-type regularity lemma in abelian groups, with applications
• Almost all triple systems with independent neighborhoods are semi-bipartite
• Counting sum-free sets in abelian groups
• Excluding induced subgraphs: critical graphs
• For which densities are random triangle-free graphs almost surely bipartite?
• Hypergraph containers
• Independent sets in hypergraphs
• Intersecting families of discrete structures are typically trivial
• On cliques in graphs
• The asymptotic number of graphs not containing a fixed color-critical subgraph
• The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
• The number of maximal independent sets in connected graphs
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of maximal sum-free subsets of integers
• The number of the maximal triangle-free graphs
• The typical structure of graphs without given excluded subgraphs

Cited in

(10)

• Structure and enumeration theorems for hereditary properties in finite relational languages
• Integer colorings with no rainbow 3-term arithmetic progression
• On the Ramsey-Turán density of triangles
• On solution-free sets of integers
• The number of the maximal triangle-free graphs
• A sharp bound on the number of maximal sum-free sets
• On maximal triangle‐free graphs
• The number of maximum primitive sets of integers
• The exponential growth of the packing chromatic number of iterated Mycielskians
• The typical structure of graphs with no large cliques

This page was built for publication: The typical structure of maximal triangle-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449989)