Skip to main content
deleted 1 character in body
Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

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\times n,\ \ m\neq n$ and symbols $\ge max(m,n)$, is it possible to fill a maximum of $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?

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$ and symbols $\ge max(m,n)$, is it possible to fill a maximum of $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?

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?

Source Link
vidyarthi
  • 2.1k
  • 1
  • 16
  • 22

Dinitz Conjecture extension to rectangles

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$ and symbols $\ge max(m,n)$, is it possible to fill a maximum of $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?