Borel combinatorics of Schreier graphs of ℤ \mathbb{Z} -actions
Su Gao, Yingying Jiang, Tianhao Wang · 2025
Read Borel combinatorics of Schreier graphs of ℤ \mathbb{Z} -actions by Su Gao, Yingying Jiang, Tianhao Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-27290.txt.
Introduction
Su Gao, Yingying Jiang, and Tianhao Wang compute Borel chromatic numbers for Schreier graphs of integer group actions. These graphs encode how an integer action with a finite generating set moves points in a shift space, and Borel coloring asks for a measurable proper coloring using few colors. The focus is the free part of the two-symbol shift space with finite symmetric generating sets.
The team proves general lower and upper bounds and exact values in special cases. The Borel values sometimes match the chromatic numbers of the corresponding distance graphs on the integers, but more often differ from them. The gap highlights how definability constraints change coloring problems in descriptive combinatorics, and the bounds give a reference for future work on Borel graph invariants.
Catalog record
| CREATOR | Su Gao, Yingying Jiang, Tianhao Wang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-27290
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Borel combinatorics of Schreier graphs of ℤ \mathbb{Z} -actions Su Gao, Yingying Jiang, Tianhao Wang Abstract . 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 ℤ ) 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 ℤ 2 \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 4 . 1. Introduction Borel combinatorics studies combinatorial properties of topological graphs or more generally Borel graphs. Since the seminal paper of Kechris, Solecki and Todorcevic [ 13 ] on Borel chromatic numbers, many researchers have contributed to this new and rapidly growing area of research; a comprehensive survey can be found in the recent book by Kechris and Marks [ 14 ] . One of the reasons Borel combinatorics is interesting to researchers is that one obtains different answers to combinatorial questions when imposing definability requirements on the combinatorial objects. For instance, Laczkovich realized early on that the graph on the unit circle defined by a rotation by a fixed irrational angle has chromatic number 2 (since every connected component is isomorphic to a bi-infinite path) but its Borel chromatic number is necessarily 3 , that is, any set of colors one needs to use to find a Borel proper coloring function from this graph must have at least 3 elements. More recently, it was discovered by Gao, Jackson, Krohne and Seward [ 7 , 8 ] that there is a further difference between Borel combinatorics and continuous combinatorics for topological graphs for nontrivial reasons. For instance, the above graph considered by Laszkovich does not have a sensible continuous chromatic number because the space is connected. But if one considers the space with one connected component removed, then it becomes zero-dimensional and the continuous chromatic number makes sense and can be seen to be 3 (while the Borel chromatic number remains 3 ). Answering a question of [ 13 ] , the authors of [ 8 ] considered the free part of the \mathbb{Z}^{2} -action on the shift space 2^{\mathbb{Z}^{2}} , and showed that the Borel chromatic number is 3 ; in contrast, they also showed (see [ 7 ] ) that the continuous chromatic number is 4 . A similar difference exists for edge chromatic numbers of this graph (see [ 1 , 5 , 7 , 9 , 10 , 16 ] ). The computations of chromatic numbers and edge chromatic numbers belong to a class of questions known as locally checkable labelling ( LCL ) problems (see, e.g., [ 10 , 11 ] ), a concept that had been studied in distributed computing in computer science (see, e.g. [ 2 ] ). Bernshteyn’s influential work [ 4 ] connected the distributed computing and Borel combinatorics together. There are now many results that characterize the descriptive-set-theoretic complexity of LCL problems by the computational complexity of local algorithms that solve the problem in a distributed fashion. In this paper we study the Borel chromatic numbers of Schreier graphs that come from \mathbb{Z} -actions but with arbitrary finite sets of generators. More generally, we formulate the LCL problems in terms of the existence of Borel equivariant maps from F(2^{\mathbb{Z}}) , the free part of the \mathbb{Z} -action on the shift space 2^{\mathbb{Z}} , to certain subshifts of finite type. Then we show that the Borel combinatorics in this context is the same as the continuous combinatorics, via the following main theorem. Theorem 1.1 . Let X be a \mathbb{Z} -subshift of finite type. Then the following are equivalent: (1) There exists a Borel equivariant map from F(2^{\mathbb{Z}}) to X ; (2) There exists a continuous equivariant map from F(2^{\mathbb{Z}}) to X . By the results of [ 7 , 8 ] , we know that the theorem fails when \mathbb{Z} is replaced by \mathbb{Z}^{2} . In fact, using some results of [ 7 ] we give a more concrete characterization of the above problems, and show that the problem is actually decidable, that is, there is an algorithm which, given a subshift of finite type, computes whether there exists a Borel equivariant map from F(2^{\mathbb{Z}}) to X . We then apply the main theorem to the problem of computing Borel chromatic numbers. If S is a finite generating set of \mathbb{Z} that is symmetric (i.e., S=-S ) and 0\not\in S , we obtain a Schreier graph G_{S} on F(2^{\mathbb{Z}}) by putting an edge between x and y if and only if there is s\in S such that s\cdot x=y . As mentioned above, this problem is now computable, that is, given S , the Borel chromatic number of G_{S} is a computable function with S as input. However, the naive algorithm that computes the Borel chromatic number takes exponential time in \max S . Thus it is still not feasible for us to compute the full answer of this problem. We then prove some partial results on this problem. Specifically, we prove some results on the upper and lower bounds, and then obtain the exact answers in some special cases. The following are our main results. Theorem 1.2 . Let S=\{\pm a_{1},\dots,\pm a_{n}\} with \gcd(a_{1},\dots,a_{n})=1 . Let \chi(S) be the Borel chromatic number of G_{S} . Then the following hold. (1) 3\leq\chi(S)\leq\left\lfloor\displaystyle\frac{3}{2}n\right\rfloor+1 . (2) If S\cap(k+1)\mathbb{Z}=\varnothing for some k\geq 1 , then \chi(S)\leq k+2 . (3) If (a_{1},\dots,a_{n})=(1,\dots,n) , then \chi(S)=n+2 . (4) If n=2 and (a_{1},a_{2})\neq(1,2) , then \chi(S)=3 . We are not able to give a general formula for \chi(S) when n\geq 3 , but our method can determine the value of \chi(S) for many different types of S . In particular, we show that for any n\geq 1 and 3\leq k\leq n+2 , there is a generating set S as above where |S|=2n and \chi(S)=k . However, we do not have any example of an S where |S|=2n but \chi(S)>n+2 . The rest of the paper is organized as follows. In Section 2 we recall some preliminary concepts and results in descriptive set theory, topological dynamics, and graph theory. In particular, we explain how to formulate Borel combinatorics by the existence of Borel equivariant maps into subshifts of finite type. In Section 3 we prove Theorem 1.1 and give a finitary characterization which is equivalent to both clauses of Theorem 1.1 . This finitary characterization turns out to be decidable. Starting from Section 4 we turn to the problem of finding Borel chromatic numbers of G_{S} . In Section 4 we give an algorithm for the problem. However, the algorithm runs in exponential time in \max S . In Section 5 we prove Theorem 1.2 (1)–(3) and give some conseqences. In Section 6 we prove Theorem 1.2 (4). Finally, in Section 7 we make some