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
[
iI
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
xS
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
.