Seminars & Colloquia Calendar

Abstract: Erd?s-Kleitman-Rothschild proved that the number of triangle-free graphs on n vertices is asymptotic to the number of bipartite graphs; or in other words, a typical triangle-free graph is a random subgraph of a nearly balanced complete bipartite graph.  Osthus-Promel-Taraz extended this result to much lower densities: when m >(\sqrt{3}/4 +eps) n^{3/2} \sqrt{\log n}, a typical triangle-free graph with m edges is a random subgraph of size m from a nearly balanced complete bipartite graph (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, in which typical triangle-free graphs are not bipartite but do align closely with a nearly balanced bipartition.  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-colorable for q >=3, 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 Matthew Jenssen and Aditya Potukuchi.