  Consider Bernoulli(1/2) percolation on $\mathbb{Z}^d$, and define a perfect
matching between open and closed vertices in a way that is a deterministic
equivariant function of the configuration. We want to find such matching rules
that make the probability that the pair of the origin is at distance greater
than $r$ decay as fast as possible. For two dimensions, we give a matching of
decay $cr^{1/2}$, which is optimal. For dimension at least 3 we give a matching
rule that has an exponential tail. This substantially improves previous bounds.
The construction has two major parts: first we define a sequence of coarser and
coarser partitions of $\mathbb{Z}^d$ in an equivariant way, such that with high
probability the cell of a fixed point is like a cube, and the labels in it are
i.i.d. Then we define a matching for a fixed finite cell, which stabilizes as
we repeatedly apply it for the cells of the consecutive partitions. Our methods
also work in the case when one wants to match points of two Poisson processes,
and they may be applied to allocation questions.
