Soit un groupe dénombrable. Considérons le graphe de Schreier de la partie libre du décalage de Bernoulli (par rapport à un ensemble fini ). Nous montrons que le nombre chromatique fractionnaire borélien de est égal à sur le nombre d’indépendance mesurable de . Comme conséquence, nous déterminons l’asymptotique du nombre chromatique fractionnaire borélien de lorsque est le groupe libre, ce qui répond à une question de Meehan.
Let be a countable group and let be the Schreier graph of the free part of the Bernoulli shift (with respect to some finite subset ). We show that the Borel fractional chromatic number of is equal to over the measurable independence number of . As a consequence, we asymptotically determine the Borel fractional chromatic number of when is the free group, answering a question of Meehan.
Accepté le :
Publié le :
Mots clés : fractional coloring, Borel sets, Borel combinatorics, Schreier graph, group action, symbolic dynamics
@article{AHL_2022__5__1151_0, author = {Bernshteyn, Anton}, title = {Borel fractional colorings of {Schreier} graphs}, journal = {Annales Henri Lebesgue}, pages = {1151--1160}, publisher = {\'ENS Rennes}, volume = {5}, year = {2022}, doi = {10.5802/ahl.145}, language = {en}, url = {http://archive.numdam.org/articles/10.5802/ahl.145/} }
Bernshteyn, Anton. Borel fractional colorings of Schreier graphs. Annales Henri Lebesgue, Tome 5 (2022), pp. 1151-1160. doi : 10.5802/ahl.145. http://archive.numdam.org/articles/10.5802/ahl.145/
[AW13] 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] Measurable versions of the Lovász Local Lemma and measurable graph colorings, Adv. Math., Volume 353 (2019), pp. 153-223 | DOI | MR | Zbl
[CKTD13] Ultraproducts of measure preserving actions and graph combinatorics, Ergodic Theory Dyn. Syst., Volume 33 (2013) no. 2, pp. 334-374 | DOI | MR | Zbl
[GG10] 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] Approximate Schreier decorations and approximate König’s line coloring Theorem, Ann. Henri Lebesgue, Volume 5 (2022), pp. 303-315 | DOI | Zbl
[Kec95] Classical Descriptive Set Theory, Graduate Texts in Mathematics, 156, Springer, 1995 | DOI | Zbl
[KM20] Descriptive Graph Combinatorics (2020) http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf (preprint)
[KST99] Borel chromatic numbers, Adv. Math., Volume 141 (1999) no. 1, pp. 1-44 | DOI | MR | Zbl
[LW07] Large independent sets in regular graphs of large girth, J. Comb. Theory, Volume 97 (2007), pp. 999-1009 | DOI | MR | Zbl
[Mar16] A determinacy approach to Borel combinatorics, J. Am. Math. Soc., Volume 29 (2016) no. 2, pp. 579-600 | DOI | MR | Zbl
[Mee18] 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] 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] Local algorithms for independent sets are half-optimal, Ann. Probab., Volume 45 (2017) no. 3, pp. 1543-1577 | MR | Zbl
[STD16] Borel structurability on the -shift of a countable group, Ann. Pure Appl. Logic, Volume 167 (2016) no. 1, pp. 1-21 | DOI | MR | Zbl
[SU97] Fractional Graph Theory. A rational approach to the theory of graphs, John Wiley & Sons, 1997 (with a foreword by Claude Berge) | Zbl
[Tho20] Factor of i.i.d. processes and Cayley diagrams (2020) https://arxiv.org/abs/2011.146044v1 (preprint)
[Tót21] Invariant Schreier decorations of unimodular random networks, Ann. Henri Lebesgue, Volume 4 (2021), pp. 1705-1726 | DOI | MR | Zbl
Cité par Sources :