Keevash, Peter;
Pokrovskiy, Alexey;
Sudakov, Benny;
Yepremyan, Liana;
(2022)
New bounds for Ryser’s conjecture and related problems.
Transactions of the American Mathematical Society, Series B
, 9
(8)
pp. 288-321.
10.1090/btran/92.
Preview |
Text
Pokrovskiy_S2330-0000-2022-00092-3.pdf Download (456kB) | Preview |
Abstract
A Latin square of order n is an n × n array filled with n symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser-Brualdi-Stein from 60s which says that every Latin square of order n × n contains a transversal of order n − 1. In this paper we prove the existence of a transversal of order n − O(log n/ log log n), improving the celebrated bound of n − O(log2 n) by Hatami and Shor. Our approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. We obtain a new lower bound on a 40-year-old conjecture of Brouwer on the maximum matching in Steiner triple systems, showing that every such system of order n is guaranteed to have a matching of size n/3 − O(log n/ log log n). This substantially improves the current best result of Alon, Kim and Spencer which has the error term of order n1/2+o(1). Finally, we also show that O(n log n/ log log n) many symbols in Latin arrays suffice to guarantee a full transversal, improving on a previously known bound of n2−ε. The proofs combine in a novel way the semi-random method together with the robust expansion properties of edge-coloured pseudorandom graphs to show the existence of a rainbow matching covering all but O(log n/ log log n) vertices. All previous results, based on the semi-random method, left uncovered at least Ω(nα) (for some constant α > 0) vertices.
| Type: | Article |
|---|---|
| Title: | New bounds for Ryser’s conjecture and related problems |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1090/btran/92 |
| Publisher version: | https://doi.org/10.1090/btran/92 |
| Language: | English |
| Additional information: | © Copyright 2022 by the authors under Creative Commons Attribution 3.0 License (CC BY 3.0) |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10160699 |
Archive Staff Only
 |
View Item |
