On the threshold problem for Latin boxes. Issue 4 (30th April 2019)

• Record Type: Journal Article
• Authors: Luria, Zur; Simkin, Michael
• Is Part Of: Random structures & algorithms. Volume 55:Issue 4(2019)
• Page Start: 926
• Page End: 949
• Publication Date: 2019-04-30
• Subjects: graph colorings -- Latin squares -- threshold functions; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20855
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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 .