A mathematical result that every matchmaker should be aware of is Hall’s marriage theorem, which was obtained by Philip Hall and published in a five-page paper, entitled ‘On Representatives of Subsets’, in the Journal of the London Mathematical Society in 1935. It gets its name from the fact that it can be described as follows.
Let G be a group of people. We say that G has property P if it is possible to marry off (monogamously) all women in G to men in G. It is assumed that a woman can be married off to a man if both are willing to marry each other; let us call one (the man/woman) a ‘good connection’ of the other.
The theorem tells us that G has property P if, and only if, G has the following property Q: for every subset S of the set of women in G, the number of men that have some good connection in S is at least the number of women in S.
In other words, the two properties are equivalent, that is, they imply each other (if one holds, then the other holds). The fact that P implies Q is straightforward, but the converse is not.
It is assumed that a woman can be married off to a man if both are willing
The following is the formal version. Let A₁ , A₂, …, Aⁿ be sets, each having a finite number of members. It is desired to choose an object from each of these sets in such a way that no object chosen from one set is the same one chosen from another set; if this is possible, then we call the n chosen objects distinct representatives of A₁, A₂, …, An (each object represents only one set).
The theorem says that A₁, A₂, …, An have distinct representatives if, and only if, for each instance of choosing some of the sets A₁, A₂, …, Aⁿ (2ⁿ instances!), the number of objects that belong to at least one of the chosen sets is at least the number of chosen sets.
It is straightforward that the two versions imply each other as follows. Let woman 1, woman 2, ..., woman n be the women in G, and, for each i from 1 to n, let Aⁱ be the set of good connections of woman i.
The result is also referred to as the Kőnig-Hall Theorem as Dénes Kőnig proved an equivalent result in 1931 (two results are equivalent if they imply each other). Using the informal marriage setting above, Kőnig had also proved that if the men and women happen to have the same number of good connections, then there are as many men as women and, more importantly, there is a way of pairing up all the men and women. He established this result in 1914 and published it in 1916.
In addition to Kőnig’s theorem, there are other remarkably powerful theorems in combinatorial mathematics that are equivalent to Hall’s marriage theorem and hence to each other, including the Kőnig-Egervary theorem, Menger’s theorem, the max-flow min-cut theorem, the Birkhoff-Von Neumann theorem, and Dilworth’s theorem.
A national STEM Career Expo will be held at Esplora for all families on January 25 to 26 from 10am to 6pm. Children and adults can play with experiments, meet professionals from all over Malta and explore their potential. The event is organised by MCST, UM and Mcast with the support of Mede and the STEM Engagement Working Group. The author of this page will have a stand together with other members of the Department of Mathematics (Faculty of Science, UM).
Peter Borg is an associate professor at the Department of Mathematics within the Faculty of Science of the University of Malta.
http://staff.um.edu.mt/peter.borg
Sound bites
• Let n and k be integers such that 2 ≤ k ≤ n (≤ means ‘is less than or equal to’). We call a sum a₁ + a₂ + ... + aᵏ a k-length partition of n if a₁, a₂, ..., aᵏ are positive integers such that a₁ ≤ a₂ ≤ ... ≤ aᵏ and n = a₁ + a₂ + ... + aᵏ (for example, 2 + 2 + 4 + 7 is a 4-length partition of 15). We call ai the i-th part of the sum a₁ + a₂ + ... + aᵏ. Let P be the set of k-length partitions of n. We say that two partitions a1 + a₂ + ... + aᵏ and b₁ + b₂ + ... + bᵏ strongly intersect if aᵢ = bᵢ for some i. We call a subset A of P strongly intersecting if every two partitions in A strongly intersect. Let P(1) be the set of partitions in P whose first part is 1. The author proved that P(1) is a largest strongly intersecting subset of P, and uniquely so if, and only if, 4 ≤ k, or k = 3 ≤ n and n is not one of 6, 7, and 8, or k = 2 ≤ n ≤ 3. The following is the reference to the author’s paper: P. Borg, Strongly intersecting integer partitions, Discrete Mathematics 336 (2014), 80-84.
For more sound bites, listen to Radio Mocha: Mondays at 7pm on Radju Malta and Thursdays at 4pm on Radju Malta 2 (https://www.fb.com/RadioMochaMalta)
Did you know?
• The volume of a pizza with radius z and height a is pi x z x z x a, where pi is the mathematical constant 3.14159… given by the ratio of a circle’s circumference to its diameter.
• In the 1760s, Johann Heinrich Lambert proved that pi is an irrational number, meaning that it cannot be written as an integer divided by an integer. It follows that its decimal representation not only is infinite but never settles into a repetitive pattern (can you see why?).
• In 1882, Ferdinand von Lindemann proved that pi is also a transcendental number, meaning that it is not the root of a polynomial with rational coefficients. This property is stronger than (i.e. implies) the irrationality property.
For more trivia, see: www.um.edu.mt/think