Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2408.12835 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913477328633856 |
|---|---|
| author | Ashvinkumar, Vikrant Kenney, Charles |
| author_facet | Ashvinkumar, Vikrant Kenney, Charles |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_12835 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Palette Sparsification via FKNP Ashvinkumar, Vikrant Kenney, Charles Combinatorics 05C15 G.2.2 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. |
| title | Palette Sparsification via FKNP |
| topic | Combinatorics 05C15 G.2.2 |
| url | https://arxiv.org/abs/2408.12835 |