Latin Squares Home, Southeast Missouri State Universiy拉丁方的家東南密蘇里州立大學(xué)

1、latin squares, cubes and hypercubesjerzy wojdymarch 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes2definition and examplesna is a square array in which each row and each column consists of the same set of entries without repetition.march 31, 2007jerzy wojdylo, latin squares, cubes and hy

2、percubes3existencendo latin squares exist for every +?nyes. march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes4operations on latin squares of a latin square is a upermutation of its rows, upermutation of its columns,upermutation of its symbols. (these permutations do not have to be the

3、 same.) is iff its first row is 1, 2, march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes5enumeration of lsnhow many latin squares ( rectangles) are there?nif order 11brendan d. mckay, ian m. wanless, “” 2004(?) (show the table on page 5)/wiki/latin_square#the_numb

4、er_of_latin_squaresnorder 12, 13, open problem.march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes6enumeration of ls1234567891011 1114569408 16942080 535281401856 377597570964258816 7580721483160132811489280 5363937773277371298119673540771840n! (n-1)! times the number of reduced latin s

5、quares march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes7orthogonal latin squaresntwo latin squares = and = are iff the 2 pairs ( , ) are all different.march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes8orthogonal ls - useful property two latin squares are orthogonal iff

6、 their normal forms are orthogonal. (you can permute symbols so both ls have the first row 1, 2, , )nno two 22 latin squares are orthogonal.1221march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes9orthogonal latin squaresnthis 44 latin square does not have an orthogonal mate.123423413412

7、41231234march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes10orthogonal ls history 1782nleonhard eulermarch 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes11orthogonal ls history 1782nleonhard euler, originally published in verhandelingen uitgegeven door het zeeuwsch genootsc

8、hap der wetenschappen te vlissingen 9, middelburg 1782, pp. 85-239also available in: commentationes arithmeticae 2, 1849, pp. 302-361opera omnia: series 1, volume 7, pp. 291-392 march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes12orthogonal ls history 1900-01ngaston tarry verified case

9、 =6. compte rendu de lassoc. franais avanc. sci. naturel 1, 122-123, 1900. compte rendu de lassoc. franais avanc. sci. naturel 2, 170-203, 1901. ntwo years of sundays.march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes13orthogonal ls history 1959nin 1959, bose and shrikhande constructed

10、 a pair of orthogonal latin squares of order 22. nthen parker constructed a pair of orthogonal latin squares of order 10. npicture (next slide) orhttp:/www.cecm.sfu.ca/organics/papers/lam/paper/html/nytimes.htmlmarch 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes14orthogonal ls nyt 4/26/

11、1959march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes15orthogonal ls history 1960n1960 r.c. bose, s.s. shrikhande, e.t. parker, , canadian journal of mathematics, vol. 12 (1960), pp. 189-203. nthere exists a pair of orthogonal ls for all +, with exception of = 2 and = 6.march 31, 2007

12、jerzy wojdylo, latin squares, cubes and hypercubes16mutually orthogonal ls (mols)na set of ls that are pairwise orthogonal is called a set of ().the largest number of mols is 1.march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes17mutually orthogonal ls (mols)if is prime, then there are

13、1 -mols.nproofconstruction of =,=1, 2, , 1: = + (mod ). if = , prime, then there are 1 -mols.if there are 1 -mols, then = , prime.march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes18mutually orthogonal ls (mols)let n( ) be the number of mols that exist of size .: find n( ) for march 31

14、, 2007jerzy wojdylo, latin squares, cubes and hypercubes19mols lower bounds for n(n)020406080100120140160180047498769615406080100120771802135486666632224268210261016264365636761067542467671247796144566666676264666610612671661087575761276769828486881087148168810246666666611103057076130150819012531576

15、13676713125527261127817219214345566686615456567776716156767676146171636769681361569196183456666766191855878861386178198march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes20completion problemsnwhen can a latin rectangle with entries in 1, 2, , be completed to a latin square?1345351251341

16、2344312march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes21completion theoremslet any latin rectangle with entries in 1, 2, , can be completed to a latin square.nthe proof uses halls marriage theorem or transversals to complete the bottom rows. the construction fills one row at a time.

17、 march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes22completion problems nthe good:1234431221433421march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes23completion theoremslet ,2, n6nj. arkin, e. g. strauss, the fibonacci quarterly, vol. 12 (3) (1974): 288-292.nj. arkin, e.

18、 g. strauss, the fibonacci quarterly, vol. 19 (3) (1981): 281-293.nm. trenkler, , czechoslovak mathematical journal, 55 (130) (2005), 725-728.nall produced essentially the same theorem:march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes33orthogonal hypercubes n2, n6there exists a set of

19、 orthogonal latin -hypercubes of order , 2 and march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes34orthogonal hypercubes n2, n61+1 = (march 31, 2007jerzy wojdylo, latin squares, cubes and hypercubes35orthogonal hypercubes n = 6nwhat about = 6? nj. kerr, , the fibonacci quarterly vol. 20. no. 4 (1982): 360-362.nsimilar theorem.nexamples of three orthogonal latin cubes and four ort