Equitable colourings of Borel graphs

Anton Bernshteyn ; Clinton T. Conley

Forum of Mathematics, Pi, Tome 9 (2021)

Résumé

Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $\Delta $, then for every integer $k \geq \Delta +1$, G has a proper colouring with k colours in which every two colour classes differ in size at most by $1$; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $\Delta $, then for each $k \geq \Delta + 1$, G has a Borel proper k-colouring in which every two colour classes are related by an element of the Borel full semigroup of G. In particular, such colourings are equitable with respect to every G-invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $\Delta $-colourings of graphs with small average degree. Namely, we prove that if $\Delta \geq 3$, G does not contain a clique on $\Delta + 1$ vertices and $\mu $ is an atomless G-invariant probability measure such that the average degree of G with respect to $\mu $ is at most $\Delta /5$, then G has a $\mu $-equitable $\Delta $-colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit.

Détail

DOI : 10.1017/fmp.2021.12

Bibliographie

[BK96] Becker, H. and Kechris, A. S., The Descriptive Set Theory of Polish Group Actions (Cambridge University Press, Cambridge, 1996).Google Scholar | DOI

[Bor79] Borodin, O. V., [Problems of Coloring and of Covering the Vertex Set of a Graph by Induced Subgraphs; in Russian], Ph.D. Thesis (Novosibirsk State University, Novosibirsk, Russia, 1979).Google Scholar

[CLW94] Chen, B.-L., Lih, K.-W. and Wu, P.-L., ‘Equitable coloring and maximum degree’, European J. Combin. 15 (1994), 443–447.Google Scholar | DOI

[Che18] Chen, R., ‘Decompositions and measures on countable Borel equivalence relations’, Preprint, 2018, .Google Scholar | arXiv

[CMT16] Conley, C. T., Marks, A. S. and Tucker-Drob, R., ‘Brooks’s theorem for measurable colorings’, Forum Math. Sigma 4 (2016), E16.Google Scholar | DOI

[Die00] Diestel, R., Graph Theory, second edn (Springer, New York, 2000).Google Scholar

[DJK94] Dougherty, R., Jackson, S. and Kechris, A. S., ‘The structure of hyperfinite borel equivalence relations’, Trans. Amer. Math. Soc. 341(1) (1994), 193–225.Google Scholar | DOI

[Erd64] Erdős, P., ‘Problem 9’, in Theory of Graphs and Its Applications, edited by Fiedler, M. (Czechoslovak Academy of Sciences, Prague, 1964), 159.Google Scholar

[ERT79] Erdős, P., Rubin, A. L. and Taylor, H., ‘Choosability in graphs’, in Proceedings of the West Coast Conference on Combinatorics , Graph Theory and Computing: Congressus Numerantium XXVI (Publisher, Arcata, California, 1979), 125–157.Google Scholar

[Far62] Farrell, R. H., ‘Representation of invariant measures’, Illinois J. Math. 6(3) (1962), 447–467.Google Scholar | DOI

[HS70] Hajnal, A. and Szemerédi, E., ‘Proof of a conjecture of P. Erdős’, in Combinatorial Theory and Its Application, edited by Erdős, P., Rényi, A. and Sós, V. T. (North-Holland, Amsterdam, 1970), 601–623.Google Scholar

[Kec95] Kechris, A. S., Classical Descriptive Set Theory (Springer-Verlag, New York, 1995).Google Scholar | DOI

[Kec19] Kechris, A. S., ‘The theory of countable Borel equivalence relations’, Preprint (2019). URL: http://www.math.caltech.edu/˜kechris/papers/lectures%20on%20CBER01.pdf.Google Scholar

[KM16] Kechris, A. S. and Marks, A. S., ‘Descriptive graph combinatorics’, Preprint (2016). URL: http://math.caltech.edu/˜kechris/papers/combinatorics16.pdf.Google Scholar

[KM04] Kechris, A. S. and Miller, B. D., Topics in Orbit Equivalence (Springer-Verlag, Berlin, 2004).Google Scholar | DOI

[KST99] Kechris, A. S., Solecki, S. and Todorcevic, S., ‘Borel chromatic numbers’, Adv. Math. 141 (1999), 1–44.Google Scholar | DOI

[KK08] Kierstead, H. A. and Kostochka, A. V., ‘A short proof of the Hajnal–Szemerédi theorem on equitable colouring’, Combin. Probab. Comput. 17(2) (2008), 265–270.Google Scholar | DOI

[Kie+10] Kierstead, H. A., Kostochka, A. V., Mydlarz, M. and Szemerédi, E., ‘A fast algorithm for equitable coloring’, Combinatorica 30(2) (2010), 217–224.Google Scholar | DOI

[KN05] Kostochka, A. V. and Nakprasit, K., ‘On equitable ∆-coloring of graphs with low average degree’, Theoret. Comput. Sci. 349 (2005), 82–91.Google Scholar | DOI

[Lih13] Lih, K.-W., ‘Equitable coloring of graphs’, in Handbook of Combinatorial Optimization, Vol. 2, edited by Pardalos, P. M., Du, D.-Z. and Graham, R. L. (Springer, Boston, MA, 2013), 1199–1248.Google Scholar | DOI

[Mar16] Marks, A., ‘A determinacy approach to Borel combinatorics’, J. Amer. Math. Soc. 29 (2016), 579–600.Google Scholar | DOI

[Nad90] Nadkarni, M. G., ‘On the existence of a finite invariant measure’, Proc. Indian Acad. Sci. Math. Sci. 100 (1990), 203–220.Google Scholar | DOI

[Tar49] Tarski, A., Cardinal Algebras (Oxford University Press, New York, 1949).Google Scholar

[Tse16] Tserunyan, A., ‘Introduction to descriptive set theory’, Preprint, 2016, http://www.math.uiuc.edu/˜anush/ Teaching_notes/dst_lectures.pdf.Google Scholar

[Var63] Varadarajan, V. S., ‘Groups of automorphisms of Borel spaces’, Trans. Amer. Math. Soc. 109(2) (1963), 191–220.Google Scholar | DOI

[Viz] Vizing, V. G., ‘ [Vertex colorings with given colors; in Russian]’, Metody Diskret. Anal. 29(1976), 3–10.Google Scholar