Triangle-free graphs on a set $V$ of $n$ labeled vertices

67 Views Asked by At

Prove that the number of triangle-free graphs on a set $V$ of $n$ labeled vertices is $2^{(\frac{1}{4} + o(1))n^2}$ where the $o(1)$ term tends to $0$ as $n \to \infty$.

I have a few ideas, but not sure how to proceed. We know that by Erdös-Stone-Simonovits Theorem, for fixed graph $H$ with chromatic number $\chi(H) = 3$, the maximum possible number of edges in an $H$-free simple graph on $n$ vertices, which we will denote as $\phi(n,H)$, satisfies $\phi(n,H) = \frac{1}{4} + o(1))n^2$. If we let $H$ be a triangle ($\chi(H) = 3$), we then know that $\phi(n,H) = \frac{1}{4} + o(1))n^2$ is the maximum number of edges, but how do I proceed from here? Is there some sort of counting argument to relate the maximum possible number of edges to the number of triangle-free graphs?