Counting Near-Spanning Matchings in Latin Squares and Steiner Triple Systems

Abstract

Montgomery recently proved that for sufficiently large $n$, every Latin square of order $n$ has a partial transversal with $n-1$ cells, and every Steiner triple system of order $n$ has a matching with $\lfloor n/3\rfloor -1$ edges, thus confirming the Ryser--Brualdi--Stein conjecture for even $n$ and the conjecture of Brouwer. We prove sharp enumerative refinements of these results: there is an absolute constant $c>0$ such that, for sufficiently large $n$, 1) every Latin square of order $n$ has ${\left((1\pm n^{-c})\frac{n}{{\mathrm{e}}^2}\right)}^n$ partial transversals with $n-1$ cells; 2) every Steiner triple system of order $n$ has ${\left((1\pm n^{-c})\frac{n}{2{\mathrm{e}}^2}\right)}^{\lfloor n/3\rfloor }$ matchings with $\lfloor n/3\rfloor -1$ edges. The first estimate confirms predictions of Montgomery and Kelly.

18 pages