## Definable Kőnig theorems

HTML articles powered by AMS MathViewer

- by Matt Bowen and Felix Weilacher
- Proc. Amer. Math. Soc.
**151**(2023), 4991-4996 - DOI: https://doi.org/10.1090/proc/16355
- Published electronically: July 28, 2023
- PDF | Request permission

## Abstract:

Let $X$ be a Polish space with Borel probability measure $\mu ,$ and let $G$ be a Borel graph on $X$ with no odd cycles and maximum degree $\Delta (G).$ We show that the Baire measurable edge chromatic number of $G$ is at most $\Delta (G)+1$, and if $G$ is $\mu$-hyperfinite then the $\mu$-measurable edge chromatic number obeys the same bound. More generally, we show that $G$ has Borel edge chromatic number at most $\Delta (G)$ plus its asymptotic separation index.## References

- Anton Bernshteyn,
*Measurable versions of the Lovász local lemma and measurable graph colorings*, Adv. Math.**353**(2019), 153–223. MR**3979016**, DOI 10.1016/j.aim.2019.06.031 - Ferenc Bencs, Aranka Hrušková, and László Márton Tóth,
*Factor-of-iid schreier decorations of lattices in Euclidean spaces*, arXiv:2101.12577 (2021). - Matthew Bowen, Gábor Kun, and Marcin Sabok,
*Perfect matchings in hyperfinite graphings*, arXiv:2106.01988 (2022). - Clinton Conley, Steve Jackson, Andrew Marks, Brandon Seward, and Robin Tucker-Drob,
*Borel asymptotic dimension and hyperfinite equivalence relations*, arXiv:2009.06721 (2020). - Clinton Conley, Steve Jackson, Andrew Marks, Brandon Seward, and Robin Tucker-Drob,
*Hyperfiniteness and Borel combinatorics*, J. Eur. Math. Soc. (JEMS)**22**(2020), no. 3, 877–892. MR**4055991**, DOI 10.4171/jems/935 - Clinton T. Conley and Benjamin D. Miller,
*A bound on measurable chromatic numbers of locally finite Borel graphs*, Math. Res. Lett.**23**(2016), no. 6, 1633–1644. MR**3621100**, DOI 10.4310/MRL.2016.v23.n6.a3 - Clinton T. Conley and Benjamin D. Miller,
*Measurable perfect matchings for acyclic locally countable Borel graphs*, J. Symb. Log.**82**(2017), no. 1, 258–271. MR**3631286**, DOI 10.1017/jsl.2016.44 - Endre Csóka, Gábor Lippner, and Oleg Pikhurko,
*Kőnig’s line coloring and Vizing’s theorems for graphings*, Forum Math. Sigma**4**(2016), Paper No. e27, 40. MR**3569061**, DOI 10.1017/fms.2016.22 - Jan Grebík and Oleg Pikhurko,
*Measurable versions of Vizing’s theorem*, Adv. Math.**374**(2020), 107378, 40. MR**4157578**, DOI 10.1016/j.aim.2020.107378 - Jan Grebík and Václav Rozhoň,
*Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics*, arXiv:2103.08394 (2021). - A. S. Kechris, S. Solecki, and S. Todorcevic,
*Borel chromatic numbers*, Adv. Math.**141**(1999), no. 1, 1–44. MR**1667145**, DOI 10.1006/aima.1998.1771 - Alexander S. Kechris and Andrew S. Marks,
*Descriptive graph combinatorics*, 2016. https://www.math.ucla.edu/ marks/papers/combinatorics20book.pdf. - Gábor Kun,
*The measurable Hall theorem fails for treeings*, arXiv:2106.02013 (2021). - Andrew S. Marks,
*A determinacy approach to Borel combinatorics*, J. Amer. Math. Soc.**29**(2016), no. 2, 579–600. MR**3454384**, DOI 10.1090/jams/836 - Benjamin D. Miller,
*Ends of graphed equivalence relations. I*, Israel J. Math.**169**(2009), 375–392. MR**2460910**, DOI 10.1007/s11856-009-0015-z - Felix Weilacher,
*Borel edge colorings for finite dimensional groups*, arXiv:2104.14646 (2021). - Felix Weilacher,
*Borel vizing’s theorem for 2-ended groups*, arXiv:2101.12740v1 (2021). - Felix Weilacher,
*Measure asymptotic separation index and hyperfiniteness*, 2021. https://www.math.cmu.edu/f̃weilach/measure_asi_and_hyperfiniteness.pdf. - Felix Weilacher,
*Descriptive chromatic numbers of locally finite and everywhere two-ended graphs*, Groups Geom. Dyn.**16**(2022), no. 1, 141–152. MR**4424966**, DOI 10.4171/ggd/643

## Bibliographic Information

**Matt Bowen**- Affiliation: Department of Mathematics and Statistics, McGill University, Burneside Hall 1020, Montreal, Quebec H3A 0B9, Canada
- MR Author ID: 1389674
- Email: matthew.bowen2@mail.mcgill.ca
**Felix Weilacher**- Affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Wean Hall 6113, Pittsburgh, Pennsylvania 15213
- MR Author ID: 1394099
- Email: fweilach@andrew.cmu.edu
- Received by editor(s): January 10, 2022
- Received by editor(s) in revised form: September 17, 2022
- Published electronically: July 28, 2023
- Additional Notes: The second author was partially supported by the ARCS foundation, Pittsburgh chapter.
- Communicated by: Vera Fischer
- © Copyright 2023 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**151**(2023), 4991-4996 - MSC (2020): Primary 03E15, 05C70
- DOI: https://doi.org/10.1090/proc/16355