Premium
The cycle structure of two rows in a random Latin square
Author(s) -
Cavenagh Nicholas J.,
Greenhill Catherine,
Wanless Ian M.
Publication year - 2008
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.20216
Subject(s) - combinatorics , permutation (music) , mathematics , random permutation , conjecture , latin square , row , order (exchange) , distribution (mathematics) , probability distribution , square (algebra) , random variable , discrete mathematics , statistics , symmetric group , physics , geometry , mathematical analysis , rumen , chemistry , food science , finance , database , fermentation , acoustics , computer science , economics
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 $\sqrt{n}$ cycles, (iii) L has fewer than $ 9\over 2$ n 5/2 intercalates (latin subsquares of order 2). We also show that the probability that σ r , s is an even permutation lies in an interval $[{1\over 4} - o(1), {3\over 4} + o(1)]$ and the probability that it has a single cycle lies in [2 n ‐2 ,2 n ‐2/3 ]. Indeed, we show that almost all derangements have similar probability (within a factor of n 3/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