arXiv:1607.07426v1 [math.GR] 25 Jul 2016

Symmetric Graphs have symmetric Matchings
Jan Fricke
November 8, 2017
Abstract
Assume that there is a free group action of automorphisms on a bipartite graph. If there is a perfect matching on the factor graph, then
obviously there is a perfect matching on the graph. Surprisingly, the reversed is also true for amenable groups: if there is a perfect matching on
the graph, there is also a perfect matching on the factor graph, i. e. a
group invariant (“symmetric”) perfect matching on the graph.

1

Introduction

In 2007 we had an interesting discussion about a problem that somehow points
to Erdős. Take Z2 in R2 and rotate that by 45◦ . Is there a bijection f between
the points of the original lattice and the rotated lattice, such that the distance
between x and f (x) is bounded? We could confirm that (and that was already
known), but is spurred us to find the smallest bound. Klaus Nagel found a
nice construction of a bijection, and
√ in a talk in July 2008 he proved that this
one has the best bound, which is 5 · sin π8 ≈ 0.8557. Unfortunately, he never
published that, and I made no notices.
Independent from that I tried to analyze the dependence of that bound from
rotation angle. And, there are in fact two qualitatively different cases. If the
rotation matrix is irrational, the “twin lattice” is aperiodic, and the bound
doesn’t change if one of the lattices is translated. If the rotation matrix is
rational, the “twin lattice” is periodic, and the bound depends on the rotation
center. Nevertheless there is some continuous dependence of that bound from
the rotation angle, and it is a nice fractal function. Since I cannot prove all of
that it is still unpublished, but I will write a survey paper soon.
In doing numerical experiments on that problem, I faced the problem of finding
a matching in an infinite but periodic bipartite graph. So I only considered
periodic matchings which could be done by the well-known Hopcroft-Karp algorithm. But does that always work? Consider the following graph with a rotation
symmetry:

1

It has two different perfect matchings, but none of them has the rotation symmetry.
So I was thinking about that in 2009 while skiing at the Kvitfjell in Norway,
when I found out, that it works on bipartite graphs using the Theorem of Hall,
because the “boundary” of a suitable finite subset of Z2 is “small” relative to
the “interior”. So I could prove a general result for groups with subexponential
growth. I suspected that it has something to do with amenability and unsuccessful tried to find a counterexample for the free group of two generators. So
it remained unpublished.
In April 2016 I wanted to present that proof in a lecture, and suddenly I found
the slight modification of the proof for showing it for all amenable groups, and
the paradoxical decomposition gave me the right hint for counterexamples for
all non-amenable groups. You will find that proof and the counterexamples in
the last section. In the sections in between I collect the well-known facts about
the Theorem of Hall (section 2), define symmetry of a bipartite graph and the
factor graph (section 3), and cite equivalent characterizations of amenability
and a slight modification of one of them (section 4).
I want to thank Rainer Rosenthal, who still patiently waits for Klaus Nagel’s
paper and my survey paper.

2

Matchings

A bipartite graph (A, B, E) is a pair of sets A and B with a subset E ⊆ A × B.
The elements of A and B are vertices, the elements of E are edges. For each
subset X ⊆ A we define E(X) = {y ∈ B | (x, y) ∈ E} and for each Y ⊆ B we
define E(Y ) = {x ∈ A | (x, y) ∈ E}. Such a bipartite graph is called locally
finite, if for any finite X ⊆ A also E(X) is finite, and for any finite Y ⊆ B also
E(Y ) is finite. (Equivalently, for any x ∈ A and y ∈ B the sets E({x}) and
E({y}) are finite.)
A bipartite graph (A, B, E) fulfills the left Hall condition, if |X| ≤ |E(X)| for
any finite X ⊆ A, and the right Hall condition, if |Y | ≤ |E(Y )| for any finite
Y ⊆ B. It fulfills the Hall condition, if the left and right Hall condition are
fulfilled.
A matching M of a bipartite graph is a subset M ⊆ E, such that for all
(x1 , y1 ), (x2 , y2 ) ∈ M there is (x1 , y1 ) = (x2 , y2 ) whenever x1 = x2 or y1 = y2 .
Define A(M ) = {x ∈ A | ∃y ∈ B : (x, y) ∈ M } and B(M ) = {y ∈ B | ∃x ∈ A :
2

(x, y) ∈ M }. A matching M is called perfect, if A(M ) = A and B(M ) = B.

Theorem 2.1 (Hall). For a locally finite bipartite graph there are equivalent:
1. The graph fulfills the Hall condition.
2. The graph has a perfect matching.

3

Symmetry

Definition 3.1. Let G be a group and (A, B, E) a bipartite graph. Then the
graph is called G-symmetric, if
• G acts free on A,
• G acts free on B,
• (x, y) ∈ E ⇐⇒ (gx, gy) ∈ E for all x ∈ A, y ∈ B and g ∈ G.
It is called proper G-symmetric, if over-more
• (x, y) ∈ E and (gx, y) ∈ E implies g is the identity, or equivalently
• (x, y) ∈ E and (x, gy) ∈ E implies g is the identity.

Definition 3.2. A matching M on a G-symmetric bipartite graph is called
G-symmetric, if (x, y) ∈ M implies (gx, gy) ∈ M for any g ∈ G.
A G-symmetric matching can also be described by a matching on some factor
graph:
Definition 3.3. Let (A, B, E) a G-symmetric bipartite graph. Then the factor
graph (Ã, B̃, Ẽ) is defined by:
• Ã = A/G = {Gx | x ∈ A},
• B̃ = B/G = {Gy | y ∈ B},
• Ẽ = {(Gx, Gy) | (x, y) ∈ E}.

Lemma 3.4. If (A, B, E) is locally finite, then also (Ã, B̃, Ẽ) is locally finite.
Proof. Let (A, B, E) be locally finite. Then
Ẽ({Gx}) = {Gy | (Gx, Gy) ∈ Ẽ} = {Gy | (gx, y) ∈ E and g ∈ G}

= {Gy | (x, g −1 y) ∈ E and g ∈ G} = {Gy ′ | (x, y ′ ) ∈ E},

hence finite. The same holds for Ẽ({Gy}).
Proposition 3.5. The map M 7→ M̃ = {(Gx, Gy) | (x, y) ∈ M } is a surjection
between the G-symmetric matchings M of (A, B, E) and the matchings M̃ of
(Ã, B̃, Ẽ). Is (A, B, E) even proper G-symmetric this map is a bijection. Overmore, M is perfect if and only if M̃ is perfect.
3

4

Amenable groups

There are some equivalent definitions of amenable groups using means on groups
or invariant probability measures. Since that properties doesn’t matter here, we
just choose that one:
Definition 4.1. A group G is called amenable, if there is an invariant finitely
additive probability measure on G.
The property “amenable” is equivalent to some other nice properties of the
group. In particular, we need the Følner condition and the paradoxical decomposition.
Definition 4.2. For a group G note by F the family of all non-empty finite
subsets.
A group G satisfies the Følner condition, if for any ε > 0 and any U ∈ F there
is a F ∈ F with |F \ F g| ≤ ε · |F | for any g ∈ U .

A group G has a paradoxical decomposition, if there is a F ∈ F and a decomposition
G
G
G
G
G=
Ag =
Bg =
Ag g ⊔
Bg g.
g∈F

g∈F

g∈F

g∈F

Theorem 4.3 (Følner, Tarski). For a group G are equivalent:
1. G is amenable.
2. G satisfies the Følner condition.
3. G has no paradoxical decomposition.
Both of that properties are interesting here, but we need a slight modification
of the Følner condition:
Proposition 4.4. A group G satisfies the Følner condition if and only if
inf

F ∈F

|F U |
=1
|F |

for any U ∈ F , where F is the family of all non-empty finite subsets of G.
|F U|
F ∈F |F |

Proof. Note that |F | ≤ |F U | for all F, U ∈ F , so inf

≥ 1.

“⇒”: Let U ∈ F and ε > 0. By the Følner condition there is a set F ∈ F such
that
ε
· |F |
|F \ F g| ≤
|U |

4

for any g ∈ U . Since |F | = |F g| we have |F \ F g| = |F g \ F |, hence


[
[
|F U \ F | = 
F g \ F =
(F g \ F ) ≤ ε · |F |.
g∈U

g∈U

Now
|F U | = |(F U \ F ) ∪ (F U ∩ F )| = |F U \ F | + |F U ∩ F | ≤ ε · |F | + |F |
implies the assertion.
“⇐”: Let U ∈ F and ε > 0. Then there is a set F ∈ F such that
|F (U ∪ {e})|/|F | < 1 + ε.
For any g ∈ U we have
|F (U ∪ {e})| = |F U ∪ F | = |(F U \ F ) ∪ F | = |F U \ F | + |F | ≥ |F g \ F | + |F |.
This implies |F \ F g| = |F g \ F | < ε · |F |.
Example 4.5. Finite groups are amenable.
Solvable groups are amenable, in particular abelian and nilpotent groups are
amenable.
Any subgroup of an amenable group is amenable.
If U is an amenable normal subgroup of G, and G/U is amenable too, then G
is amenable.
Any group with subexponential growth is amenable.
Example 4.6. Any free group on at least two generators is not amenable.
Any group that has a non-amenable subgroup is not amenable, e.g. SL(n, Z) for
n ≥ 2, since it has a subgroup isomorphic to the free group on two generators.

5

Symmetric graphs have symmetric matchings

Now we can formulate and proof the main result:
Theorem 5.1. Let (A, B, E) a locally finite G-symmetric bipartite graph, where
G is amenable. Then the following properties are equivalent.
1. (A, B, E) has a perfect matching.
2. (A, B, E) has a perfect G-symmetric matching.
Since the reverse direction is obvious, there is only one direction to show.
5

Proof. Let X̃ ⊆ Ã be some finite subset in the factor graph. Set Ỹ = Ẽ(X̃).
Then there are representing sets X ⊆ A and Y ⊆ B, i.e.
X̃ = {Gx | x ∈ X},

Ỹ = {Gy | y ∈ Y },

|X| = |X̃|,

|Y | = |Ỹ |.

Now for any pair (x, y) ∈ E(X) there is some g ∈ G with gy ∈ Y , so there is a
U ∈ F with E(X) ⊆ U Y . Since E is G-invariant, we conclude E(F X) ⊆ F U Y
for any F ∈ F .

By the left Hall condition, the free action of G, and the modified Følner condition
this implies
|F | · |X| ≤ |F U | · |Y | =⇒ |X| ≤

|F U |
· |Y | =⇒ |X| ≤ |Y | =⇒ |X̃| ≤ |Ỹ |
|F |

which proves the left Hall condition in the factor graph. The right Hall condition
is shown the same way, so the assertion is proved.
Proposition 5.2. If G is not amenable, then there is a locally finite proper
G-symmetric bipartite graph (A, B, E) with a perfect matching, that admits no
G-symmetric perfect matching.
Proof. By the Tarski Theorem there is a paradoxical decomposition of G. This
can be used to construct such a G-symmetric bipartite graph: Set A = G,
B = G × {1, 2}, E = {(xg, (x, i)) | x ∈ G, g ∈ F, i ∈ {1, 2}}, and the group
action is the group composition. Then there is a perfect matching
M = {(xg, (x, 1)) | g ∈ F, x ∈ Ag } ∪ {(xg, (x, 2)) | g ∈ F, x ∈ Bg }.
But the factor graph Ã = {G}, B̃ = {G} × {1, 2}, Ẽ = Ã × B̃ has obviously no
perfect matching.
It’s easy to see that this example is not proper G-symmetric, so we have to
modify it slightly. Each vertex has to be replaced by |F | copies of itself, and
the edges have to be twisted a little bit.
Let ϕ : F × F → F be bijective if any of the arguments is fixed. One can
get such a function for instance by the group composition in a cyclic group of
order |F |, and map the elements bijectively to F . Now we set A = G × F ,
B = G × F × {1, 2}, and
E = {((xg, ϕ(g, h)), (x, h, i)) | g, h ∈ F, x ∈ G, i ∈ {1, 2}}.
G acts again by left multiplication on the G-component of A and B. This
G-symmetry is proper, because
((zxg, ϕ(g, h)), (x, h, i)) = ((x′ g ′ , ϕ(g ′ , h′ )), (x′ , h′ , i′ ))
for some z ∈ G implies x = x′ , h = h′ , i = i′ , and by injectivity of g 7→ ϕ(g, h)
also g = g ′ , hence z = e.
6

A perfect matching is given by
M ={((xg, ϕ(g, h)), (x, h, 1)) | g, h ∈ F, x ∈ Ag }∪
{((xg, ϕ(g, h)), (x, h, 2)) | g, h ∈ F, x ∈ Bg } ⊆ E.
F
F
F
F
Bg g
Ag g ⊔
Bg any vertex of B, and since G =
Ag =
Since G =
g∈F

g∈F

g∈F

g∈F

and h 7→ ϕ(g, h) is bijective, any vertex of A belongs to exactly one edge in M .
Hence, (A, B, E) admits a perfect matching.
Now take a look at the factor graph. We have Ã = {G}×F , B̃ = {G}×F ×{1, 2},
Ẽ = {((G, ϕ(g, h)), (G, h, i)) | g, h ∈ F, i ∈ {1, 2}},
which is the complete bipartite graph with |F | and 2|F | vertices. That one has
obviously no perfect matching.

References
[1] T. Ceccherini-Silberstein, M. Coornaert: Cellular Automata and Groups.
Springer 2010.

7

