UCLA Logic Seminar: Baire measurable paradoxical decompositions via matchings (Andrew Marks)

Today's logic seminar was by Andrew Marks, entitled Baire measurable paradoxical decompositions via matchings. The work, joint with Spencer Unger, showed the following theorem:

Main Result: Suppose a group $\Gamma$ acts on a Polish space $X$ by Borel automorphisms ($x\mapsto \gamma\cdot x$ is Borel for every $\gamma\in \Gamma$. Then if this action has a paradoxical decomposition, it has one where the pieces have the Baire property.

If $a$ is a group action of $\Gamma$ on a space $X$, a paradoxical decomposition of $a$ is a partition of $X$ into finitely many pieces $\{A_1,\ldots, A_n, B_1,\ldots, B_m\}$ such that there exists $\alpha_1,\ldots, \alpha_n, \beta_1,\ldots,\beta_m\in \Gamma$ so that $\alpha_1A_1,\ldots, \alpha_nA_n$ and $\beta_1B_1,\ldots,\beta_mB_m$ each partition $X$.

As an example, the Banach-Tarski paradox corresponds to a paradoxical decomposition of the action of the group of rotations on the unit ball in $\mathbb{R^3}$ (minus the origin, for technical reasons).

The amenable groups, those which have a finitely additive translation invariant probability measure, cannot have paradoxical decompositions of their free actions. Tarski showed that the left translation action of a nonamenable group on itself admits a paradoxical decomposition.

Marczewski asked in 1930 whether there is a Banach-Tarski decomposition using pieces with the Baire Property, which was answered affirmatively by Dougherty-Foreman. Andrew's talk extended this result (with different proof methods) to all nonamenable groups.

Someone in the audience asked whether the Baire decomposition can always use the minimum number of pieces of a paradoxical decomposition. Andrew stated a result of Mycielski that the answer is no, but the present work gives a bound for the number of Baire pieces needed (something like $n^2$, where $n$ is the least number of pieces in any paradoxical decomposition).

To do this, they constructed a graph whose perfect matchings exactly correspond to paradoxical decompositions. Suppose $a$ is an action of a group $\Gamma$ on $X$. Given a finite set $S\subseteq \Gamma$ closed under inverses, form the graph $G_p(a,S)$ with vertex set $\{0,1,2\}\times X$ (three disjoint copies of $X$), where $(i,x)\sim (j,y)$ iff exactly one of $i,j$ is equal to 0 and there is some $s\in S$ such that $sx=y$. The fact that $S$ is closed under inverses makes this relation symmetric.

Then he recalled Hall's theorem: a locally finite bipartite graph has a perfect matching iff for every finite $F$ on one side of the bipartition of $G$, $|N(F)|\ge|F|$ where $N(F)$ is the number of vertices not in $F$ adjacent to a vertex in $F$.

The condition that Hall's theorem shows equivalent to the existence of a perfect matching is called Hall condition.

Laczkovich showed that there is no Borel version of Hall's theorem, and Conley--Kechris found more examples. I had encountered these results earlier: around 2009 during the time of the Conley--Kechris results, I had finished working on a project in (finite) matching theory and became interested in "descriptive" combinatorics, and Kechris shared with me these two papers that gave negative answers to the natural Borel questions for matchings.

But it turns out that if you require a Borel perfect matching on just a Borel $G$-invariant (union of connected components) comeager set, then it can be done while strengthening the Hall condition.

Theorem: Suppose $G$ is a locally finite bipartite Borel graph, and there is $\epsilon>0$ such that for every finite $F$ in one part of this bipartition,
$$|N(F)|\ge (1+\epsilon)|F|$$
then $G$ has a Borel perfect matching on a Borel $G$-invariant comeager set.

In response to a question, Andrew noted that this means "isoperimetric constant is greater than 1". The theorem was proven using nice elementary arguments.

To apply it to the graphs of the form $G_p(a,S)$, for $S$ a finite set of generators witnessing the paradoxical decomposition and closed under inverses, notice that changing $S$ to $S^2$ results in
$|N_{G_p(a,S)}(F)\ge 2|F|$. We may assume $F=\{1,2\}\times F'$, the other case is trivial. Now if $N_{G(a,S)}(\{1,2\}\times F')=\{0\}\times F''$, then
$$|N_{G(a,S^2)}(F)|\ge |N_{G(a,S)}(\{1,2\}\times F'')|$$
$$\ge|\{1,2\}\times F''|$$
$$\ge 2|F''|\ge 2 |F|$$
where the second line follows since $G(a,S)$ satisfied the Hall condition.  This gives the strong Hall condition needed to apply the theorem (with $\epsilon=1$).