论文标题
Ryser的猜想和相关问题的新界限
New bounds for Ryser's conjecture and related problems
论文作者
论文摘要
$ n $的拉丁正方形是一个$ n \ times n $阵列，填充了$ n $符号，使每个符号在每个行或列中仅出现一次，而横向是一个不共享同一行，列或符号的单元格集合。对拉丁广场的研究可以追溯到200多年来，这归功于欧拉的工作。该地区最著名的开放问题之一是60年代的Ryser-Brualdi-Stein的猜想，该命令说每个拉丁订单$ n \ times n $都包含订单$ n-1 $的横向。在本文中，我们证明存在$ n-o（\ log {n}/\ log {\ log {n}}）$的顺序的横向，改善了hatami and shor的$ n-o（\ log^2n）$的著名绑定。我们的方法（与hatami-s的方法不同）是相当一般的，并且还提供了其他几种应用。我们在Steiner Triple Systems的最大匹配中获得了40年历史的Brouwer猜想的新下限，这表明每种这样的订单$ n $系统都可以保证具有大小$ n/3-o（\ log {n}/\ log {n}/\ log {\ log log {\ log log {n}}}）的匹配。这实质上改善了Alon，Kim和Spencer的当前最佳结果，该结果具有$ n^{1/2+O（1）} $的订单误差项。最后，我们还表明$ o（n \ log {n}/\ log {\ log {n}}）$拉丁阵列中的许多符号足以保证完整的横向，并在先前已知的$ n^{2- \ varepsilon} $上改进。证明以一种新颖的方式结合了Semirandom方法以及边缘有色伪数图的强大膨胀属性，以显示彩虹匹配的存在，除了$ o（\ log n/\ n/\ log {\ log {\ log {n}}}）$ Vertices $ Vertices。所有先前的结果，基于半随机方法，均未发现至少$ω（n^α）$（对于某些常数$α$）顶点。
A Latin square of order $n$ is an $n \times 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\times 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(\log^2n)$ 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 $n^{1/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 previously known bound of $n^{2-\varepsilon}$. The proofs combine in a novel way the semirandom 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 $α$) vertices.
