Editing Latin square (section)

== {{Anchor|transversal}}Transversals and rainbow matchings ==
{{See also|Hall-type theorems for hypergraphs#More conditions from rainbow matchings}}
A '''transversal''' in a Latin square is a choice of ''n'' cells, where each row contains one cell, each column contains one cell, and there is one cell containing each symbol.

One can consider a Latin square as a complete [[bipartite graph]] in which the rows are vertices of one part, the columns are vertices of the other part, each cell is an edge (between its row and its column), and the symbols are colors. The rules of the Latin squares imply that this is a proper [[edge coloring]]. With this definition, a Latin transversal is a matching in which each edge has a different color; such a matching is called a [[Rainbow matching#Bounds depending only on the number of vertices|rainbow matching]].

Therefore, many results on Latin squares/rectangles are contained in papers with the term "rainbow matching" in their title, and vice versa.<ref>{{cite arXiv|eprint=1208.5670|class=math. CO|first1=Andras|last1=Gyarfas|first2=Gabor N.|last2=Sarkozy|title=Rainbow matchings and partial transversals of Latin squares|year=2012}}</ref>

Some Latin squares have no transversal. For example, when ''n'' is even, an ''n''-by-''n'' Latin square in which the value of cell ''i'',''j'' is (''i''+''j'') mod ''n'' has no transversal. Here are two examples:<math display="block">
\begin{bmatrix}
 1 & 2 \\
 2 & 1 
\end{bmatrix}
\quad
\begin{bmatrix}
 1 & 2 & 3 & 4 \\
 2 & 3 & 4 & 1 \\
 3 & 4 & 1 & 2 \\
 4 & 1 & 2 & 3 
\end{bmatrix}
</math>In 1967, [[H. J. Ryser]] conjectured that, when ''n'' is '''odd''', every ''n''-by-''n'' Latin square has a transversal.<ref name=":0">{{Cite journal|last1=Aharoni|first1=Ron|last2=Berger|first2=Eli|last3=Kotlar|first3=Dani|last4=Ziv|first4=Ran|date=2017-01-04|title=On a conjecture of Stein|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=87|issue=2|pages=203–211|doi=10.1007/s12188-016-0160-3|s2cid=119139740|issn=0025-5858}}</ref>

In 1975, S. K. Stein and Brualdi conjectured that, when ''n'' is '''even''', every ''n''-by-''n'' Latin square has a '''partial''' transversal of size ''n''−1.<ref>{{Cite journal|last=Stein|first=Sherman|date=1975-08-01|title=Transversals of Latin squares and their generalizations| journal=Pacific Journal of Mathematics| volume=59| issue=2| pages=567–575| doi=10.2140/pjm.1975.59.567|issn=0030-8730|doi-access=free}}</ref>

A more general conjecture of Stein is that a transversal of size ''n''−1 exists not only in Latin squares but also in any ''n''-by-''n'' array of ''n'' symbols, as long as each symbol appears exactly ''n'' times.<ref name=":0" />

Some weaker versions of these conjectures have been proved:

* Every ''n''-by-''n'' Latin square has a partial transversal of size 2''n''/3.<ref>{{Cite journal|last=Koksma|first=Klaas K.| date=1969-07-01|title=A lower bound for the order of a partial transversal in a latin square|journal=Journal of Combinatorial Theory|volume=7|issue=1|pages=94–95|doi=10.1016/s0021-9800(69)80009-8|issn=0021-9800|doi-access=free}}</ref>
* Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − sqrt(''n'').<ref>{{Cite journal| last=Woolbright| first=David E|date=1978-03-01|title=An n × n Latin square has a transversal with at least n−n distinct symbols|journal=Journal of Combinatorial Theory, Series A|volume=24|issue=2|pages=235–237|doi=10.1016/0097-3165(78)90009-2|issn=0097-3165|doi-access=free}}</ref>
* Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − 11 log{{su|b=2|p=2}}(''n'').<ref>{{Cite journal|last1=Hatami|first1=Pooya|last2=Shor|first2=Peter W.|date=2008-10-01|title=A lower bound for the length of a partial transversal in a Latin square|journal=Journal of Combinatorial Theory, Series A|volume=115| issue=7| pages=1103–1113| doi=10.1016/j.jcta.2008.01.002|issn=0097-3165|doi-access=free}}</ref>
* Every ''n''-by-''n'' Latin square has a partial transversal of size ''n'' − O(log n/loglog n).<ref>{{Cite journal |last1=Keevash |first1=Peter |last2=Pokrovskiy |first2=Alexey |last3=Sudakov |first3=Benny |last4=Yepremyan |first4=Liana |date=2022-04-15 |title=New bounds for Ryser's conjecture and related problems |url=https://www.ams.org/btran/2022-09-08/S2330-0000-2022-00092-3/ |journal=Transactions of the American Mathematical Society, Series B |language=en |volume=9 |issue=8 |pages=288–321 |doi=10.1090/btran/92 |issn=2330-0000|doi-access=free |hdl=20.500.11850/592212 |hdl-access=free }}</ref>
* Every large enough ''n''-by-''n'' Latin square has a partial transversal of size ''n'' −1.<ref>{{Cite arXiv |last=Montgomery |first=Richard |date=2023 |title=A proof of the Ryser-Brualdi-Stein conjecture for large even ''n'' |class=math.CO |eprint=2310.19779}}</ref> (Preprint)