Systems of distinct representatives
Sharad S. Sane · Texts and readings in mathematics · 2013
In this last chapter, we deal with a question which is very much combinatorial in nature but is qualitatively very different from the kind of questions we dealt with and the combinatorial tools we developed in all the earlier chapters. The problem is the following. A (professional) matchmaker has a list of some boys and some girls who have approached him. Looking at their likings and disliking, he has formed a compatibility or suitability graph that declares a boy-girl pair suitable (for matching) or not suitable. Compatibility is always to be taken on a two-way basis (giving rise to a bipartite graph). The matchmaker wishes to marry off as many boys as he can. Suppose we have m boys and n girls. Then an obvious condition, for all the boys to get married, is that n ≥ m since there must be at least m girls available to marry all the m boys. Moreover, every boy must be suitable for at least one girl (else he cannot be married off). The list of girls suitable for at least one of the two boys must have at least two girls (else there would be a tie and only one of the two boys can get married). In general, given any subset of k boys, the list of all the girls suitable to at least one of the k boys must have at least k girls. What turns out to be true is that this simple looking necessary condition is also sufficient to marry off all the m boys (Theorem 16.1.3). This chapter is organized as follows. In this first Section, we prove the standard form of P. Hall’s theorem on the existence of a system of distinct representatives along with a defect version of this theorem. In Section 16.2, we translate these results in the convenient set up of bipartite graphs.