7
$\begingroup$

Given $n$, the number of vertices, what is the number of triangle-free simple graphs on $n$ vertices (or asymptotically)?

A more difficult problem is, given $n$, $m$, what is the number of triangle-free simple graphs on $n$ vertices with $\le m$ edges (or asymptotically)?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
12
$\begingroup$

Next terms are 581460254001, 31720840164950 (sent to OEIS). All these numbers were found by exhaustive enumeration. As far as I know, the theoretic enumeration problem is unsolved, even for labelled graphs.

As for asymptotics, it is an old result of Erdős, Kleitman and Rothschild that almost all triangle-free graphs are bipartite. Someone studied the case of restricted numbers of edges see http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-0118(199602)21:2%3C137::AID-JGT3%3E3.0.CO;2-S/abstract .

Improve this answer
$\endgroup$
6
$\begingroup$

Computing the first terms in sage and searching in OEIS gave A006785 Triangle-free graphs on n vertices

The first terms are:

1, 2, 3, 7, 14, 38, 107, 410, 1897, 12172, 105071, 1262180, 20797002, 467871369, 14232552452

There is no formula in OEIS, some of the referenced papers might be useful.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .