Type: Seminar

Distribution: World

Expiry: 17 Apr 2015

Auth: seangard@cpe-58-173-10-43.ecxf2.cht.bigpond.net.au (sgar9702) in SMS-WASM

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.