The Borel Distinguishing Number of Schreier Graphs

The Borel distinguishing number $D_B(\mathcal{G})$ of a Borel graph $\mathcal{G}$, recently introduced by Bilge and Kaya, is the minimum number of colors required to break the symmetry of $\mathcal{G}$ 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 $\mathrm{\Gamma }\curvearrowright n^{\mathrm{\Gamma }}$. We prove that $D_B(\mathcal{G})\le n+1$ for $\mathrm{\Gamma }={\mathbb{Z}}^d$ equipped with the standard generators. Moreover, we show that $D_B(\mathcal{G})\ge n+1$ if $\mathrm{\Gamma }$ is amenable and $\{\gamma \in \mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{C}\mathrm{a}\mathrm{y}(\mathrm{\Gamma },S))\mid \gamma (e)=e\}$ is non-trivial. We also show that $D_B(\mathcal{G})$ is finite if $\mathrm{\Gamma }$ is finitely generated, and give some applications of our results. These results answer some questions raised by Bilge and Kaya.