Math Conjectures

Ryser–Brualdi–Stein Latin Transversal Conjecture

OPENMajorConjectureProposed 1967–1975 · Standard version

Canonical statement

Let LL be a Latin square of order nn, meaning an n×nn\times n array on nn symbols in which every symbol occurs once in every row and every column. A partial transversal is a set of cells using no row, column, or symbol twice. Then:
every L has a partial transversal of size n−1, \text{every }L\text{ has a partial transversal of size }n-1,
and, if nn is odd, every LL has a transversal of size nn.
View source LaTeX
Let \(L\) be a Latin square of order \(n\), meaning an
\(n\times n\) array on \(n\) symbols in which every symbol occurs once in
every row and every column. A partial transversal is a set of cells using
no row, column, or symbol twice. Then:
\[
  \text{every }L\text{ has a partial transversal of size }n-1,
\]
and, if \(n\) is odd, every \(L\) has a transversal of size \(n\).
COMB-006:[Stein1975Transversal][Montgomery2023Transversal][Montgomery2026Survey]
CombinatoricsDiscrete geometry

Notes

A partial transversal of a Latin square of order nn is a set of cells no two of which share a row, a column, or a symbol; a transversal is one of full size nn. The conjecture, assembled from proposals of Ryser and of Brualdi and Stein between 1967 and 1975 and routinely treated in the literature as a single problem, asserts that every Latin square of order nn has a partial transversal of size n−1n-1, and that every Latin square of odd order has a full transversal [Stein1975Transversal].

The odd-order restriction is necessary: the addition table of Z/nZ\mathbb Z/n\mathbb Z for even nn is a standard example of a Latin square with no transversal, so n−1n-1 is in general best possible. On the near-transversal side the problem is now essentially solved: Montgomery proved that every Latin square of sufficiently large order nn contains a partial transversal of size n−1n-1 [Montgomery2023Transversal]; see his survey for the state of the art [Montgomery2026Survey].

What remains is the finite check of the outstanding small orders for the n−1n-1 statement and, more substantially, the full-transversal assertion for arbitrary odd order, which is still open.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.