Measurable Vizing’s theorem
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 $ -measur...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Cambridge University Press
2025-01-01
|
| Series: | Forum of Mathematics, Sigma |
| Subjects: | |
| Online Access: | https://www.cambridge.org/core/product/identifier/S2050509424000835/type/journal_article |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825206612748402688 |
|---|---|
| author | Jan Grebík |
| author_facet | Jan Grebík |
| author_sort | Jan Grebík |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-212d6b03a46f4c3c8f2aea4925edf336 |
| institution | Kabale University |
| issn | 2050-5094 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | Cambridge University Press |
| record_format | Article |
| series | Forum of Mathematics, Sigma |
| spelling | doaj-art-212d6b03a46f4c3c8f2aea4925edf3362025-02-07T07:50:18ZengCambridge University PressForum of Mathematics, Sigma2050-50942025-01-011310.1017/fms.2024.83Measurable Vizing’s theoremJan Grebík0https://orcid.org/0000-0002-9980-4660Masaryk University, Botanická 68A, 602 00 Brno, Czech Republic and UCLA, 520 Portola Plaza, Los Angeles, CA 90095, USAWe 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.https://www.cambridge.org/core/product/identifier/S2050509424000835/type/journal_article03E1560C0505C1537A50 |
| spellingShingle | Jan Grebík Measurable Vizing’s theorem Forum of Mathematics, Sigma 03E15 60C05 05C15 37A50 |
| title | Measurable Vizing’s theorem |
| title_full | Measurable Vizing’s theorem |
| title_fullStr | Measurable Vizing’s theorem |
| title_full_unstemmed | Measurable Vizing’s theorem |
| title_short | Measurable Vizing’s theorem |
| title_sort | measurable vizing s theorem |
| topic | 03E15 60C05 05C15 37A50 |
| url | https://www.cambridge.org/core/product/identifier/S2050509424000835/type/journal_article |
| work_keys_str_mv | AT jangrebik measurablevizingstheorem |