ÂÌñÉç

Speaker: , assistant professor of mathematics, University of Illinois at Urbana-Champaign

Title: Independent Sets and Colorings of K_{t,t,t}-Free Graphs

Abstract: Ajtai, Erdős, Komlós, and Szemerédi conjectured in 1981 that for every graph F, every n-vertex F-free graph G of average degree d contains an independent set of size at least Ω(n log d / d). The largest class of graphs for which this was previously known was established by Alon, Krivelevich, and Sudakov in 1999, who proved it for the so-called almost bipartite graphs, namely subgraphs of K_{1,t,t}.

We prove the conjecture for all 3-colorable graphs F, i.e., subgraphs of K_{t,t,t}, representing the first progress on the problem in more than 25 years. In particular, we show that every n-vertex K_{t,t,t}-free graph contains an independent set of size at least (1 – o(1)) · n log d / d, which both matches and significantly strengthens Shearer’s celebrated bound for triangle-free graphs (the case t = 1). Our proof combines a new variant of the Rödl nibble method for constructing independent sets with a Turán-type result on K_{t,t,t}-free graphs.

A closely related conjecture of Alon, Krivelevich, and Sudakov (1999) asserts that any F-free graph G of maximum degree at most Δ has chromatic number O(Δ / log Δ). This was previously known only for almost bipartite graphs, with much of the progress focused on improving the constant factor. We establish this conjecture as well for all 3-colorable graphs F. This is joint work with Abhishek Dhawan and Oliver Janzer.

Discrete Applied Math Seminar