Borel chromatic-number conjecture for graphs of subexponential growth

Let GG be a Borel graph of subexponential growth. Write a(G)a(G) for its asymptotic separation index and χB(G)\chi_{\mathrm{B}}(G) for its Borel chromatic number.

Borel chromatic-number conjecture.

χB(G)max{2a(G),3}.\chi_{\mathrm{B}}(G) \leqslant \max\{2a(G),3\}.

This conjecture would sharpen the general bound χB(G)2a(G)+1\chi_{\mathrm{B}}(G) \leqslant 2a(G)+1 and, when a(G)2a(G)\geqslant 2, give the proposed bound χB(G)2a(G)\chi_{\mathrm{B}}(G)\leqslant 2a(G). Its status is not resolved in the supplied material.

Sources & referencesView supporting material

Primary source

Anton Bernshteyn, “Distributed Algorithms, the Lovász Local Lemma, and Descriptive Combinatorics”, arXiv:2004.04905 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.