Graph Theory and Combinatorics Seminar
- Sponsor
- Department of Mathematics
- Speaker
- Abhishek Dhawan
- Contact
- Abhishek Dhawan
- adhawan2@illinois.edu
- Originating Calendar
- Mathematics Seminar Series: Combinatorics
Speaker: Abhishek Dhawan (UIUC)
Title: Independent sets in 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 of average degree d contains an independent set of size Ω(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. More precisely, we show that every n-vertex K_{t,t,t}-free graph of average degree d contains an independent set of size at least (1 − o(1))n log d/d, matching Shearer's celebrated bound for triangle-free graphs (the case t = 1) and thereby yielding a substantial strengthening of it. We develop a new variant of the Rödl nibble method to prove this result, which is of independent interest.
This talk is based on joint work with Oliver Janzer and Abhishek Methuku.