# 4.E: Systems of Distinct Representatives (Exercises)

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

## 4.1: Existence of SDRs

**Ex 4.1.1** How many different systems of distinct representatives are there for \(A_1=\{1,2\}\), \(A_2=\{2,3\}\), …, \(A_n=\{n,1\}\)?

**Ex 4.1.2** How many different systems of distinct representatives are there for the sets \(A_i=[n]\backslash{i}\), \(i=1,2,\ldots,n\), \(n\ge2\)?

**Ex 4.1.3** Suppose the set system \(A_1,A_2,\ldots,A_n\) has an **sdr**, and that \(x\in A_i\). Show the set system has an **sdr** containing \(x\). Show that \(x\) cannot necessarily be chosen to represent \(A_i\).

**Ex 4.1.4** Suppose the set system \(A_1,A_2,\ldots,A_n\) satisfies \(|\bigcup_{j=1}^k A_{i_j}|\ge k+1\) for every \(1\le k< n\) and \(\{i_1,i_2,\ldots,i_k\}\subseteq [n]\), and that \(x\in A_i\). Show the set system has an **sdr** in which \(x\) represents \(A_i\).

**Ex 4.1.5** An \(m\times n\) chessboard, with \(m\) even and both \(m\) and \(n\) at least 2, has one white and one black square removed. Show that the board can be covered by dominoes.

## 4.2: Partial SDRs

**Ex 4.2.1** Find the size of a maximum **sdr** for $$A_1=\{a,b,c\}, A_2=\{a,b,c,d,e\}, A_3=\{a,b\}, A_4=\{b,c\}, A_5=\{a\}, A_6=\{a,c,e\}.$$ Justify your answer.

## 4.3: Latin Squares

**Ex 4.3.1** Show that there is only one reduced Latin square of order 3.

**Ex 4.3.2** Verify that the isotopy relation is an equivalence relation.

**Ex 4.3.3** Find all 4 reduced Latin squares of order 4. Show that there are at most 2 isotopy classes for order 4.

**Ex 4.3.4** Show that the second set system defined in example 4.3.7 has an **sdr** as claimed.

**Ex 4.3.5** Show that there are no orthogonal Latin squares of order 2.

**Ex 4.3.6** Find the two orthogonal Latin squares of order \(5\) as described in theorem 4.3.9. Show your answer as in example 4.3.10.

**Ex 4.3.7** Prove that to construct orthogonal Latin squares of order \(2^m\), \(m\ge2\), it suffices to find two orthogonal Latin squares of order \(4=2^2\) and two of order \(8=2^3\).

**Ex 4.3.8** An \(n\times n\) Latin square \(A\) is **symmetric** if it is symmetric around the main diagonal, that is, \(A_{i,j}=A_{j,i}\) for all \(i\) and \(j\). It is easy to find symmetric Latin squares: every addition table modulo \(n\) is an example, as in example 4.3.6. A Latin square is **idempotent** if every symbol appears on the main diagonal. Show that if \(A\) is both symmetric and idempotent, then \(n\) is odd. Find a \(5\times 5\) symmetric, idempotent Latin square.

**Ex 4.3.9** The **transpose** \(A^\top\) of a Latin square \(A\) is the reflection of \(A\) across the main diagonal, so that \(A_{i,j}^\top=A_{j,i}\). A Latin square is self-orthogonal if \(A\) is orthogonal to \(A^\top\). Show that there is no self-orthogonal Latin square of order 3. Find one of order 4.

## 4.5: Matchings

**Ex 4.5.1** In this bipartite graph, find a maximum matching and a minimum vertex cover using the algorithm of this section. Start with the matching shown in red. Copies of this graph are available in this pdf file.

**Ex 4.5.2** Show directly that that the size of a minimum vertex cover in \(G\) is the minimum value of \(n-k+|\bigcup_{j=1}^k A_{i_j}|\), as mentioned above.