The measurable Hall theorem fails for treeings

Abstract

We construct, for every $d\ge 3$, a $d$-regular acyclic measurably bipartite graphing that admits no measurable perfect matching, resolving a problem of Kechris and Marks. A dense variant of our construction yields a coupling of two standard Borel probability measure spaces whose support contains no deterministic coupling, though the conditional probabilities of the coupling measure are atomless. This refutes a conjecture of Gurel-Gurevich and Peled.

We refute in this version the conjecture of Gurel-Gurevich and Peled on deterministic couplings besides the Kechris-Marks problem on measurable matchings. We also solve further open questions including separation of local (so-called Locally Checkable Labeling) problems. The method in the previous versions has been extended using Lovász' terminology on flows in measurable graphs