Richard P. Stanley Seminar in Combinatorics: On the evolution of structure in triangle-free graphs

SEMINARS, HARVARD-MIT COMBINATORICS

Speaker:

Will Perkins - Georgia Tech

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.

===============================

For more info, see https://math.mit.edu/combin/