Abstract

Erdős, Kleitman and Rothschild proved that the number of triangle-free graphs on n vertices is asymptotically the same as the number of bipartite graphs; or in other words, a typical triangle-free graph is bipartite. Osthus, Promel and Taraz proved a sparse analogue of this result: if m > (\sqrt{3}/4 +\epsilon) n^{3/2} \sqrt{\log n}, a typical triangle-free graph on n vertices with m edges is bipartite (and this no longer holds below this threshold). What do typical triangle-free graphs at sparser densities look like and how many of them are there? We consider what we call the ordered regime, where typical triangle-free graphs are not bipartite but have a dense max-cut. In this regime we prove asymptotic formulas for the number of triangle-free graphs and give a precise probabilistic description of their structure. This leads to further results such as determining the threshold at which typical triangle-free graphs are q-colourable for q > 2, determining the threshold for the emergence of a giant component in the complement of a max-cut, and many others. This is joint work with Will Perkins and Aditya Potukuchi.