Chapter 11 - Some combinatorial applications

Summary

Systems of distinct representatives

Let F = (S₁, …, S_n) be a family of subsets of a finite set S. A sequence F = (f₁, …, f_n) of elements of S is called a system of representatives of F if f_i ∈ S_i, for i = 1,2, …, n. If the elements of F are distinct then F is called a system of distinct representatives (SDR) for F.

Example 11.1.1Let S₁={u₂, u₃, u₄}, S₂={u₁, u₂, u₃} and S₃={u₃, u₄, u₅}. Then F = (u₂, u₁, u₃) is an SDR for F = (S₁, S₂, S₃), since u₂ ∈ S₁, u₁ ∈ S₂ and u₃ ∈ S₃.

Many criteria for the existence of systems of representatives, under various restrictions, have been developed (see Mirsky (1971)). Bipartite graphs have proven to be a particularly useful tool in these investigations, since every collection of subsets F can be represented by the bipartite graph G(F) with bipartition (V₁, V₂) where V₁ = {S₁, …, S_n}, V₂ = S and the vertices S_i ∈ V₁ and u ∈ V₂ are joined by an edge if and only if u ∈ S_i. We shall give a few examples of results on SDRs to demonstrate how this representation can be used, which employ a variety of different graph theoretic results. We begin with the principal result in this area, obtained by P. Hall (1935).