Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.17068 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911784786460672 |
|---|---|
| author | Timár, Ádám |
| author_facet | Timár, Ádám |
| contents | We prove that every (possibly infinite) graph of degree at most $d$ has a 4-dependent random proper $4^{d(d+1)/2}$-coloring, and one can construct it as a finitary factor of iid. For unimodular transitive (or unimodular random) graphs we construct an automorphism-invariant (respectively, unimodular) 2-dependent coloring by $3^{d(d+1)/2}$ colors. In particular, there exist random proper colorings for $\Z^d$ and for the regular tree that are 2-dependent and automorphism-invariant, or 4-dependent and finitary factor of iid. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_17068 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Finitely dependent random colorings of bounded degree graphs Timár, Ádám Probability We prove that every (possibly infinite) graph of degree at most $d$ has a 4-dependent random proper $4^{d(d+1)/2}$-coloring, and one can construct it as a finitary factor of iid. For unimodular transitive (or unimodular random) graphs we construct an automorphism-invariant (respectively, unimodular) 2-dependent coloring by $3^{d(d+1)/2}$ colors. In particular, there exist random proper colorings for $\Z^d$ and for the regular tree that are 2-dependent and automorphism-invariant, or 4-dependent and finitary factor of iid. |
| title | Finitely dependent random colorings of bounded degree graphs |
| topic | Probability |
| url | https://arxiv.org/abs/2402.17068 |