MEASURABLE PERFECT MATCHINGS FOR ACYCLIC LOCALLY COUNTABLE BOREL GRAPHS

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 a...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2017-03, Vol.82 (1), p.258-271, Article 258
Main Authors: CONLEY, CLINTON T., MILLER, BENJAMIN D.
Format: Article
Language:English
Subjects:
Logic
Mathematics
Philosophy
Structuralism
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 μ-hyperfinite equivalence relations admit μ-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.
ISSN:0022-4812
1943-5886
DOI:10.1017/jsl.2016.44