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.

  • 1
    $\begingroup$ 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? $\endgroup$ – bof Mar 5 '17 at 0:53

Presumably your answer to (a) formalized the bijection illustrated below:

enter image description here

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".

enter image description here

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).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.