4.E: Systems of Distinct Representatives (Exercises)
- Page ID
- 7243
4.2: Existence of SDRs
How many different systems of distinct representatives are there for \(A_1=\{1,2\}\), \(A_2=\{2,3\}\), …, \(A_n=\{n,1\}\)?
How many different systems of distinct representatives are there for the sets \(A_i=[n]\backslash{i}\), \(i=1,2,\ldots,n\), \(n\ge2\)?
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\).
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\).
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.3: Partial SDRs
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\}.\nonumber\] Justify your answer.
4.4: Latin Squares
Show that there is only one reduced Latin square of order 3.
Verify that the isotopy relation is an equivalence relation.
Find all 4 reduced Latin squares of order 4. Show that there are at most 2 isotopy classes for order 4.
Show that the second set system defined in Example 4.4.5 has an sdr as claimed.
Show that there are no orthogonal Latin squares of order 2.
Find the two orthogonal Latin squares of order \(5\) as described in Theorem 4.4.1. Show your answer as in Example 4.4.6.
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\).
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.4.4. 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.
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.6: Matchings
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.
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.