The cycle structure of two rows in a random latin square

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√n cycles,

(iii) L has fewer than (9/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/4-o(1),3/4+o(1)] 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 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.

Click here to download the whole paper.

Last modified: Mon Sep 18 15:29:26 EST 2006