4.1: Prelude to Systems of Distinct Representatives

Last updated
Save as PDF

Page ID: 7159

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Suppose that the student clubs at a college each send a representative to the student government from among the members of the club. No person may represent more than one club; is this possible? It is certainly possible sometimes, for example when no student belongs to two clubs. It is not hard to see that it could be impossible. So the first substantive question is: is there anything useful or interesting we can say about under what conditions it is possible to choose such representatives.

We turn this into a more mathematical situation:

Definition \(\PageIndex{1}\): System of Distinct Representatives (SDR)

Suppose that \(A_1,A_2,\ldots,A_n\) are sets, which we refer to as a set system. A (complete) system of distinct representatives is a set \(\{x_1, x_2, \ldots x_n\}\) such that \(x_i\in A_i\) for all \(i\), and no two of the \(x_i\) are the same. A (partial) system of distinct representatives is a set of distinct elements \(\{x_1, x_2, \ldots x_k\}\) such that \(x_i\in A_{j_i}\), where \(j_1,j_2,\ldots,j_k\) are distinct integers in \([n]\).

In standard usage, "system of distinct representatives'' means "complete system of distinct representatives'', but it will be convenient to let "system of distinct representatives'' mean either a complete or partial system of distinct representatives depending on context. We usually abbreviate "system of distinct representatives'' as sdr.

We will analyze this problem in two ways: combinatorially and using graph theory.