MATH Seminar

Title: On the evolution of structure in triangle-free graphs
Seminar: Discrete Analysis
Speaker: Will Perkins of Georgia Tech
Contact: Cosmin Pohoata, cosmin.pohoata@emory.edu
Date: 2024-02-19 at 5:30PM
Venue: MSC W301
Download Flyer
Abstract: 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.