Seminars & Colloquia Calendar
On the evolution of triangle-free graphs in the ordered regime
Will Perkins (Georgia Tech)
Location: Hill Center Room 705
Date & time: Monday, 27 February 2023 at 2:00PM - 3:00PM
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.