Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-20T00:42:21.169Z 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: [email protected]: 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: [email protected]: http://www.logic.univie.ac.at/benjamin.miller
Get access Rights & Permissions [Opens in a new window]

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 μ-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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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