1Hall's theorem
III Combinatorics
1 Hall’s theorem
We shall begin with a discussion of Hall’s theorem. Ideally, you’ve already met
it in IID Graph Theory, but we shall nevertheless go through it again.
Definition
(Bipartite graph)
.
We say
G
= (
X, Y
;
E
) is a bipartite graph with
bipartition
X
and
Y
if (
X t Y, E
) is a graph such that every edge is between a
vertex in X and a vertex in Y .
We say such a bipartite graph is (
k, `
)-regular if every vertex in
X
has degree
k
and every vertex in
Y
has degree
`
. A bipartite graph that is (
k, `
)-regular for
some k, ` ≥ 1 is said to be biregular.
Definition
(Complete matching)
.
Let
G
= (
X, Y
;
E
) be a bipartite graph
with bipartition
X
and
Y
. A complete matching from
X
to
Y
is an injection
f : X → Y such that x f(x) is an edge for every x ∈ X.
Hall’s theorem gives us a necessary and sufficient condition for the existence
of a complete matching. Let’s try to first come up with a necessary condition.
If there is a complete matching, then for any subset
S ⊆ X
, we certainly have
|
Γ(
S
)
| ≥ |S|
, where Γ(
S
) is the set of neighbours of
S
. Hall’s theorem says this
is also sufficient.
Theorem
(Hall, 1935)
.
A bipartite graph
G
= (
X, Y
;
E
) has a complete match-
ing from X to Y if and only if |Γ(S)| ≥ |S| for all S ⊆ X.
This condition is known as Hall’s condition.
Proof.
We may assume
G
is edge-minimal satisfying Hall’s condition. We show
that
G
is a complete matching from
X
to
Y
. For
G
to be a complete matching,
we need the following two properties:
(i) Every vertex in X has degree 1
(ii) Every vertex in Y has degree 0 or 1.
We first examine the second condition. Suppose
y ∈ Y
is such that there
exists edges
x
1
y, x
2
y ∈ E
. Then the minimality of
G
implies there are sets,
X
1
, X
2
⊆ X
such that
x
i
∈ X
i
such that
|
Γ(
X
i
)
|
=
|X
i
|
and
x
i
is the only
neighbour of y in X
i
.
Now consider the set
X
1
∩ X
2
. We know Γ(
X
1
∩ X
2
)
⊆
Γ(
X
1
)
∩
Γ(
X
2
).
Moreover, this is strict, as y is in the RHS but not the LHS. So we have
Γ(X
1
∩ X
2
) ≤ |Γ(X
i
) ∩ Γ(X
2
)| − 1.
But also
|X
1
∩ X
2
| ≤ |Γ(X
1
∩ X
2
)|
≤ |Γ(X
1
) ∩ Γ(X
2
)| − 1
= |Γ(X
1
)| + |Γ(X
2
)| − |Γ(X
1
) ∪ Γ(X
2
)| − 1
= |X
1
| + |X
2
| − |Γ(X
1
∪ X
2
)| − 1
≤ |X
1
| + |X
2
| − |X
1
∪ X
2
| − 1
= |X
1
∩ X
2
| − 1,
which contradicts Hall’s condition.
One then sees that the first condition is also satisfied — if
x ∈ X
is a vertex,
then the degree of
x
certainly cannot be 0, or else
|
Γ(
{x}
)
| < |{x}|
, and we see
that
d
(
x
) cannot be
>
1 or else we can just remove an edge from
x
without
violating Hall’s condition.
We shall now describe some consequences of Hall’s theorem. They will
be rather straightforward applications, but we shall later see they have some
interesting consequences.
Let
A
=
{A
1
, . . . , A
m
}
be a set system. All sets are finite. A set of distinct
representatives of A is a set {a
1
, . . . a
m
} of distinct elements a
i
∈ A
i
.
Under what condition do we have a set of distinct representatives? If we
have one, then for any I ⊆ [m] = {1, 2, . . . , m}, we have
[
i∈I
A
i
≥ |I|.
We might hope this is sufficient.
Theorem. A has a set of distinct representatives iff for all B ⊆ A, we have
[
B∈B
B
≥ |B|.
This is an immediate consequence of Hall’s theorem.
Proof.
Define a bipartite graph as follows — we let
X
=
A
, and
Y
=
S
i∈[m]
A
i
.
Then draw an edge from
x
to
A
i
if
x ∈ A
i
. Then there is a complete matching
of this graph iff
A
has a set of distinct representations, and the condition in the
theorem is exactly Hall’s condition. So we are done by Hall’s theorem.
Theorem.
Let
G
= (
X, Y
;
E
) be a bipartite graph such that
d
(
x
)
≥ d
(
y
) for
all x ∈ X and y ∈ Y . Then there is a complete matching from X to Y .
Proof.
Let
d
be such that
d
(
x
)
≥ d ≥ d
(
y
) for all
x ∈ X
and
y ∈ Y
. For
S ⊆ X
and
T ⊆ Y
, we let
e
(
S, T
) be the number of edges between
S
and
T
. Let
S ⊆ X
,
and T = Γ(S). Then we have
e(S, T) =
X
x∈S
d(x) ≥ d|S|,
but on the other hand, we have
e(S, T) ≤
X
y ∈T
d(y) ≤ d|T |.
So we find that |T | ≥ |S|. So Hall’s condition is satisfied.
Corollary.
If
G
= (
X, Y
;
E
) is a (
k, `
)-regular bipartite graph with 1
≤ ` ≤ k
,
then there is a complete matching from X to Y .
Theorem. Let G = (X, Y ; E) be biregular and A ⊆ X. Then
|Γ(A)|
|Y |
≥
|A|
|X|
.
Proof. Suppose G is (k, `)-regular. Then
k|A| = e(A, Γ(A)) ≤ `|Γ(A)|.
Thus we have
|Γ(A)|
|Y |
≥
k|A|
`|Y |
.
On the other hand, we can count that
|E| = |X|k = |Y |`,
and so
k
`
=
|Y |
|X|
.
So we are done.
Briefly, this says biregular graphs “expand”.
Corollary.
Let
G
= (
X, Y
;
E
) be biregular and let
|X| ≤ |Y |
. Then there is a
complete matching of X into Y .
In particular, for any biregular graph, there is always a complete matching
from one side of the graph to the other.
Notation.
Given a set
X
, we write
X
(r)
for the set of all subsets of
X
with
r
elements, and similarly for X
(≥r)
and X
(≤r)
.
If |X| = n, then |X
(r)
| =
n
r
.
Now given a set
X
and two numbers
r < s
, we can construct a biregular
graph (X
(r)
, X
(s)
; E), where A ∈ X
(r)
is joined to B ∈ X
(s)
if A ⊆ B.
Corollary.
Let 1
≤ r < s ≤ |X|
=
n
. Suppose
|
n
2
− r| ≥ |
n
2
− s|
. Then there
exists an injection f : X
(r)
→ X
(s)
such that A ⊆ f(A) for all A ∈ X
(r)
.
If
|
n
2
− r| ≤ |
n
2
− s|
, then there exists an injection
g
:
X
(s)
→ X
(r)
such that
A ⊇ g(A) for all A ∈ X
(s)
.
Proof. Note that |
n
2
− r| ≤ |
n
2
− s| iff
n
r
≥
n
s
.