# One-to-one correspondence between n-edge-colourings of $K_{n,n}$ and Latin squares

I need help with this. I don't know how to do this (especially case b) ).

a) An $n \times n$ array $A = (a_{ij})$, whose entries are taken from some set $S$ of $n$ symbols, is called a Latin square of order $n$ if each symbol appears precisely once in each row and precisely once in each column of $A$. Show that there is a one-to-one correspondence between $n$-edge-colourings of $K_{n,n}$ in colours $1, 2, \dots , n$ and Latin squares of order $n$ in symbols $1, 2, \dots, n$.

b) Deduce from the (below) Theorem the following assertion, a special case of a conjecture due to J. Dinitz.

For $1 \leq i\leq j \leq n$, let $S_{ij}$ be a set of $n$ elements. Then there exists a Latin square $A = (a_{ij})$ of order $n$ using a set $S$ of $n$ symbols such that $a_{ij} \in S_{ij} \cap S$, $1 \leq i \leq j \leq n$.

Theorem: Every simple bipartite graph $G$ is $\Delta$-list-edge-colourable.

• I don't understand the assertion in part (b). Are $S_{ij}$ and $a_{ij}$ only defined for $i\le j$? And what if the sets $S_{ij}$ happen to be pairwise disjoint, so that the elements $a_{ij}$ are pairwise distinct? What is the "set $S$ of $n$ symbols" supposed to be in that case? – bof Mar 5 '17 at 0:53

Basically, the symbol $s$ in cell $(a,b)$ maps to the edge $\text{row}_a \text{col}_b$, say, of color $s$.

For the second part, it's the same idea with "symbol"/"color" replaced by "list".

The list $L$ assigned to cell $(a,b)$ maps to the edge $\text{row}_a \text{col}_b$ which is also assigned the list $L$. The theorem implies a $\Delta$-list-edge-coloring exists, which we convert back to give a $n \times n$ matrix which we can show has no repeated symbols in the rows and columns.

As bof points out, however, the statement of the Dinitz Conjecture Theorem is incorrect. I.e., it doesn't guarantee a Latin square, just no repeats in rows/columns (a generalization of a Latin square).