Oct 21 2024

Combinatorics and Discrete Probability Seminar: 3-colorability of triangle-free graphs, by Clayton Mizgerd

October 21, 2024

3:00 PM - 3:50 PM

Location

1227 SEO

Address

Chicago, IL

Calendar

Download iCal File

Clayton Mizgerd (UIC): 3-colorability of triangle-free graphs

It is well-known that dense triangle-free graphs are bipartite with high probability. Jenssen, Perkins, and Potukuchi showed that there are edge densities where the chromatic number of triangle-free graphs is (with high probability) 2, 3, 4, and unbounded. In this talk, we analyze the threshold from 3- to 4-colorability. We get a precise description of the scaling window via a comparison with the satisfiability of a random 2-SAT formula. Based on joint work with Will Perkins and Yuzhou Wang.

Please click here to make changes to, or delete, this seminar announcement.