Definable Kőnig theorems

DOI10.1090/PROC/16355MaRDI QIDQ6095830zbMATH OpenOpenAlexWikidataFDO

Authors Matthew Bowen, Felix Weilacher

Publication date 8 September 2023

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.10222

Mathematics Subject Classification ID

Descriptive set theory (03E15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Cites work

• A bound on measurable chromatic numbers of locally finite Borel graphs
• A determinacy approach to Borel combinatorics
• Borel chromatic numbers
• Descriptive chromatic numbers of locally finite and everywhere two-ended graphs
• Ends of graphed equivalence relations. I
• Hyperfiniteness and Borel combinatorics
• Kőnig's line coloring and Vizing's theorems for graphings
• Marked groups with isomorphic Cayley graphs but different Borel combinatorics
• Measurable perfect matchings for acyclic locally countable Borel graphs
• Measurable versions of the Lovász local lemma and measurable graph colorings
• Measurable versions of Vizing's theorem

Cited in

(7)

• Effective definability of Kolchin polynomials
• Borel Vizing's theorem for graphs of subexponential growth
• Borel versions of the local lemma and local algorithms for graphs of finite asymptotic separation index
• The uniform Gardner conjecture and rounding Borel flows
• Large-scale geometry of Borel graphs of polynomial growth
• Measurable Vizing's theorem
• Embedding Borel graphs into grids of asymptotically optimal dimension

This page was built for publication: Definable Kőnig theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6095830)