Premium
On the threshold problem for Latin boxes
Author(s) -
Luria Zur,
Simkin Michael
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20855
Subject(s) - latin square , combinatorics , mathematics , latin americans , probability distribution , distribution (mathematics) , discrete mathematics , statistics , mathematical analysis , law , political science , rumen , chemistry , food science , fermentation
Let m ≤ n ≤ k . An m × n × k 0‐1 array is a Latin box if it contains exactly m n 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 M ( m , n , k ; p ) be the distribution on m × n × k 0‐1 arrays where each entry is 1 with probability p , independently of the other entries. The threshold question for Latin squares asks when M ( n , n , n ; p ) contains a Latin square with high probability. More generally, when does M ( m , n , k ; p ) support a Latin box with high probability? Let ε > 0. We give an asymptotically tight answer to this question in the special cases where n = k and m ≤ 1 − ε n , and where n = m and k ≥ 1 + ε n . In both cases, the threshold probability is Θ log n / n . This implies threshold results for Latin rectangles and proper edge‐colorings of K n , n .