5
$\begingroup$

The Dinitz Conjecture, which was proved later in a more general form by Galvin, stated that given an $n\times n$ array, its elements could be filled exactly like a latin square, where the elements in each row/column is chosen from a set (list) of $m\ge n$ symbols.

Whether an extension of this is possible for partial latin rectangles? That is given a rectangle of size $m\times n,\ \ m\neq n$ and symbols $\ge max(m,n)$, is it possible to fill $min(m,n)$ symbols in each row and/or column such that the symbols in each row, column as well as diagonal (the places $a_{ij}$ with $j=i$, where $i,j$ denote row and column indices and $a$ denotes the symbol) are distinct?

Improve this question
$\endgroup$
3
  • $\begingroup$ @RebeccaJ.Stones yes, the latin rectangle is partial, that is, has some empty cells $\endgroup$
    – vidyarthi
    Sep 13, 2019 at 11:55
  • 2
    $\begingroup$ I don't understand the statement. What does your conjecture say in the special case where $m=n$? It's not the Dinitz Conjecture because the DC does not require distinct symbold on the diagonal, and I believe it would be false if you just added that requirement. Also not sure what "fill a maximum of $\min(m,n)$ symbols . . ." means. If it means "fill at most $\min(m,n)$ symbols," can't you satisfy it trivially by leaving all cells empty? $\endgroup$
    – bof
    Oct 7, 2019 at 3:42
  • $\begingroup$ @bof thanks for that observation. Edited the question now. $\endgroup$
    – vidyarthi
    Oct 7, 2019 at 19:28

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.