Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor

DOI10.1090/TRAN/8954MaRDI QIDQ6135844zbMATH OpenOpenAlexFDO

Authors Dong Yeap Kang, Tom Kelly, Daniela Kühn, Abhishek Methuku, Deryk Osthus

Publication date 28 August 2023

Full work available at URL https://arxiv.org/abs/2206.14472

zbMATH Keywords

thresholdblock designrandom graphLatin square1-factorizationSteiner triple systemrandom hypergraphtriangle decompositionShamir's problemspreadness

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial aspects of block designs (05B05) Combinatorial probability (60C05) Orthogonal arrays, Latin squares, Room squares (05B15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Triple systems (05B07)

Abstract: We prove that for $ninmathbbN$ and an absolute constant $C$, if $pgeqClo{g}^{2}n/n$ and $L_{i,j}subseteq[n]$ is a random subset of $[n]$ where each $kin[n]$ is included in $L_{i,j}$ independently with probability $p$ for each $i,jin[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{"a}ggkvist; our result provides an upper bound which is tight up to a factor of $logn$ 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.

Recommendations

• On the threshold problem for Latin boxes
• Threshold for Steiner triple systems
• Most Latin squares have many subsquares
• New bounds for Ryser’s conjecture and related problems
• On the maximum number of Latin transversals

Cites work

• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• scientific article; zbMATH DE number 3216216 (Why is no real title available?)
• scientific article; zbMATH DE number 3266380 (Why is no real title available?)
• A Census of Small Latin Hypercubes
• An upper bound on the number of high-dimensional permutations
• Coloring complete and complete bipartite graphs from random lists
• Combinatorial and computational aspects of graph packing and graph decomposition
• Edge-disjoint Hamilton cycles in random graphs
• Extremal aspects of graph and hypergraph decomposition problems
• Factors in random graphs
• Fractional clique decompositions of dense graphs and hypergraphs
• Hamilton decompositions of regular expanders: A proof of Kelly's conjecture for large tournaments
• Hunting for sharp thresholds
• Minimalist designs
• Nearly perfect matchings in regular simple hypergraphs
• New Bounds on the List-Chromatic Index of the Complete Graph and Other Simple Graphs
• Number of 1-factorizations of regular high-degree graphs
• On a hypergraph matching problem
• On a packing and covering problem
• On the combinatorial problems which I would most like to see solved
• On the existence of a factor of degree one of a connected random graph
• On the threshold problem for Latin boxes
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Pseudorandom hypergraph matchings
• Random graphs.
• Sharp thresholds of graph properties, and the $k$-sat problem
• Sublinear algorithms for \((\Delta + 1)\) vertex coloring
• The Existence of Designs via Iterative Absorption: Hypergraph 𝐹-designs for Arbitrary 𝐹
• The Solution of a Timetabling Problem
• The list chromatic index of a bipartite multigraph
• The probabilistic method
• The solution of van der Waerden's problem for permanents
• Threshold for Steiner triple systems
• Thresholds versus fractional expectation-thresholds

Cited in

(7)

• On the threshold problem for Latin boxes
• On the upper embedding of Steiner triple systems and Latin squares
• Threshold for Steiner triple systems
• Searching for (sharp) thresholds in random structures: where are we now?
• Large deviations in random latin squares
• Coloring hypergraphs from random lists
• ON DEFINING SETS IN LATIN SQUARES AND TWO INTERSECTION PROBLEMS, ONE FOR LATIN SQUARES AND ONE FOR STEINER TRIPLE SYSTEMS

This page was built for publication: Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6135844)