Measurable perfect matchings for acyclic locally countable Borel graphs

DOI10.1017/JSL.2016.44zbMATH Open1496.03186arXiv2002.09653OpenAlexW3102767982MaRDI QIDQ5738201FDOQ5738201

Authors: Clinton T. Conley, Benjamin D. Miller 

Publication date: 1 June 2017

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Abstract: We characterize the structural impediments to the existence of Borel perfect matchings for acyclic locally countable Borel graphs admitting a Borel selection of finitely many ends from their connected components. In particular, this yields the existence of Borel matchings for such graphs of degree at least three. As a corollary, it follows that acyclic locally countable Borel graphs of degree at least three generating $mu$-hyperfinite equivalence relations admit $mu$-measurable matchings. We establish the analogous result for Baire measurable matchings in the locally finite case, and provide a counterexample in the locally countable case.

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

Recommendations

• Borel combinatorics of locally finite graphs
• Hyperfiniteness and Borel combinatorics
• A bound on measurable chromatic numbers of locally finite Borel graphs
• Baire measurable paradoxical decompositions via matchings
• Borel chromatic numbers

zbMATH Keywords

matchingmarriagemeasurable matching

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Classes of sets (Borel fields, (sigma)-rings, etc.), measurable sets, Suslin sets, analytic sets (28A05) Descriptive set theory (03E15)

Cites Work

• Title not available (Why is that?)
• Topics in orbit equivalence
• The Structure of Hyperfinite Borel Equivalence Relations
• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• COUNTABLE BOREL EQUIVALENCE RELATIONS
• Borel chromatic numbers
• The graph-theoretic approach to descriptive set theory
• Perfect matchings as IID factors on non-amenable groups
• A determinacy approach to Borel combinatorics
• Baire measurable paradoxical decompositions via matchings
• Ends of graphed equivalence relations. II
• A bound on measurable chromatic numbers of locally finite Borel graphs

Cited In (7)

• Definable Kőnig theorems
• Hyperfiniteness and Borel combinatorics
• Symmetric measures, continuous networks, and dynamics
• Borel combinatorics of locally finite graphs
• One-ended spanning trees and definable combinatorics
• A determinacy approach to Borel combinatorics
• Measurable Hall's theorem for actions of abelian groups

This page was built for publication: Measurable perfect matchings for acyclic locally countable Borel graphs

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