Combinatorics and Discrete Probability Seminar
Clayton Mizgerd
UIC
3-colorability of triangle-free graphs
Abstract: 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.
Monday October 21, 2024 at 3:00 PM in 1227 SEO