Counting labeled triangle-free graphs on $n$ vertices

Question

Given $n$, the number of vertices, what is the number of labeled triangle-free graphs on $n$ vertices?

Answer 1

There shouldn't be any sensible exact formula, as Ira Gessel says. But there are very good asymptotics and a structural description.

An old result of Erdős, Kleitman and Rothschild is that almost all triangle-free graphs are bipartite. Proemel, Schickinger and Steger refined this to show that almost all triangle-free graphs which are not bipartite can be made bipartite by removing one edge; and almost all of the rest can be made bipartite by removing two edges; and so on.

It's easy to count bipartite graphs (there are roughly $2^{n+n^2/4}$; you can easily enough find accurate asymptotics which depend on the parity of $n$) and similarly the Proemel-Schickinger-Steger classes are not too hard to enumerate asymptotically (I don't know of these being explicitly in the literature).

There are also similar results if you fix the number of edges (which get less precise for sparse graphs).

Answer 2

user36212 has already essentially answered the question; the state of the art has not yet been pointed out though (by that I mean I miss a mention of the latest relevant publications, and a mention of the hypergraph container method, which the OP might find useful being told about) : due to work of Balogh and coworkers also for the class of maximal triangle-free graphs the asymptotics are known (and these differ from the asymptotics for all triangle-free graphs). In

[BP2014] József Balogh, Šárka Petříková, Number of maximal triangle-free graphs, Bull. London Math. Soc. 46(5) (2014), 1003-1006

it was shown that the lower bound of $2^{\frac18 n^2 + o(n^2)}$ for labelled maximal triangle-free graphs does give the correct asymptotics (to within this precision).

Incidentally, while [BP2014] avers without reference that the lower bound was "known much earlier", the first public reference seems to be this answer of Douglas Zare, which gives the a slighly more complicated construction than [BP2014], but in return gives a little more detail regarding the proof that the construction actually produces enough maximal triangle-free graphs. An exposition giving full detail does not exist as far as I know, though writing one would be easy: for the construction in [BP2014], that is, if one takes a pefect matching $M$ consisting of $n/4$ edges, and adds a new independent set $S$ of $n/2$ vertices, and then decides independently for each $(u,vw)\in S\times M$ whether to join $u$ to $v$ or to $w$ (and does exactly one of those), then evidently in the labelled sense precisely $2^{\frac{n}{2}\cdot\frac{n}{4}}=2^{n^2/8}$ are constructed, and what remains to be proved is that $2^{n^2/8 - r}$ with $r\in o(n^2)$ of those are maximal triangle-free; this is an exercise.

The proof of the upper bound in [BP2014] uses a result of Saxton and Thomason sometimes referred to a the method of hypergraph containers.

One should note that, in view of the results from the 1970s already mentioned by user36212, [JP2014] implies

$\text{# maximal triangle-free graphs}\qquad\sim_{n\to\infty}\qquad\sqrt{\text{# triangle free graphs}}$.

Even more recently, in

[BLPS2015] József Balogh, Hong Liu, Šárka Petříková, Maryam Sharifzadeh,

The Typical Structure of Maximal Triangle-Free Graphs,

Forum of Mathematics, Sigma (2015), Vol. 3, e20, 19 pages

two structural statements were proved, 'structural' in the sense that they shed some light on how most of the members of the set $\mathbb{K}$ of finite maximal triangle-free graphs 'look' like:

(0) Almost every member of $\mathbb{K}$ can be constructed according to what arguably is the most straighforward construction of a maximal triangle-free graph: to start with a perfect matching $M$, to add an independent set $S$, and then to add edges between $V(M)$ and $S$ until the graph is maximal-triangle free. (Evidently, not every member of $\mathbb{K}$ can be so constructed: e.g., the Petersen graph cannot.)

(1) By [BLPS2015, Lemma 2.4],

$\forall n\in\omega$ $\forall$ maximal triangle-free $n$-vertex graph $G$

($\#\text{maximal independent sets in $G$}$)

$\leq$

$2^{\frac12 n - \frac{1}{25}\text{number of vertex-disjoint three-vertex paths in $G$}}$

It seems not to be known whether there is any triangle-free graph for which the bound in the above lemma is attained.