Palette Sparsification via FKNP

Vikrant Ashvinkumar, Charles Kenney

A random set $S$ is $p$-spread if, for all sets $T$, $$\mathbb{P}(S\supseteq T)\le p^{|T|}.$$ There is a constant $C>1$ large enough that for every graph $G$ with maximum degree…