Name
Abstract | ||
|---|---|---|
Let L be chosen uniformly at random from among the latinsquares of order n ≥ 4 and let r,s bearbitrary distinct rows of L. We study the distribution ofσr,s, the permutation of the symbolsof L which maps r to s. We show that for anyconstant c 0, the following events hold withprobability 1 - o(1) as n → ∞: (i)σr,s has more than (logn)1-c cycles, (ii)σr,s has fewer than 9$\sqrt{n}$cycles, (iii) L has fewer than $ 9\over 2$n5-2 intercalates (latin subsquares of order 2).We also show that the probability thatσr,s is an even permutation lies inan interval $[{1\over 4} - o(1), {3\over 4} + o(1)]$ and theprobability that it has a single cycle lies in[2n-2,2n-2-3]. Indeed, we showthat almost all derangements have similar probability (within afactor of n3-2) of occurring asσr,s as they do if chosen uniformlyat random from among all derangements of {1,2,…,n}.We conjecture that σr,s shares theasymptotic distribution of a random derangement. Finally, we givecomputational data on the cycle structure of latin squares oforders n ≥ 11. © 2008 Wiley Periodicals, Inc. RandomStruct. Alg., 2008 |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1002/rsa.v33:3 | Random Struct. Algorithms |
Keywords | Field | DocType |
latin square,intercalate | Discrete mathematics,Binary logarithm,Combinatorics,Permutation,struct,Latin square,Derangement,Parity of a permutation,Conjecture,Mathematics,Asymptotic distribution | Journal |
Volume | Issue | ISSN |
33 | 3 | 1042-9832 |
Citations | PageRank | References |
10 | 0.84 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicholas J. Cavenagh | 1 | 92 | 20.89 |
| Catherine Greenhill | 2 | 628 | 62.40 |
| Ian M. Wanless | 3 | 245 | 38.75 |