On the threshold problem for Latin boxes

DOI10.1002/RSA.20855zbMATH Open1439.05040arXiv1711.09741OpenAlexW2963507266WikidataQ127950584 ScholiaQ127950584MaRDI QIDQ5216183FDOQ5216183

Authors: Zur Luria, Michael Simkin 

Publication date: 14 February 2020

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

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}$.

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

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

zbMATH Keywords

Latin squaresthreshold functionsgraph colorings

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• The \(n\)-queens completion problem
• 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?
• Computing tighter bounds on the \(n\)-queens constant via Newton's method
• Large deviations in random latin squares
• Coloring hypergraphs from random lists

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)