Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

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.

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.