Skip to content
DraconiticResearch
Search Sources API
181,716 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

The Borel Distinguishing Number of Schreier Graphs

  • Junhao Chen
  • Jie Zou
Open at sourcePDFDOICite

Abstract

The Borel distinguishing number DB(𝒢) of a Borel graph 𝒢, recently introduced by Bilge and Kaya, is the minimum number of colors required to break the symmetry of 𝒢 in a Borel way. In this paper, we investigate the Borel distinguishing number of Schreier graphs induced by the free part of the shift action Γcurvearrowright nΓ. We prove that DB(𝒢)≤ n+1 for Γ=ℤd equipped with the standard generators. Moreover, we show that DB(𝒢)≥ n+1 if $ Γ$ is amenable and $ \{γ\in \mathrm{Aut}(\mathrm{Cay}(Γ,S)) \mid γ(e) = e \}$ is non-trivial. We also show that DB(𝒢) is finite if Γ is finitely generated, and give some applications of our results. These results answer some questions raised by Bilge and Kaya.

Related

  1. Spectral Theory and Descriptive Combinatorics for Non-Regular Borel pmp Graphs
    Cecelia Higgins, Pieter Spaas, Sofia Torelli
    arXivPreprintarXiv licenceFull textAnalysis & PDEsCombinatorics & discrete mathematicsarXiv
  2. Unfriendly partitions of locally finite Borel graphs
    José de Jesús Pelayo-Gómez
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  3. Adjacent vertex distinguishing total chromatic number of graph products
    Amitayu Banerjee, Jayabalan Geetha, Kanagasabapathi Somasundaram
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. Distinguishing graphs with simple spectrum by homomorphism counts
    Takanori Maehara
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ

Cite

BibTeXRIS
BibTeX
@misc{chen2026borel,
  title = {{The Borel Distinguishing Number of Schreier Graphs}},
  author = {Junhao Chen and Jie Zou},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.15003},
  eprint = {2609.15003},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.15003},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - The Borel Distinguishing Number of Schreier Graphs
AU  - Junhao Chen
AU  - Jie Zou
PY  - 2026
DA  - 2026/09/14
PB  - arXiv
DO  - 10.48550/arxiv.2609.15003
UR  - https://arxiv.org/abs/2609.15003
AB  - The Borel distinguishing number D_B(𝒢) of a Borel graph 𝒢, recently introduced by Bilge and Kaya, is the minimum number of colors required to break the symmetry of 𝒢 in a Borel way. In this paper, we investigate the Borel distinguishing number of Schreier graphs induced by the free part of the shift action Γcurvearrowright n^Γ. We prove that D_B(𝒢)≤ n+1 for Γ=ℤ^d equipped with the standard generators. Moreover, we show that D_B(𝒢)≥ n+1 if $ Γ$ is amenable and $ \{γ\in \mathrm{Aut}(\mathrm{Cay}(Γ,S)) \mid γ(e) = e \}$ is non-trivial. We also show that D_B(𝒢) is finite if Γ is finitely generated, and give some applications of our results. These results answer some questions raised by Bilge and Kaya.
ER  -