Volume 5 (2022)
Bernshteyn, Anton
Borel fractional colorings of Schreier graphs
Annales Henri Lebesgue, Volume 5 (2022), pp. 1151-1160.

Metadata

DOI10.5802/ahl.145
Keywords fractional coloring, Borel sets, Borel combinatorics, Schreier graph, group action, symbolic dynamics

Abstract

Let Γ be a countable group and let G be the Schreier graph of the free part of the Bernoulli shift Γ↷2 Γ (with respect to some finite subset F⊆Γ). We show that the Borel fractional chromatic number of G is equal to 1 over the measurable independence number of G. As a consequence, we asymptotically determine the Borel fractional chromatic number of G when Γ is the free group, answering a question of Meehan.


References

[AW13] Abért, Miklós; Weiss, Benjamin Bernoulli actions are weakly contained in any free action, Ergodic Theory Dyn. Syst., Volume 33 (2013) no. 2, pp. 323-333 | DOI | MR | Zbl

[Ber19] Bernshteyn, Anton Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv. Math., Volume 353 (2019), pp. 153-223 | DOI | MR | Zbl

[CKTD13] Conley, Clinton T.; Kechris, Alexander S.; Tucker-Drob, Robin D. Ultraproducts of measure preserving actions and graph combinatorics, Ergodic Theory Dyn. Syst., Volume 33 (2013) no. 2, pp. 334-374 | DOI | MR | Zbl

[GG10] Gamarnik, David; Goldberg, David A. Randomized greedy algorithms for independent sets and matchings in regular graphs: Exact results and finite girth corrections, Comb. Probab. Comput., Volume 19 (2010) no. 1, pp. 61-85 | DOI | MR | Zbl

[Gre22] Grebík, Jan Approximate Schreier decorations and approximate König’s line coloring Theorem, Ann. Henri Lebesgue, Volume 5 (2022), pp. 303-315 | DOI | Zbl

[Kec95] Kechris, Alexander S. Classical Descriptive Set Theory, Graduate Texts in Mathematics, 156, Springer, 1995 | DOI | Zbl

[KM20] Kechris, Alexander S.; Marks, Andrew S. Descriptive Graph Combinatorics (2020) http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf (preprint)

[KST99] Kechris, Alexander S.; Solecki, Sławomir; Todorcevic, Stevo B. Borel chromatic numbers, Adv. Math., Volume 141 (1999) no. 1, pp. 1-44 | DOI | MR | Zbl

[LW07] Lauer, J.; Wormald, N. Large independent sets in regular graphs of large girth, J. Comb. Theory, Volume 97 (2007), pp. 999-1009 | DOI | MR | Zbl

[Mar16] Marks, Andrew S. A determinacy approach to Borel combinatorics, J. Am. Math. Soc., Volume 29 (2016) no. 2, pp. 579-600 | DOI | MR | Zbl

[Mee18] Meehan, C. Definable combinatorics of graphs and equivalence relations, Ph. D. Thesis, California Institute of Technology, Pasadena, CA, USA (2018) (https://resolver.caltech.edu/caltechthesis:06012018-160828760)

[Pik21] Pikhurko, Oleg Borel combinatorics of locally finite graphs, Surveys in combinatorics 2021 (Dabrowski, K.K. et al., eds.) (London Mathematical Society Lecture Note Series), Volume 470, Cambridge University Press, 2021, pp. 267-319 | DOI | MR | Zbl

[RV17] Rahman, Mustazee; Virág, Bálint Local algorithms for independent sets are half-optimal, Ann. Probab., Volume 45 (2017) no. 3, pp. 1543-1577 | MR | Zbl

[STD16] Seward, Brandon; Tucker-Drob, Robin D. Borel structurability on the 2-shift of a countable group, Ann. Pure Appl. Logic, Volume 167 (2016) no. 1, pp. 1-21 | DOI | MR | Zbl

[SU97] Scheinerman, Edward R.; Ullman, Daniel H. Fractional Graph Theory. A rational approach to the theory of graphs, John Wiley & Sons, 1997 (with a foreword by Claude Berge) | Zbl

[Tho20] Thornton, Riley Factor of i.i.d. processes and Cayley diagrams (2020) https://arxiv.org/abs/2011.146044v1 (preprint)

[Tót21] Tóth, Lázló M. Invariant Schreier decorations of unimodular random networks, Ann. Henri Lebesgue, Volume 4 (2021), pp. 1705-1726 | DOI | MR | Zbl