New bounds for Ryser’s conjecture and related problems

Abstract

A Latin square of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> × </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> array filled with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> × </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n\times n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> contains a transversal of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n minus 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n-1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . In this paper we prove the existence of a transversal of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n minus upper O left-parenthesis log n slash log log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">n-O(\log {n}/\log {\log {n}})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , improving the celebrated bound of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n minus upper O left-parenthesis log squared n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>log</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo> ⁡ </mml:mo> <mml:mi>n</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">n-O(\log ^2n)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> 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 <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is guaranteed to have a matching of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n slash 3 minus upper O left-parenthesis log n slash log log n right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mn>3</mml:mn> <mml:mo> − </mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>log</mml:mi> <mml:mo> ⁡ </mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annota

Topics & Concepts