Richard P. Stanley Seminar in Combinatorics: Will Perkins (Georgia Tech)

Building 2, Room 139

Speaker: Will Perkins (Georgia Tech)Title: On the evolution of structure in triangle-free graphsAbstract: Erdos-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. Joint work with Matthew Jenssen and Aditya Potukuchi.