Borel Vizing's theorem for graphs of subexponential growth (Q6654016)

A graph \(G=(V,E)\) is a Borel graph if \(V\) is a Borel space and \(E\) is a Borel subset of \(V^{2}\). All graphs in the paper under review have finite maximum degree \(\Delta(G)\). Generalising the usual notion of edge-colouring, we say the Borel chromatic index \(\chi^{\prime}_{B}(G)\) of a Borel graph \(G\) is the smallest \(q\in \mathbb{N}\) such that \(G\) has a proper Borel edge-colouring \(\phi: E(G)\rightarrow [q]\), meaning that \(\phi^{-1}(i)\) is a Borel subset of \(E\) for every \(i\in [q]\).\N\NAs with arbitrary edge-colourings, there is an obvious lower bound \(\chi^{\prime}_{B}(G)\geq \Delta(G)\). For arbitrary edge-colourings of finite graphs Vizing's theorem says that if the edge-chromatic number is not \(\Delta(G)\), it is \(\Delta(G)+1\). With the requirement that colourings be Borel, the situation is more complex. In [\textit{A. S. Kechris} et al., Adv. Math. 141, No. 1, 1--44 (1999; Zbl 0918.05052)] and [\textit{A. S. Marks}, J. Am. Math. Soc. 29, No. 2, 579--600 (2016; Zbl 1403.03088)] it is shown firstly that \(\chi^{\prime}_{B}(G)\leq 2\Delta(G)-1\) and secondly, perhaps initially surprisingly, that for every \(\Delta\in \mathbb{N}\) there is a Borel graph for which \(\Delta(G)=\Delta\) but \(\chi^{\prime}_{B}(G)=2\Delta(G)-1\). However, there are a number of precise results in the general spirit of the statement that by removing a small set of vertices we can reduce \(\chi^{\prime}_{B}(G)\) to \(\Delta(G)+1\) or close to it. In the paper under review, the authors show that Borel graphs of subexponential growth and maximum degree \(\Delta\) have \(\chi^{\prime}_{B}(G)\leq \Delta(G)+1\).\N\NTo define subexponential growth, firstly say a function \(f: \mathbb{N}\rightarrow \mathbb{N}\) is subexponential if \(\forall \epsilon>0\) \(\exists R(\epsilon)\in \mathbb{N}\) such that \(R\geq R(\epsilon)\) \(f(G)<\exp(\epsilon R)\). Next say a function \(f: \mathbb{N}\rightarrow \mathbb{N}\) bounds the growth of a graph \(G\) if, letting \(N_{G}^{R}[v]\) be the set of vertices at distance at most \(R\) from \(v\), we have \(\vert N_{G}^{R}[v]\vert \leq f(R)\). Finally, say that a graph is of subexponential growth if its growth is bounded by a subexponential function. The rough notion that many combinatorial problems can be solved \lq in a Borel way\rq\, on graphs of subexponential growth, is emerging from some other recent papers as well, noted in the paper.\N\NThe proof depends on a link with distributed computing which was noted by the first author of the paper under review. In particular the LOCAL model of distributed computing introduced by \textit{N. Linial} [SIAM J. Comput. 21, No. 1, 193--201 (1992; Zbl 0787.05058)] is important and the main technical result leading to the main result is a proof of the existence of a deterministic LOCAL algorithm which finds a suitable \(\Delta+1\) colouring of the graph.