REVIEW 6 cited by
A proof of the Ryser-Brualdi-Stein conjecture for large even $n$
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
A Latin square of order $n$ is an $n$ by $n$ grid filled using $n$ symbols so that each symbol appears exactly once in each row and column. A transversal in a Latin square is a collection of cells which share no symbol, row or column. The Ryser-Brualdi-Stein conjecture, with origins from 1967, states that every Latin square of order $n$ contains a transversal with $n-1$ cells, and a transversal with $n$ cells if $n$ is odd. Keevash, Pokrovskiy, Sudakov and Yepremyan recently improved the long-standing best known bounds towards this conjecture by showing that every Latin square of order $n$ has a transversal with $n-O(\log n/\log\log n)$ cells. Here, we show, for sufficiently large $n$, that every Latin square of order $n$ has a transversal with $n-1$ cells. We also apply our methods to show that, for sufficiently large $n$, every Steiner triple system of order $n$ has a matching containing at least $(n-4)/3$ edges. This improves a recent result of Keevash, Pokrovskiy, Sudakov and Yepremyan, who found such matchings with $n/3-O(\log n/\log\log n)$ edges, and proves a conjecture of Brouwer from 1981 for large $n$.
Forward citations
Cited by 6 Pith papers
-
A proof of Andersen's rainbow path conjecture for large $n$
For all sufficiently large n, every properly edge-coloured n-vertex complete graph has a rainbow path on n-1 vertices, resolving Andersen's conjecture and its Latin-square analogue for large n.
-
Almost every Latin square has a decomposition into transversals
With high probability, a uniformly random Latin square of order n has a decomposition into n disjoint transversals.
-
Colour-balanced subgraphs
Colour-balanced k-edge-coloured K_{2kt} has a perfect matching adjustable to colour-balance by recolouring O(k^2) edges.
-
A note on improved bounds for hypergraph rainbow matching problems
For r-uniform hypergraphs, rainbow matchings of size at least 2n/(r+1) - O_r(1) are guaranteed, but the maximum guaranteed size is below n - Ω_r(n^{1-1/r}).
-
Recent progress in graph theory using expansion
Sublinear expansion—weak neighbourhood growth in sparse graphs—has resolved many long-standing extremal graph theory conjectures, and this survey organizes that progress.
-
Restricted subgraphs of edge-colored graphs and applications
A survey that maps the results and methods for finding rainbow subgraphs in edge-colored graphs, and their applications across discrete mathematics, coding theory, and computer science.
Discussion (0). Continue with ORCID to comment.