SUMS: Myerson -- Consequences of a combinatorial theorem

For this week’s SUMS talk we have guest speaker Dr Gerry Myerson, senior lecture at 
Macquarie University. 

Abstract: 
Deal out a pack of cards, face up, into 4 rows of 13 cards each.
Then it is always possible to choose 13 cards, one from each column,
in such a way as to get exactly one king, one queen, one jack, ...,
one ace.

Every square matrix with positive integer entries and all row sums
and all column sums equal can be written as a sum of permutation
matrices (zero-one matrices with a single 1 in each row and in each
column).

In a rectangular array of zeros and ones, the largest number of ones,
no two in the same row or column, equals the smallest number of rows
and columns whose erasure would eliminate all the ones in the array.

Given m rows of numbers, where each row has each of the numbers
1, 2, ..., n exactly once, and where no column has any number
more than once, it is possible to extend the configuration to n rows
with the same property.

For m < n, it is always possible to pair the m-element subsets of
an (m + n)-element set with the n-element subsets in such a way that
each m-element set is paired with a n-element set that contains it.

Given two ways to partition a set of m n people into m committees
of n people each, there is always a set of m people including exactly
one representative of each committee.

These are all consequences of one result, Hall’s Marriage Theorem.
I’ll talk about Hall’s Theorem, and about as many of the consequences
as I can.