The number of the maximal triangle-free graphs

Abstract

Paul Erdős suggested the following problem: Determine or estimate the number of maximal triangle-free graphs on $n$ vertices. Here we show that the number of maximal triangle-free graphs is at most $2^{n^2/8+o(n^2)}$, which matches the previously known lower bound. Our proof uses among others the Ruzsa-Szemerédi triangle removal lemma, and recent results on characterizing of the structure of independent sets in hypergraphs.

7 pages. This article is slightly different from the journal version, as it contains comments on more recent developments

References in corpus (1)

• The number of maximal sum-free subsets of integers

Cited by in corpus (1)

• The number of maximal sum-free subsets of integers