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

DOI10.1090/TRAN/8954zbMATH Open1520.05089arXiv2206.14472OpenAlexW4362607184MaRDI QIDQ6135844FDOQ6135844

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

Publication date: 28 August 2023

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.

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

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

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)

Cites Work

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

Cited In (6)

• 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)