Determine or estimate the number of maximal triangle-free graphs on $n$ vertices Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/newproblems/NumberOfTriangleFreeGraphs.html
Open Problem: Determine or estimate the number of maximal triangle-free graphs
on $n$ vertices.
Is any one working on this problem? Any known related results? 
Now I am considering about using a "connection game" method to solve this problem: Given a set of $n$ players, each one chooses to connect to other nodes, if any two neighbors of it connect a new edge(which means there would form a triangle), it has to choose delete either edges with those two neighbors. Then the question is how many different topology connections does it have? 
Any comments on this method? 
 A: 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.
A: 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
