论文标题
拉丁正方形和施泰纳三重系统的阈值：对数因素的界限
Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
论文作者
论文摘要
We prove that for $n \in \mathbb N$ and an absolute constant $C$, if $p \geq C\log^2 n / n$ and $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k\in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i, j\in [n] $，然后几乎渐近地肯定有一个订单 - $ n $ latin Square，其中$ i $ th行的条目和$ j $ th列在$ l_ {i，j} $中。确定存在订单的阈值概率的问题是由Johansson，Luria和Simkin独立提出的，以及Casselgren和H {ä} ggkvist；我们的结果提供了一个上限，该界限紧密至$ \ log n $，并加强了SAH，Sawhney和Simkin最近获得的界限。我们还证明了Steiner Triple Systems和完整图的$ 1 $ factorizations的结果，而且我们表明，这些阈值中的每一个最多都是存在$ 1 $ factor的$ 1 $ factorization的阈值。
We prove that for $n \in \mathbb N$ and an absolute constant $C$, if $p \geq C\log^2 n / n$ and $L_{i,j} \subseteq [n]$ is a random subset of $[n]$ where each $k\in [n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i, j\in [n]$, then asymptotically almost surely there is an order-$n$ Latin square in which the entry in the $i$th row and $j$th column lies in $L_{i,j}$. The problem of determining the threshold probability for the existence of an order-$n$ Latin square was raised independently by Johansson, by Luria and Simkin, and by Casselgren and H{ä}ggkvist; our result provides an upper bound which is tight up to a factor of $\log n$ and strengthens the bound recently obtained by Sah, Sawhney, and Simkin. We also prove analogous results for Steiner triple systems and $1$-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a $1$-factorization of a nearly complete regular bipartite graph.
