The cycle structure of two rows in a random Latin square |
| |
Authors: | Nicholas J Cavenagh Catherine Greenhill Ian M Wanless |
| |
Institution: | 1. School of Mathematics and Statistics, The University of New South Wales, NSW 2052 Australia;2. School of Mathematical Sciences, Monash University, VIC 3800 Australia |
| |
Abstract: | Let L be chosen uniformly at random from among the latin squares of order n ≥ 4 and let r,s be arbitrary distinct rows of L. We study the distribution of σr,s, the permutation of the symbols of L which maps r to s. We show that for any constant c > 0, the following events hold with probability 1 ‐ o(1) as n → ∞: (i) σr,s has more than (log n)1?c cycles, (ii) σr,s has fewer than 9 cycles, (iii) L has fewer than n5/2 intercalates (latin subsquares of order 2). We also show that the probability that σr,s is an even permutation lies in an interval and the probability that it has a single cycle lies in 2n‐2,2n‐2/3]. Indeed, we show that almost all derangements have similar probability (within a factor of n3/2) of occurring as σr,s as they do if chosen uniformly at random from among all derangements of {1,2,…,n}. We conjecture that σr,s shares the asymptotic distribution of a random derangement. Finally, we give computational data on the cycle structure of latin squares of orders n ≤ 11. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
Keywords: | latin square latin trade random derangement cycle structure intercalate quasigroup character |
|
|