C8.

3 Combinatorics
Sheet 0 — MT21
Introductory questions

There will not be classes on this problem sheet, but solutions will be available on the
course webpage from the end of Week 0.
Part B Graph Theory is not a prerequisite for the course, but we will use a little standard
notation, as well as Hall’s Theorem on matchings in bipartite graphs (this can can be found
in the Part B Graph Theory notes). All graphs below are assumed to be finite.

Questions
1. Let G be a bipartite graph with bipartition (A, B). Suppose that every vertex in G has
the same degree d > 0.
(a) Show that |A| = |B|.
(b) Look up Hall’s theorem. Use this result to prove that G contains a complete
matching.
(c) Show that the edge set of G can be partitioned into d edge-disjoint complete match-
ings.

Solution: For part (a), note that since G is bipartite we can count the edges of G by
summing the degrees in either A or B. This gives
X X
d|A| = dG (a) = e(G) = dG (b) = d|B|.
a∈A b∈B

As d > 0 this implies |A| = |B|.

(b) Given S ⊂ A let Γ(S) := {b ∈ B : ab ∈ E(G) for some a ∈ S} ⊂ B. By Hall’s

theorem in order to prove G has a complete matching from A to B it is enough to show
that |Γ(S)| ≥ |S| for all S ⊂ A. To see this, we will estimate edges between S and Γ(S)
in two ways; this technique is often referred to as ‘double counting’. Note that

d|S| = {(a, b) ∈ S × Γ(S) : ab ∈ E(G)} ≤ d|Γ(S)|.

The equality holds as each a ∈ S has all dG (a) = d neighbours in Γ(S) and the inequality
holds since each b ∈ Γ(S) has at most dG (b) = d neighbours in S. Dividing by d we see
that the conditions of Hall’s theorem hold for G.

Mathematical Institute, University of Oxford Page 1 of 3

Alex Scott: scott@maths.ox.ac.uk
 C8.3 Combinatorics: Sheet 0 — MT21

(c) By induction on d. If d = 1 then the edges of G form a complete matching. We will

prove the result for d ≥ 2 assuming by induction that it holds for smaller degree. From
(b) there is a complete matching M in G. Let G0 denote the graph obtained from G
by deleting the edges of M. All vertices in G0 have degree d − 1 and so the edges of
G0 can be partitioned into d − 1 complete matching M1 , . . . , Md−1 . Combined with M
this gives the required partition.

2. Let P(n) denote the power set of [n] := {1, . . . n}. For A, B ∈ P(n), the symmetric
difference of A and B is A4B := (A \ B) ∪ (B \ A).
(a) Suppose A ⊂ P(n), and there do not exist A, B ∈ A with |A4B| = 1. How large
can |A| be?
(b) For n ≥ 1, give two examples of A with maximal size. Are there any others?

Solution: It may be helpful to note that if two sets have symmetric difference of size
1, then the corresponding vertices in the hypercube are adjacent. (See the introductory
lecture for this correspondence.)
For (a), we define a bipartite graph as follows. Let V = A and let W = P(n) \ A, and
join A ∈ V and B ∈ W if and only if their symmetric difference has size 1. Now note
that every vertex in V has degree n, while every vertex in W has degree at most n.
Double counting the set E of edges, we see that

|A|n = |E| ≤ |B|n, (1)

and so |A| ≤ |B|. We deduce that |A| ≤ |P(n)|/2 = 2n−1 .

For (b), two examples are the sets of even size and the sets of odd size.
These are in fact the only examples. If A is an example with |A| = 2n−1 , then we must
have equality in (1). So every vertex in W has degree n. Now suppose A contains a set
F of even size. If we add or delete an element to F then we get a set F 0 in P(n) \ A;
and if we add or delete an element to F 0 then we get a set F 00 in A again. You can get
between any two sets of even size by changing two elements at a time, so A must contain
all sets of even size (and so no sets of odd size). On the other hand, if A contains no
sets of even size, then it must contain all sets of odd size.


3. Let [n](i) := A ⊂ {1, . . . , n} : |A| = i and suppose that i ≤ n/2. Prove that there is
a bijection f : [n](i) → [n](i) such that A ∩ f (A) = ∅ for every A.

Mathematical Institute, University of Oxford Page 2 of 3

Alex Scott: scott@maths.ox.ac.uk
 C8.3 Combinatorics: Sheet 0 — MT21

Solution: Let’s set up a bipartite graph G = (V, W ). Let V = W = [n](i) , and join
A ∈ V and B ∈ W if A ∩ B = ∅. Since i ≤ n/2, the graph G does have edges;
and it is easy to see that every vertex has the same degree (in fact n−i


i
). We know
from Question 1 that this graph contains a complete matching: use this to define the
mapping.

4. (a) Prove that |P(n)| = 2n .

(b) Suppose a set A ∈ P[n] is selected uniformly at random. Let X denote the random
variable given by X(A) := |A|. Prove that E(X) = n/2 and var(X) = n/4.
(c) Use Chebyshev’s inequality and (b) to show that given  > 0 there is C > 0 such
√
that at least (1 − )2n sets A ⊂ [n] satisfy |A| − n2 ≤ C n.

Solution: (a) The map which sends the vector (x1 , . . . , xn ) ∈ {0, 1}n to the set {i ∈
[n] : xi = 1} ∈ P[n] is a bijection, and so |P[n]| = |{0, 1}n | = 2n .

To see (b), note that X can be written as a sum of indicator random variables X =
P
i∈[n] Xi , where Xi (A) = 1 if i ∈ A and Xi (A) = 0 if i ∈
/ A. We have E(Xi ) = P(i ∈
1
A) = 2
for each i ∈ [n] and so linearity of expectation gives
X X n
E(X) = E( Xi ) = E(Xi ) = .
2
i∈[n] i∈[n]

To see the variance calculation recall that

 X X  n2
2 2
var(X) = E(X ) − E(X) = E ( Xi )( Xj ) −
4
i∈[n] j∈[n]
X   X   n2
= E Xi2 + E Xi Xj −
4
i∈[n] i,j∈[n]:i6=j

1 1 n2 n
=n· + n(n − 1) · − = .
2 4 4 4
1 1
Here we used E(Xi2 ) = E(Xi ) = 2
and E(Xi Xj ) = P(i, j ∈ A) = 4
for i 6= j.

For (c) note that for any t > 0 by Chebyshev’s inequality we have
 n    var(X) n
P |A| − ≥ t = P X − E(X) ≥ t ≤ 2
= 2.
2 t 4t
If we set t = Cn1/2 where C = −1/2 /2 then gives P |A| − n2 ≥ t ≤ . Since the sets

were selected uniformly at random, this is equivalent to the statement that at most 2n
n
sets A ∈ P[n] satisfy |A| − 2
≥ t.

Mathematical Institute, University of Oxford Page 3 of 3

Alex Scott: scott@maths.ox.ac.uk