Systems of Distinct Representatives

Definition: Let $A$ be a finite set, and let $\mathcal A = ( A_1, A_2, ..., A_n )$ be a collection of subsets of $A$. A System of Representatives of $\mathcal A$ is a collection of elements $x_1, x_2, ..., x_n$ such that $x_i \in A_i$ for all $i \in \{ 1, 2, ..., n \}$. A Distinct System of Representatives of $\mathcal A$ is a collection of elements $x_1, x_2, ..., x_n$ such that $x_i \neq x_j$ for all $i, j \in \{1, 2, ..., n \}$ and $i \neq j$.

The term "System of Representatives" is often abbreviated as an "SDR" though, we will not use this abbreviation.

For example, consider the finite set:

(1)

\begin{align} \quad A = \{ x_1, x_2, x_4, x_5, x_5 \} \end{align}

Also consider the collection of subsets $\mathcal A = ( A_1, A_2, A_3, A_4, A_5 )$ defined to be $A_1 = \{ x_1, x_2 \}$, $A_2 = \{ x_2, x_3 \}$, $A_3 = \{x_3, x_4 \}$, $A_4 = \{ x_4, x_5 \}$, and $A_5 = \{ x_1, x_5 \}$. If we let $x_1 \in A_1$ represent $A_1$, $x_2 \in A_2$ represent $A_2$, …, $x_5 \in A_5$ to represent $A_5$ then the collection of elements $x_1, x_2, x_3, x_4, x_5$ is a system of representation of $\mathcal A$ - more specifically, a distinct system of representatives of $\mathcal A$.

Alternatively, the collection $x_1, x_2, x_3, x_4, x_1$ is also a system of representatives of $A$ where $x_i \in A_i$ represents $A_i$ for each $i = 1, 2, 3, 4$ and $x_1 \in A_5$ represents $A_5$. In this case, this system of representatives of $\mathcal A$ is not distinct.

We should note that if $\mathcal A = ( A_1, A_2, ..., A_n )$ is a collection of subsets of $A$ then provided that $A_i \neq \emptyset$ for all $i \in \{1, 2, ..., n \}$ then a system of representatives exist for $\mathcal A$. Therefore, systems of representatives alone are not that interesting to study. That said, a system of distinct represents need not exist. For example, consider the following set:

(2)

\begin{align} \quad B = \{y_1, y_2, y_3 \} \end{align}

Also consider the collection of subsets $\mathcal B = ( B_1, B_2 , B_3 )$ where $B_1 =\{ y_1, y_2 \}$, $B_2 = \{ y_1 \}$ and $B_3 = \{ y_2 \}$. The collection of elements $y_1, y_2$ do not form a system of distinct represents of $\mathcal B$.

There are two ways to show this. We note that $B_2$ and $B_3$ are $1$-element sets, so we must choose their sole elements as representatives, i.e., say $y_1 \in B_2$ represents $B_2$ and $y_2 \in B_3$ represents $B_3$. Then for the set $B_1$ we have that either $y_1$ or $y_2$ must represent $B_1$ - but both of those elements already represent other subsets in $\mathcal B$. Another way to show that $y_1, y_2$ do not form a system of distinct representatives of $\mathcal B$ is noticing that we must have at least $3$ distinct elements to form a system of distinct representatives of $\mathcal B$ and $\mid B_1 \cup B_2 \cup B_3 \mid = 2 < 3$.