Geodesic
Measurable Vizing’s theorem
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e32

Voir la notice de l'article provenant de la source Cambridge University Press

We prove a full measurable version of Vizing’s theorem for bounded degree Borel graphs, that is, we show that every Borel graph $\mathcal {G}$ of degree uniformly bounded by $\Delta \in \mathbb {N}$ defined on a standard probability space $(X,\mu )$ admits a $\mu $-measurable proper edge coloring with $(\Delta +1)$-many colors. This answers a question of Marks [Question 4.9, J. Amer. Math. Soc. 29 (2016)] also stated in Kechris and Marks as a part of [Problem 6.13, survey (2020)], and extends the result of the author and Pikhurko [Adv. Math. 374, (2020)], who derived the same conclusion under the additional assumption that the measure $\mu $ is $\mathcal {G}$-invariant. 
Grebík, Jan. Measurable Vizing’s theorem. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e32. doi: 10.1017/fms.2024.83
@article{10_1017_fms_2024_83,
     author = {Greb{\'\i}k, Jan},
     title = {Measurable {Vizing{\textquoteright}s} theorem},
     journal = {Forum of Mathematics, Sigma},
     pages = {e32},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2024.83},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.83/}
}
TY  - JOUR
AU  - Grebík, Jan
TI  - Measurable Vizing’s theorem
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e32
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.83/
DO  - 10.1017/fms.2024.83
ID  - 10_1017_fms_2024_83
ER  - 
%0 Journal Article
%A Grebík, Jan
%T Measurable Vizing’s theorem
%J Forum of Mathematics, Sigma
%D 2025
%P e32
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2024.83/
%R 10.1017/fms.2024.83
%F 10_1017_fms_2024_83

[Abe10] Abert, M., ‘Some questions,’ (2010). Google Scholar

[BCG+24] Brandt, S., Chang, Y.-J., Grebík, J., Grunau, C., Rozhoň, V. and Vidnyánszky, Z., ‘On homomorphism graphs’, Forum of Mathematics, Pi 12 (2024), e10. Google Scholar | DOI

[BD23] Bernshteyn, A. and Dhawan, A., ‘Fast algorithms for Vizing’s theorem on bounded degree graphs’, Preprint, 2023, . Google Scholar | arXiv

[Ber19] Bernshteyn, A., ‘Measurable versions of the Lovász local lemma and measurable graph colorings’, Advances in Mathematics 353 (2019), 153–223. Google Scholar | DOI

[Ber22] Bernshteyn, A., ‘A fast distributed algorithm for -edge-coloring’, Journal of Combinatorial Theory , Series B 152 (2022), 319–352. Google Scholar | DOI

[Ber23] Bernshteyn, A., ‘Distributed algorithms, the Lovász local lemma, and descriptive combinatorics’, Invent. Math. 233 (2023), 495–542. Google Scholar | DOI

[BHT24] Bencs, F., Hrušková, A. and Tóth, L. M., ‘Factor-of-iid Schreier decorations of lattices in Euclidean spaces’, Discrete Mathematics 347(9) (2024),114056. Google Scholar | DOI

[BW23] Bowen, M. and Weilacher, F., ‘Definable König theorems’, Proc. Amer. Math. Soc. 151 (2023), 4991–4996. Google Scholar | DOI

[CGM+17] Csóka, E., Grabowski, Ł., Máthé, A., Pikhurko, O. and Tyros, K., ‘Borel version of the local lemma’, Preprint, 2017, . Google Scholar | arXiv

[Chr23] Christiansen, A. B. G., ‘The power of multi-step Vizing chains’, In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 (Association for Computing Machinery, New York, 2023), 1013–1026. Google Scholar | DOI

[CJM+23] Conley, C. T., Jackson, S., Marks, A. S., Seward, B. and Tucker-Drob, Robin, ‘Borel asymptotic dimension and hyperfinite equivalence relations’, Duke Math. J. 172(16) (2023), 3175–3226. Google Scholar | DOI

[CLP16] Csóka, E., Lippner, G. and Pikhurko, O., ‘Invariant gaussian processes and independent sets on regular graphs of large girth’, Forum of Math., Sigma 4 (2016). Google Scholar

[CM17] Conley, C. T. and Miller, B. D., ‘Measure reducibility of countable Borel equivalence relations’, Ann. of Math. (2) 185(2) (2017), 347–402. Google Scholar | DOI

[CMTD16] Conley, C. T., Marks, A. S. and Tucker-Drob, R. D., ‘Brooks’ theorem for measurable colorings’, Forum Math. Sigma e16(4) (2016), 23. Google Scholar

[CT21] Conley, C. T. and Tamuz, O., ‘Unfriendly colorings of graphs with finite average degree’, Proc. Lond. Math. Soc. 3 (2021). Google Scholar

[CU22] Chandgotia, N. and Unger, S., ‘Borel factors and embeddings of systems in subshifts’, Preprint, 2022, . Google Scholar | arXiv

[DF92] Dougherty, R. and Foreman, M., ‘Banach–Tarski paradox using pieces with the property of Baire’, Proc. Nat. Acad. Sci. U.S.A. 89(22) (1992), 10726–10728. Google Scholar PubMed | DOI

[Gab00] Gaboriau, D., ‘Coût des relations d’équivalence et des groupes’, Invent. Math. 139(1) (2000), 41–98. Google Scholar | DOI

[GMP17] Grabowski, Ł., Máthé, A. and Pikhurko, O., ‘Measurable circle squaring’, Ann. of Math. (2) 185(2) (2017), 671–710. Google Scholar | DOI

[GP20] Grebík, J. and Pikhurko, O., ‘Measurable versions of Vizing’s theorem’, Advances in Mathematics 374 (2020), 107378. Google Scholar | DOI

[GR23] Grebík, J. and Rozhoň, V., ‘Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics’, Advances in Mathematics 431 (2023), 109241. Google Scholar | DOI

[Gre22] Grebík, J., ‘Approximate Schreier decorations and approximate König’s line coloring theorem’, Annales Henri Lebesgue 5 (2022), 303–315. Google Scholar | DOI

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

[Kec24] Kechris, A. S., ‘The theory of countable Borel equivalence relations’, Cambridge Tracts in Mathematics (Cambridge University Press, 2024) To appear. Google Scholar

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

[KM20] Kechris, A. S. and Marks, A. S., ‘Descriptive graph combinatorics’, (2020). http://www.math.caltech.edu/~kechris/papers/combinatorics20book.pdf. Google Scholar

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

[Kuh94] Kuhn, G., ‘Amenable actions and weak containment of certain representations of discrete groups’, Proc. Amer. Math. Soc. 122(3) (1994), 751–757. Google Scholar | DOI

[Lac90] Laczkovich, M., ‘Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem’, J. Reine Angew. Math. 404 (1990), 77–117. Google Scholar

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

[MU16] Marks, A. and Unger, S., ‘Baire measurable paradoxical decompositions via matchings’, Advances in Mathematics 289 (2016), 397–410. Google Scholar | DOI

[MU17] Marks, A. S. and Unger, S. T., ‘Borel circle squaring’, Ann. of Math. (2) 186(2) (2017), 581–605. Google Scholar | DOI

[Pik21] Pikhurko, O., ‘Borel combinatorics of locally finite graphs’, Surveys in Combinatorics 2021, the 28th British Combinatorial Conference (2021), 267–319. Google Scholar | DOI

[QW22] Qian, L. and Weilacher, F., ‘Descriptive combinatorics, computable combinatorics, and asi algorithms’, Preprint, 2022, . Google Scholar | arXiv

[SSTF12] Stiebitz, M., Scheide, D., Toft, B. and Favrholdt, L. M., Graph Edge Coloring, Wiley Series in Discrete Mathematics and Optimization (John Wiley & Sons, Inc., Hoboken, NJ, 2012). Google Scholar

[T2́1] Tóth, L. M., ‘Invariant schreier decorations of unimodular random networks’, Annales Henri Lebesgue 4 (2021), 1705–1726. Google Scholar | DOI

[Wei21] Weilacher, F., ‘Borel edge colorings for finite dimensional groups’, Preprint, 2021, . Google Scholar | arXiv

Cité par Sources :