18
$\begingroup$

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?

$\endgroup$
26
  • 1
    $\begingroup$ According to E-K-R theorem from the above link, the bulk of all triangle-free graphs consists of the bipartite graphs. Perhaps it's worthwhile to check if something similar is true in the case of maximal triangle-free graphs. If these were true then the number of maximal bipartite graphs would give a good lower bound which would be $2^{n-1}-1$. And thank you, Rupei Xu, for the confirmation about maximal versus all. $\endgroup$ Mar 14, 2014 at 3:46
  • 1
    $\begingroup$ @Wlodzimierz Holsztynski, the maximal here means if you add one more edge, it will form a triangle. $\endgroup$
    – user39815
    Mar 14, 2014 at 3:55
  • 2
    $\begingroup$ @Gerry : 1,1,3,7,27,211,1743,15247,219747,5379451, 154297863,5085738967,225515577147 . I'm using that "maximal triangle-free" is the same as "triangle-free and diameter 2", at least for $n\ge 3$. $\endgroup$ Mar 17, 2014 at 10:23
  • 3
    $\begingroup$ Yes. If the diameter is 1, it is a complete graph. If the diameter is 2, any non-adjacent vertices have distance 2 so adding an edge makes a triangle. If the diameter is 3 or more, you can add an edge between two vertices at distance 3 or more without making a triangle. $\endgroup$ Mar 17, 2014 at 11:23
  • 1
    $\begingroup$ @Gerry : for $n=14$ the count is 14272681411171. Note that these are labelled graphs; there are only 1274 unlabelled graphs in this class out of 467871369 unlabelled triangle-free graphs altogether. It took about an hour, so a few larger sizes could be done. It might be possible to make a special generator for these and go quite a lot further. $\endgroup$ Mar 17, 2014 at 11:54

2 Answers 2

8
+50
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is this bound tight? There may be many different kind of maximal triangle free graphs. $\endgroup$
    – user39815
    Mar 17, 2014 at 8:25
  • $\begingroup$ @Rupei Xu: It's just a lower bound of the same general shape as the upper bound, but I don't know whether the $1/8$ factor is tight. $\endgroup$ Mar 17, 2014 at 13:04
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ They refer to this question for the lower bound but claim without reference that it was known earlier. I still haven't found any earlier reference. $\endgroup$ Feb 28, 2016 at 14:37
  • $\begingroup$ Well, let me offer $107 for an earlier reference since Erdős is 107 years old now. If nobody claims it until the end of this year, maybe I should mail it to Douglas Zare. $\endgroup$
    – user39815
    Aug 21, 2019 at 7:19
  • $\begingroup$ After showing Balogh the lower bound in Erdős 101 conference, Balogh quickly gave a proof of the matching upper bound in the next coffee break(amazing!). However, in his formal published paper, he mentioned the lower bound was known much earlier. Some readers emailed me to ask for more details after reading his paper. Jozsi Balogh said Jacob Fox and Tomasz Luczak told him they knew this construction for a long time. Paul Horn told me he had this bound in 2011 when he was in Emory and talked it to Jacob Fox at MIT in 2011 and 2012, he also discussed it with several other people including Rodl. $\endgroup$
    – user39815
    Aug 23, 2019 at 0:54
  • 1
    $\begingroup$ In 2014, after a lot of email exchanges, I wrote a paper together with McKay and Zare towards this topic(but didn't publish it), but the main focus was for exact enumeration of the number of maximal triangle-free graphs and applied it to Triangle Ramsey Number. Zare did the independent work for the lower bound without knowing any previous results. Only recently, I know the whole story. Hope those comments can clear the doubts of readers. $\endgroup$
    – user39815
    Aug 23, 2019 at 1:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.