Back to Search
Start Over
Palette Sparsification via FKNP
- Publication Year :
- 2024
-
Abstract
- A random set $S$ is $p$-spread if, for all sets $T$, $$\mathbb{P}(S \supseteq T) \leq p^{|T|}.$$ There is a constant $C>1$ large enough that for every graph $G$ with maximum degree $D$, there is a $C/D$-spread distribution on $(D+1)$-colorings of $G$. Making use of a connection between thresholds and spread distributions due to Frankston, Kahn, Narayanan, and Park, a palette sparsification theorem of Assadi, Chen, and Khanna follows.<br />Comment: 18 pages
- Subjects :
- Mathematics - Combinatorics
05C15
G.2.2
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2408.12835
- Document Type :
- Working Paper