Approximate Schreier decorations and approximate Kőnig’s line coloring Theorem
[Décorations de Schreier approchées et un théorème de coloriage de lignes de Kőnig approché]
GrebÍk, Jan1
1 Mathematics Institute, University of Warwick, Coventry, CV4 7AL (United Kingdom)
Annales Henri Lebesgue, Tome 5 (2022), pp. 303-315.

À la suite d’un récent résultat de L. M. Tóth [Tót21, Annales Henri Lebesgue, Volume 4 (2021)], nous montrons que tout graphe borélien 𝒢, 2Δ-régulier et muni d’une mesure de probabilité borélienne (pas nécessairement invariante) admet une décoration de Schreier approchée. En réalité, nous montrons que les deux ingrédients correspondants pour les graphes finis ont des analogues approchés dans le cadre mesurable, i.e., un théorème de coloriage de lignes de Kőnig approché pour les graphes boréliens sans cycle impair, et une orientation équilibrée approchée pour les graphes boréliens de degré pair.

Following recent result of L. M. Tóth [Tót21, Annales Henri Lebesgue, Volume 4 (2021)] we show that every 2Δ-regular Borel graph 𝒢 with a (not necessarily invariant) Borel probability measure admits approximate Schreier decoration. In fact, we show that both ingredients from the analogous statements for finite graphs have approximate counterparts in the measurable setting, i.e., approximate Kőnig’s line coloring Theorem for Borel graphs without odd cycles and approximate balanced orientation for even degree Borel graphs.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/ahl.124
Classification : 37A50, 03E15, 20E05, 05C15, 28A05
Mots clés : Schreier decoration, Borel graphs, local-global equivalence, edge colorings
GrebÍk, Jan 1

1 Mathematics Institute, University of Warwick, Coventry, CV4 7AL (United Kingdom) 
@article{AHL_2022__5__303_0,
     author = {Greb\'Ik, Jan},
     title = {Approximate {Schreier} decorations and approximate {K\H{o}nig{\textquoteright}s} line coloring {Theorem}},
     journal = {Annales Henri Lebesgue},
     pages = {303--315},
     publisher = {\'ENS Rennes},
     volume = {5},
     year = {2022},
     doi = {10.5802/ahl.124},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/ahl.124/}
}
TY  - JOUR
AU  - GrebÍk, Jan
TI  - Approximate Schreier decorations and approximate Kőnig’s line coloring Theorem
JO  - Annales Henri Lebesgue
PY  - 2022
SP  - 303
EP  - 315
VL  - 5
PB  - ÉNS Rennes
UR  - http://www.numdam.org/articles/10.5802/ahl.124/
DO  - 10.5802/ahl.124
LA  - en
ID  - AHL_2022__5__303_0
ER  - 
%0 Journal Article
%A GrebÍk, Jan
%T Approximate Schreier decorations and approximate Kőnig’s line coloring Theorem
%J Annales Henri Lebesgue
%D 2022
%P 303-315
%V 5
%I ÉNS Rennes
%U http://www.numdam.org/articles/10.5802/ahl.124/
%R 10.5802/ahl.124
%G en
%F AHL_2022__5__303_0
GrebÍk, Jan. Approximate Schreier decorations and approximate Kőnig’s line coloring Theorem. Annales Henri Lebesgue, Tome 5 (2022), pp. 303-315. doi : 10.5802/ahl.124. http://www.numdam.org/articles/10.5802/ahl.124/

[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

[CLP16] Csóka, Endre; Lippner, Gábor; Pikhurko, Oleg Kőnig’s line coloring and Vizing’s theorems for graphings, Forum Math. Sigma, Volume 4 (2016), e27, 40 pages | Zbl

[EL10] Elek, Gábor; Lippner, Gábor Borel oracles. An analytical approach to constant-time algorithms, Proc. Am. Math. Soc., Volume 138 (2010) no. 8, pp. 2939-2947 | DOI | MR | Zbl

[Ele10] Elek, Gábor Parameter testing in bounded degree graphs of subexponential growth, Random Struct. Algorithms, Volume 37 (2010) no. 2, pp. 248-270 | DOI | MR | Zbl

[GP20] Grebík, Jan; Pikhurko, Oleg Measurable versions of Vizing’s theorem, Adv. Math., Volume 374 (2020), 107378, 40 pages | MR | Zbl

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

[KM04] Kechris, Alexander S.; Miller, Benjamin D. Topics in orbit equivalence, Lecture Notes in Mathematics, 1852, Springer, 2004 | DOI | Zbl

[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

[Kun21] Kun, Gábor The measurable Hall theorem fails for treeings (2021) (https://arxiv.org/abs/2106.02013)

[Lac88] Laczkovich, Miklós Closed sets without measurable matching, Proc. Am. Math. Soc., Volume 103 (1988) no. 3, pp. 894-896 | DOI | MR | Zbl

[Lov12] Lovász, László Large networks and graph limits, Colloquium Publications, 60, American Mathematical Society, 2012 | Zbl

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

Cité par Sources :