On the threshold problem for Latin boxes

DOI10.1002/RSA.20855MaRDI QIDQ5216183zbMATHOpenAlexWikidataFDO

Authors Zur Luria, Michael Simkin

Publication date 14 February 2020

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

Latin squaresthreshold functionsgraph colorings

Mathematics Subject Classification ID

Orthogonal arrays, Latin squares, Room squares (05B15) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $mleqnleqk$. An $mimesnimesk$ 0-1 array is a Latin box if it contains exactly $mn$ ones, and has at most one $1$ in each line. As a special case, Latin boxes in which $m=n=k$ are equivalent to Latin squares. Let $mathcalM(m,n,k;p)$ be the distribution on $mimesnimesk$ 0-1 arrays where each entry is $1$ with probability $p$, independently of the other entries. The threshold question for Latin squares asks when $mathcalM(n,n,n;p)$ contains a Latin square with high probability. More generally, when does $mathcalM(m,n,k;p)$ support a Latin box with high probability? Let $varepsilon>0$. We give an asymptotically tight answer to this question in the special cases where $n=k$ and $mleqleft(1-varepsilonight)n$, and where $n=m$ and $kgeqleft(1+varepsilonight)n$. In both cases, the threshold probability is $Thetaleft(logleft(night)/night)$. This implies threshold results for Latin rectangles and proper edge-colorings of $K_{n,n}$.

Recommendations

• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Asymptotic enumeration of generalized Latin rectangles
• Discrepancy of high-dimensional permutations
• Avoiding Arrays of Odd Order by Latin Squares
• Large deviations in random latin squares

Cites work

• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 949656 (Why is no real title available?)
• scientific article; zbMATH DE number 1405894 (Why is no real title available?)
• A course in combinatorics.
• Avoiding Arrays of Odd Order by Latin Squares
• Coloring complete and complete bipartite graphs from random lists
• Intercalates and discrepancy in random Latin squares
• Perfect matchings in \(\varepsilon\)-regular graphs
• Perfect matchings via uniform sampling in regular bipartite graphs
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Random triangle removal
• The solution of van der Waerden's problem for permanents
• Two-dimensional weight-constrained codes through enumeration bounds

Cited in

(7)

• Coloring hypergraphs from random lists
• Thresholds for Latin squares and Steiner triple systems: Bounds within a logarithmic factor
• Perfect matchings in random subgraphs of regular bipartite graphs
• Searching for (sharp) thresholds in random structures: where are we now?
• The \(n\)-queens completion problem
• Large deviations in random latin squares
• Computing tighter bounds on the \(n\)-queens constant via Newton's method

This page was built for publication: On the threshold problem for Latin boxes

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