Volume 5 (2022)
GrebÍk, Jan
Approximate Schreier decorations and approximate Kőnig’s line coloring Theorem
Annales Henri Lebesgue, Volume 5 (2022), pp. 303-315.

Metadata

DOI10.5802/ahl.124
Keywords Schreier decoration, Borel graphs, local-global equivalence, edge colorings

Abstract

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.


References

[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