Baire Measurable Matchings in Non-Amenable Graphs

Abstract

We prove that every Schreier graph of a free Borel action of a finitely generated non-amenable group admits a Baire measurable perfect matching, and that the Schreier graph of a free computable action of a finitely generated non-amenable group admits a computable perfect matching. These results were previously only known in the bipartite setting. To prove them, we establish variants of Tutte's theorem on perfect matchings in non-bipartite graphs. We also prove that every Borel non-amenable bounded-degree graph with only even degrees admits a Baire measurable balanced orientation.