Speaker: Abhishek Dhawan (UIUC)
Title: Palette Sparsification via the Nibble Method
Abstract: A celebrated palette sparsification result of Assadi, Chen, and Khanna states that in every $n$-vertex graph of maximum degree $\Delta$, sampling $\Theta(\log n)$ colors per vertex from $[\Delta+1]$ almost certainly allows for a proper coloring from the sampled colors. Alon and Assadi extended this work proving a similar result for $O(\Delta/\log \Delta)$-coloring triangle-free graphs. A key part of their argument involves a proposition regarding list coloring with constraints on color degrees. The proof of this proposition follows the so-called R\”odl nibble method. The approach can be adapted to prove analogous results for $K_{1, t, t}$-free graphs as well as locally-sparse graphs. In this talk, we will discuss the approach in detail and outline potential future directions of inquiry.
This talk is based on joint work with James Anderson and Anton Bernshteyn.
