Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

By Theorem 1 in the paper of Erdős, Kleitman, and Rothschild, the number of triangle-free graphs on $n$ vertices is $2^{n^2(1/4 +o(1)) }$. The number of bipartite graphs with a fixed pair of parts of size $n/2$ is $2^{n^2/4}$. Here is a construction of $2^{n^2(1/8 +o(1)) }$ maximum triangle-free graphs.

Suppose we start with a bipartite graph on two parts $A$ and $B$. We'll try to embed this in a maximal triangle-free graph with $2|A|+|B|$ vertices. For every vertex $a \in A$, add a vertex $a'$ connected to $a$ and every element of $B$ not connected to $a$. This graph is triangle-free, but not necessarily maximal.

Adding an edge between two elements of $A$ will form a triangle with any mutual neighbor in $B$. Such a mutual neighbor will exist for almost all bipartite graphs as long as $\log |A| \ll |B|$. Similarly, an edge between two elements of $B$ will form a triangle with any mutual neighbor in $A$, which will usually exist (proportion approaching $1$) if $\log |B| \ll |A|$.

Adding an edge between $a'$ and a neighbor $b$ of $a$ forms the triangle $a-b-a'$, as does adding an edge between $a$ and an element $b\in B$ initially not connected to $a$.

Adding an edge between $a_0'$ and $a_1 \in A$ will form a triangle as long as there is some $b\in B$ connected to $a_1$ but not $a_0$. Again, this happens with a proportion approaching $1$ if $\log|A| \ll |B|$.

By the way, it's not a problem if you can add more edges between $a_0'$ and elements of $A$. If you can, do so. The important thing is that we ensured that no edges between elements of $A \cup B$ can be added without forming triangles, and we did so by adding a small number of vertices.

Adding edges between the added vertices might or might not form triangles. Add enough edges to make the graph maximal. Assuming the high-proportion conditions are satisfied, there is at least one maximal graph so that the induced subgraph on $A \cup B$ is the original bipartite graph.

Choose $|B| = 2|A|$. As $|A| \to \infty$, a proportion approaching $1$ of these bipartite graphs can be embedded in a maximal triangle-free graph on $4|A|$ vertices. This constructs $2^{n^2(1/8 + o(1))}$ maximal triangle-free graphs on $n$ vertices, or roughly the square root of the total number of triangle-free graphs.

This question was recently solved by Balogh & Petrickova. Douglas Zare's bound is tight (apart from the $o(1)$ term). See http://arxiv.org/abs/1409.8123