Borel Combinatorics of Schreier Graphs of $\mathbb{Z}$-actions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912679458766848 |
|---|---|
| author | Gao, Su Jiang, Yingying Wang, Tianhao |
| author_facet | Gao, Su Jiang, Yingying Wang, Tianhao |
| contents | In this paper we consider the Borel combinatorics of Schreier graphs of $\mathbb{Z}$-actions with arbitrary finite generating sets. We formulate the Borel combinatorics in terms of existence of Borel equivariant maps from $F(2^{\mathbb{Z}})$ to subshifts of finite type. We then show that the Borel combinatorics and the continuous combinatorics coincide, and both are decidable. This is in contrast with the case of $\mathbb{Z}^2$-actions. We then turn to the problem of computing Borel chromatic numbers for such graphs. We give an algorithm for this problem which runs in exponential time. We then prove some bounds for the Borel chromatic numbers and give a formula for the case where the generating set has size 4. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_27290 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Borel Combinatorics of Schreier Graphs of $\mathbb{Z}$-actions Gao, Su Jiang, Yingying Wang, Tianhao Combinatorics Dynamical Systems Logic 05C15, 54H05 In this paper we consider the Borel combinatorics of Schreier graphs of $\mathbb{Z}$-actions with arbitrary finite generating sets. We formulate the Borel combinatorics in terms of existence of Borel equivariant maps from $F(2^{\mathbb{Z}})$ to subshifts of finite type. We then show that the Borel combinatorics and the continuous combinatorics coincide, and both are decidable. This is in contrast with the case of $\mathbb{Z}^2$-actions. We then turn to the problem of computing Borel chromatic numbers for such graphs. We give an algorithm for this problem which runs in exponential time. We then prove some bounds for the Borel chromatic numbers and give a formula for the case where the generating set has size 4. |
| title | Borel Combinatorics of Schreier Graphs of $\mathbb{Z}$-actions |
| topic | Combinatorics Dynamical Systems Logic 05C15, 54H05 |
| url | https://arxiv.org/abs/2510.27290 |