Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-06T04:40:30.806Z Has data issue: false hasContentIssue false
  • English
  • Français

MEASURABLE PERFECT MATCHINGS FOR ACYCLIC LOCALLY COUNTABLE BOREL GRAPHS

Published online by Cambridge University Press:  21 March 2017

CLINTON T. CONLEY  and
BENJAMIN D. MILLER
CLINTON T. CONLEY
Affiliation:
DEPARTMENT OF MATHEMATICAL SCIENCES CARNEGIE MELLON UNIVERSITY PITTSBURGH, PA 15213, USAE-mail: clintonc@andrew.cmu.eduURL: http://www.math.cmu.edu/math/faculty/conley
BENJAMIN D. MILLER
Affiliation:
KURT GÖDEL RESEARCH CENTER FOR MATHEMATICAL LOGIC UNIVERSITÄT WIEN WÄHRINGER STRASSE 25 1090 WIEN, AUSTRIAE-mail: benjamin.miller@univie.ac.atURL: http://www.logic.univie.ac.at/benjamin.miller
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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.

Keywords

Primary 03E1528A05Secondary 05C15Marriagematchingmeasurable
Type
Articles
Information
The Journal of Symbolic Logic , Volume 82 , Issue 1 , March 2017 , pp. 258 - 271
Copyright
Copyright © The Association for Symbolic Logic 2017 

References

REFERENCES

Csóka, E. and Lippner, G., Invariant random matchings in Cayley graphs, preprint available at http://arxiv.org/abs/1211.2374.Google Scholar
Conley, C. T. and Miller, B. D., A bound on measurable chromatic numbers of locally finite Borel graphs, Mathematical Research Letters, preprint available at http://www.logic.univie.ac.at/ benjamin.miller, to appear.Google Scholar
Dougherty, R. L., Jackson, S. C., and Kechris, A. S., The structure of hyperfinite Borel equivalence relations . Transaction of the American Mathematical Society, vol. 341 (1994), no. 1, pp. 193–225.Google Scholar
Harrington, L. A., Kechris, A. S., and Louveau, A., A Glimm-Effros dichotomy for Borel equivalence relations . Journal of American Mathematical Society, vol. 3 (1990), no. 4, pp. 903–928.Google Scholar
Hjorth, G. and Miller, B. D., Ends of graphed equivalence relations. II . Israel Journal of Mathematics, vol. 169 (2009), pp. 393–415.Google Scholar
Jackson, S., Kechris, A. S., and Louveau, A., Countable Borel equivalence relations . Journal of Mathematical Logic, vol. 2 (2002), no. 1, pp. 1–80.Google Scholar
Kechris, A. S., Classical Descriptive Set Theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995.CrossRefGoogle Scholar
Kechris, A. S. and Marks, A. S., Descriptive graph combinatorics, available at http://www.its.caltech.edu/∼marks/.Google Scholar
Kechris, A. S. and Miller, B. D., Topics in Orbit Equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004.Google Scholar
Kechris, A. S., Solecki, S., and Todorcevic, S., Borel chromatic numbers . Advances in Mathematics, vol. 141 (1999), no. 1, pp. 1–44.CrossRefGoogle Scholar
Lyons, R. and Nazarov, F., Perfect matchings as IID factors on non-amenable groups . European Journal of Combinatorics, vol. 32 (2011), no. 7, pp. 1115–1125.Google Scholar
Marks, A. S., A determinacy approach to Borel combinatorics , Journal of the American Mathematical Society, vol. 29 (2016), pp. 579–600.Google Scholar
Miller, B. D., The graph-theoretic approach to descriptive set theory . Bulletin of Symbolic Logic, vol. 18 (2012), no. 4, pp. 554–575.Google Scholar
Marks, A. S. and Unger, S., Baire measurable paradoxical decompositions via matchings , Advances in Mathematics, vol. 289 (2016), pp. 397–410.CrossRefGoogle Scholar