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 ⌊ n/3⌋−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 ⌊ n/3⌋−1 edges. The first estimate confirms predictions of Montgomery and Kelly.
Related
- Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
- A simplified proof of the FPRAS for counting perfect matchings
- Δ-Y Moves and Partial Steiner Systems
- Thresholds for ( n , q , 2)-Steiner systems via refined absorption
- Characterizing Steiner Systems via Betti Numbers of Monomial Ideals
BibTeX
@misc{tang2026counting,
title = {{Counting Near-Spanning Matchings in Latin Squares and Steiner Triple Systems}},
author = {Yantao Tang and Yi Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.11006},
eprint = {2609.11006},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.11006},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Counting Near-Spanning Matchings in Latin Squares and Steiner Triple Systems
AU - Yantao Tang
AU - Yi Zhao
PY - 2026
DA - 2026/09/10
PB - arXiv
DO - 10.48550/arxiv.2609.11006
UR - https://arxiv.org/abs/2609.11006
AB - 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 ⌊ n/3⌋−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 ⌊ n/3⌋−1 edges. The first estimate confirms predictions of Montgomery and Kelly.
ER -