Ryser conjectured in 1967 that every Latin square of odd order n has a full transversal, a set of n cells containing exactly one cell from each row, each column, and each symbol. Equivalently, every proper n-edge-coloring of the complete bipartite graph on two sets of n vertices, with n odd, contains a perfect rainbow matching. This is the odd-order clause of the standard Ryser-Brualdi-Stein conjecture complex; its other clause, the near-transversal conjecture attributed to Brualdi and Stein together with its equivalent quasi-transversal formulation, is open only in a residual finite range of smaller orders, Montgomery (2023) having proved it for all sufficiently large orders. The conjecture has been open since 1967; every known transversal-free Latin square has even order, yet no current method forces a transversal in an arbitrary odd-order square.

Background

A Latin square of order nn is an n×nn\times n array filled with nn symbols so that each symbol appears exactly once in every row and every column; the multiplication table of any finite group is an example. A transversal is a set of nn cells of such a square that includes exactly one cell from each row, exactly one from each column, and each symbol exactly once. Relaxing this, a partial transversal of length kk is a set of kk cells no two of which share a row, a column, or a symbol, and a partial transversal of length n−1n-1 is called a near-transversal. Transversals are the classical route to orthogonality: a Latin square LL has an orthogonal mate, meaning a second Latin square MM such that the n2n^2 ordered pairs of entries in corresponding cells of LL and MM are all distinct, if and only if the cells of LL can be partitioned into nn pairwise disjoint transversals.

Not every Latin square has a transversal: the addition table of the cyclic group Zn\mathbb{Z}_n has none when nn is even, and a classical parity result says that every Latin square of even order has an even number of transversals. In contrast, no Latin square of odd order without a transversal has ever been found. Ryser conjectured in 1967 that none exists: every Latin square of odd order has a full transversal. Brualdi, and independently Stein in 1975 in a stronger form for equitable arrays (n×nn\times n arrays in which each of the nn symbols occurs exactly nn times, with no row or column restriction), conjectured that every Latin square of order nn has a near-transversal. Best and Wanless later documented that the attribution of the near-transversal conjecture to Ryser is apocryphal and recovered Ryser's actual 1967 statement, which concerns odd order. The combined statement is now standard: every Latin square of order nn has a partial transversal with at least n−1n-1 cells, and a full transversal when nn is odd; it is called the Ryser-Brualdi-Stein conjecture.

Kazemi and Pahlavsay (2018) study this conjecture complex. They define a quasi-transversal, a set of n+1n+1 cells containing exactly two cells in one row and two in one column, with one symbol occurring twice and every other symbol once, and observe that the near-transversal conjecture is equivalent to the statement that every Latin square has a quasi-transversal. They also relate transversals to graph domination: the Latin square graph has the cells as vertices, with two cells adjacent when they share a row, a column, or a symbol, and transversals correspond to certain 3-dominating sets (sets meeting the neighborhood of every vertex at least three times) of size nn. They record Rodney's conjecture that every Latin square has a duplex, that is, a 2-plex: a set of 2n2n cells containing exactly two cells from each row, each column, and exactly two occurrences of each symbol. Since not all squares of order nn have a transversal, the best that can be guaranteed in general is a partial transversal of length n−1n-1.

On the near-transversal clause, a long line of work gave partial transversals of length 2n/32n/3, then 3n/43n/4, then n−nn-\sqrt n in 1978, then n−O(log⁡2n)n-O(\log^2 n) (proved in 1982 with a gap fixed in 2008); Keevash, Pokrovskiy, Sudakov and Yepremyan (2022) improved this to n−O(log⁡n/log⁡log⁡n)n-O(\log n/\log\log n); and Montgomery (2023) proved that every Latin square of order n≥n0n\ge n_0 has a partial transversal of n−1n-1 cells, resolving the near-transversal clause for all large orders and hence, by the equivalence above, the quasi-transversal conjecture for large orders, while leaving the finite range of smaller orders open. For full transversals much less is known: the Hall-Paige conjecture, settled in 2009, gives a complete characterization for group multiplication tables (the Cayley table of a group has a transversal exactly when its Sylow 2-subgroups, the largest subgroups of 2-power order, are trivial or non-cyclic), and Eberhard, Manners and Mrazović (2023) showed that Latin squares satisfying a spectral quasirandomness condition, including a uniformly random Latin square with high probability, have many transversals. None of this touches arbitrary odd-order squares, and Montgomery's 2024 survey assesses the odd-order full-transversal case as quite far beyond the methods that settled the n−1n-1 clause.

Problem Statement

The near-transversal conjecture and its equivalent quasi-transversal formulation constitute the n−1n-1 clause of the Ryser-Brualdi-Stein conjecture. Montgomery (2023) proved that clause for all orders n≥n0n\ge n_0, for a threshold n0n_0 that is not explicitly given, so it remains open only for the residual finite range of smaller orders. The other clause of the same standard conjecture, open at every order, is Ryser's 1967 conjecture, stated here in its standard formulation:

Does every Latin square of odd order nn have a transversal, that is, a set of nn cells containing exactly one cell from each row, exactly one cell from each column, and each symbol exactly once?

Equivalently, in the edge-coloring formulation: Latin squares of order nn correspond bijectively to proper nn-edge-colorings of the complete bipartite graph on two sets of nn vertices (rows and columns; the color of an edge is the entry in the corresponding cell, and proper means edges sharing a vertex get different colors), and a transversal corresponds to a perfect rainbow matching, a perfect matching whose nn edges carry nn distinct colors. The question is whether every such coloring has a perfect rainbow matching when nn is odd.

References

  1. Adel P. Kazemi and Behnaz Pahlavsay, "Quasi-transversal in Latin Squares", arXiv:1808.05213 (2018). DOI: 10.48550/arXiv.1808.05213. https://arxiv.org/abs/1808.05213
  2. Richard Montgomery, "A proof of the Ryser-Brualdi-Stein conjecture for large even n", arXiv:2310.19779 (2023). https://arxiv.org/abs/2310.19779
  3. Richard Montgomery, "Transversals in Latin Squares", in Surveys in Combinatorics 2024, London Mathematical Society Lecture Note Series 493, Cambridge University Press (2024), pp. 131-158. DOI: 10.1017/9781009490559.006. arXiv:2406.19873, https://arxiv.org/abs/2406.19873
  4. Peter Keevash, Alexey Pokrovskiy, Benny Sudakov and Liana Yepremyan, "New bounds for Ryser's conjecture and related problems", Transactions of the American Mathematical Society, Series B 9 (2022), 288-321. DOI: 10.1090/btran/92. arXiv:2005.00526, https://arxiv.org/abs/2005.00526
  5. Ian M. Wanless, "Transversals in Latin Squares", Quasigroups and Related Systems 15 (2007), 169-190. arXiv:0903.5142, https://arxiv.org/abs/0903.5142
  6. Darcy Best and Ian M. Wanless, "What did Ryser Conjecture?", arXiv:1801.02893 (2018). https://arxiv.org/abs/1801.02893
  7. Candida Bowtell and Richard Montgomery, "Almost every Latin square has a decomposition into transversals", arXiv:2501.05438 (2025). https://arxiv.org/abs/2501.05438
  8. Afsane Ghafari and Ian M. Wanless, "Latin Squares whose transversals intersect in unusual ways", arXiv:2607.17547 (2026). https://arxiv.org/abs/2607.17547
  9. Nicholas J. Cavenagh and Ian M. Wanless, "Latin squares with no transversals", The Electronic Journal of Combinatorics 24(2) (2017), #P2.45. DOI: 10.37236/6481. arXiv:1609.03001, https://arxiv.org/abs/1609.03001
  10. Kyle Pula, "A generalization of plexes of Latin squares", Discrete Mathematics 311 (2011), 577-581. DOI: 10.1016/j.disc.2011.01.007
  11. Behnaz Pahlavsay, Elisa Palezzato and Michele Torielli, "Domination for Latin Square Graphs", Graphs and Combinatorics (2021). DOI: 10.1007/s00373-021-02297-7
  12. Debsoumya Chakraborti, Micha Christoph, Zach Hunter, Richard Montgomery and Teo Petrov, "Almost-full transversals in equi-n-squares", arXiv:2412.07733 (2024). https://arxiv.org/abs/2412.07733
  13. Sean Eberhard, Freddie Manners and Rudi Mrazović, "Transversals in quasirandom latin squares", Proceedings of the London Mathematical Society 127(1) (2023), 84-115. DOI: 10.1112/plms.12538
  14. P. Erdős, D. R. Hickerson, D. A. Norton and S. K. Stein, "Has Every Latin Square of Order n a Partial Latin Transversal of Size n-1?", The American Mathematical Monthly 95(5) (1988), 428-430. DOI: 10.2307/2322477