Partial Latin squares related to a given autotopism

Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Partial Latin squares related to a given autotopism. Ra´ul M. Falc´on Department of Applied Mathematics I University of Seville (Spain) [email protected] 23rd British Combinatorial Conference Exeter, 3rd to 8th July 2011 Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Introduction Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. CSn: Cycle structures of a permutation. π= (1234)(56)(78)(9) ⇒zπ= 41·22·1. |CSn|=p(n)≡Number of partitions of n. Two permutations are conjugate if and only if they have the same cycle structure. π2=π0−1π1π0 Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. LSn: Latin squares. Latin square: ALatin square Lof order n, is a n×narray with elements chosen from the set [n] = {1,2, ..., n}, such that each symbol occurs precisely once in each row and each column.     1234 2143 3421 4312     ∈ LS4 O(L) = {(r≡row,c≡column,s≡symbol)}. Parastrophism: π∈Sn O(Lπ) = {(lπ(1),lπ(2),lπ(3))|(l1,l2,l3)∈O(L)}. Isotopism (∼): Θ=(α, β, γ)∈In=S3 n O(LΘ) = {(α(r), β(c), γ(s)) |(r,c,s)∈O(L)} [L] Θ = ((12)(34),(12)(3)(4),(1234)) ⇒zΘ= (22,2·12,4). Parastrophic class: π∈Snand z∈ CSIn. [z] = {zπ= (zπ(1),zπ(2),zπ(3) |π∈S3}. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. An: Autotopisms of a Latin square. Autotopism: LΘ=L An. LSΘ={L∈ LSn|LΘ=L}. CSAnis known for n≤17 [Falc´on, 2007; Stones, Vojtˇechovsk´y and Wanless, 2011] ∆(Θ) = |LSΘ|only depends on zΘ ∆(z). ∆(z) is known for n≤7 [Falc´on, Mart´ın-Morales, 2007] and the majority of n= 8 and n= 9 [Falc´on, Mart´ın-Morales, 2008]. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Latin Squares and the 3PAPn 3-dimensional planar assignment problem (3PAPn): min Pr,c,s∈[n]wrcs ·xrcs , s.t. Pr∈[n]xrcs = 1,∀c,s∈[n], Pc∈[n]xrcs = 1,∀r,s∈[n], Ps∈[n]xrcs = 1,∀r,c∈[n], xrcs ∈ {0,1},∀r,c,s∈[n], (3PAPn) It can be defined the 1-1 correspondence: xrcs =(1,if (r,c,s)∈O(L), 0,otherwise     1234 2143 3421 4312     ←→ (1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1, 0,1,0,0,1,0,0,0,0,0,0,1,0,0,1,0, 0,0,1,0,0,0,0,1,0,1,0,0,1,0,0,0, 0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0) Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Partial Latin Squares PLSn. Partial Latin square: Apartial Latin square Pof order n, is a n×n array with elements chosen from [n], such that each symbol occurs at most once in each row and each column.     1·3 4 2143 3 4 ·1 ·3 1 ·     ∈ PLS4 O(P) = {(r,c,s)|s6=∅}. PLSΘ={P∈ PLSn|PΘ=P}. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Partial Latin Squares PLSn. Pcan be completed to a Latin square Lif O(P)⊆O(L). P-coefficient of symmetry of Θ: The computation of ∆(z) can be simplified if a multiplicative factor cP∈Nis found s.t. ∆(z) = cP· |LSΘ,P|. Main problem: cPbecomes crucial in the processing of high orders, but none exhaustive study has been developed. A comprehensive analysis of APnand PLSΘhas not been properly done until now. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. The set CSAPn. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Sizes LCMz={(i,j)∈[n]2| ∃k∈[n] s.t. (i,j,k)∈LCMnand z1i·z2j·z3k>0}. Lemma z∈ CSAPn. Θ∈Iz. P∈ PLSΘ. i×j-block Bof the Θ-decomposition of P. There exists ωB∈[gcd(i,j)] ∪ {0}such that |B|=ωB·lcm(i,j). Specifically, ωB= 0 if (i,j)6∈ LCMz. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Sizes Proposition z= (z1,z2,z3)∈ CSAPn. P∈ PLSz. It is lz≤ |P| ≤ uz, where: lz= min (i,j)∈LCMz {lcm(i,j)}, uz= min{X (i,j)∈LCMz z1i·z2j·i·j,X (i,k)∈LCMz(23) z1i·z3k·i·k,X (k,j)∈LCMz(13) z2j·z3k·j·k}. Sizes(z) =   X (i,j)∈LCMz ωij ·lcm(i,j)≤uz|ωij ∈[z1i·z2j·gcd(i,j)]   . Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Sizes z= (6,3·2·1,4·2) ∈ CSAP6 Θ = ((123456),(123)(45)(6),(1234)(56)) ∈ PLSz.        ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦ ···∗∗◦        . LCMz={(6,3)},LCMz(23) ={(6,2)}and LCMz(13) ={(2,3)}. So: 6 ≤ |P| ≤ min{18,12,6}= 6. Thus, Sizes(z) = {6}and |P|= 6.        5· · · · · ·6· · · · · · 5··· 6· · · · · ·5· · · · · · 6···        ,        6· · · · · ·5· · · · · · 6··· 5· · · · · ·6· · · · · · 5···        ,        ·5· · · · · · 6··· 5· · · · · ·6· · · · · · 5··· 6· · · · ·        ,        ·6· · · · · · 5··· 6· · · · · ·5· · · · · · 6··· 5· · · · ·        ,        · · 5··· 6· · · · · ·5· · · · · · 6··· 5· · · · · ·6· · · ·        ,        · · 6··· 5· · · · · ·6· · · · · · 5··· 6· · · · · ·5· · · ·        . Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. The number of partial Latin squares related to an autotopism. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. PLSΘ,[P]and PLSΘ,s z∈ CSAPn. Θ∈Iz. P∈ PLSΘ. s∈[n]. PLSΘ,[P]=PLSΘ∩[P] PLSΘ,s=PLSΘ∩ PLSn,s. Lemma The number of isotopic partial Latin squares related to an autotopism only depends on the parastrophic class of the cycle structure of the latter. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Incidence structures. Proposition P∈ PLSn. z∈ CSAPn. ([P],Iz,IPn) is ∆[P](z)-uniform and regular incidence structure. (PLSn,s,Iz,IPn) is ∆s(z)-uniform incidence structure. (PLSn,Iz,IPn) is ∆P(z)-uniform incidence structure. All their blocks have the same multiplicity. Theorem P∈ PLSn. Q∈[P]. |AQ|=|AP|=|IP,Q| Moreover, given Θ ∈AP, it is AQ={Θ0ΘΘ0−1|Θ0∈IP,Q}. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. ∆s(z). Proposition ∆s((n,n,1n)) = (n!2 k!·(n−k)!2,if ∃k∈[n] s.t. s=k·n, 0,otherwise. Proposition ∆n((n,n,n)) = n2 If n>2: ∆2n((n,n,n)) = n2·(n−1)·(n−2) 2. Theorem ∆lz(z) = X (i,j)∈LCMz s.t. lcm(i,j) = lz z1i·z2j·gcd(i,j)·X k∈[n] s.t. (i,j,k)∈LCMn k·z3k. Corollary ∆[P](z)=∆1(z) = z11 ·z21 ·z31. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. 3-PAP. Proposition Θ = (α, β, γ)∈In. There exists a bijection between PLSΘand the set of feasible solutions of:                Pr∈[n]xrcs ≤1,∀c,s∈[n], Pc∈[n]xrcs ≤1,∀r,s∈[n], Ps∈[n]xrcs ≤1,∀r,c∈[n], xrcs =xα(r)β(c)γ(s),∀r,c,s∈[n], xrcs ∈ {0,1},∀r,c,s∈[n]. X r,c,s∈[n] xrcs =m PLSΘ,m Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Gr¨ obner bases. PLSΘ,mis determined by 2n3+ 3n2+ 1 polynomial equations of degree 1 and 2 in n3variables: Corollary Θ = (α, β, γ)∈In. m∈[n2]. PLSΘ,mis the set of zeros of the ideal I: h(Pr∈[n]xrcs )·(1 −Pr∈[n]xrcs ) = 0 |c,s∈[n]i+ h(Pc∈[n]xrcs )·(1 −Pc∈[n]xrcs )|r,s∈[n]i+ h(Ps∈[n]xrcs )·(1 −Ps∈[n]xrcs )|r,c∈[n]i+ hxrcs ·(1 −xrcs )|r,c,s∈[n]i+ hxrcs −xα(r)β(c)γ(s)|r,c,s∈[n]i+ hm−Pr,c,s∈[n]xrcs i ⊆ Q[xn] = Q[x111, ..., xnnn] Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. ∆s(z)and ∆P(z). Order n≤3 n z ∆s(z) ∆P(z)s 1 2 3 4 5 6 7 8 9 1 (1,1,1) 1 1 2 (2,2,2) 4 0 4 (2,2,12) 4 2 6 (12,12,12) 8 16 8 2 34 3 (3,3,3) 9 9 3 21 (3,3,2·1) 3 3 (3,3,13) 9 18 6 33 (2·1,2·1,2·1) 1 10 10 24 24 20 20 4 4 117 (2·1,2·1,13) 3 6 18 6 18 51 (2·1,13,13) 9 18 6 33 (13,13,13) 27 270 1278 3078 3834 2412 756 108 12 11775 Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Basis of LSΘ. Basis of LSΘ:{P1,P2, ..., Pm}, with PiΘ-completable s.t. Si∈[m]LSΘ,Pi=LSΘ LSΘ,Pi∩ LSΘ,Pj=∅, whenever i6=j ⇓ ∆(z) = Pi∈[m]|LSΘ,Pi| Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Basis of LSΘ. Lemma S⊆[n]2. Θ = (α, β, γ)∈An. Each of the following sets is non-empty if and only if it is a basis of LSΘ: SRC ={P∈CΘ|(r,c,s)∈O(P)⇔(r,c)∈S}, SRS ={P∈CΘ|(r,c,s)∈O(P)⇔(r,s)∈S}, SCS ={P∈CΘ|(r,c,s)∈O(P)⇔(c,s)∈S}. Θ = ((12)(3)(4),(12)(3)(4),(34)(1)(2)) S={(3,3),(3,4),(4,3),(4,4)} SRC =     · · · · · · · · · · 1 2 · · 2 1  ,   · · · · · · · · · · 2 1 · · 1 2     Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Homogeneous basis of LSΘ. Homogeneous basis of LSΘ:{P1,P2, ..., Pm}basis of LSΘs.t. |LSΘ,Pi|=|LSΘ,Pj|, for all i,j∈[m]. ⇓ ∆(z) = m· |LSΘ,Pi|, for all i∈[m]. ⇓ m≡Pi-coefficient of symmetry of Θ. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z)Θ-completability Further work. Homogeneous basis of LSΘ. Theorem z= (z1,z2,z3)∈ CSAn z11 ·z21 ·z31 6= 0. Θ = (α, β, γ)∈Iz S={(i,j)∈[n]2|i∈α∞,j∈β∞}. SRC is an homogeneous basis of LSΘof cardinality |LSz11 |.     · · ∗ ◦ · · ∗ ◦   1 2   2 1     ∈ PLS4 Θ = ((12)(3)(4),(12)(3)(4),(34)(1)(2)) S={(3,3),(3,4),(4,3),(4,4)} Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Further work. Application to the calculus of ∆(z). |CSAPn|has been bounded. General expression? General expression for ∆[P](z)? Isotopic classes of PLSn. Examples of order n>4. Comprehensive study of homogeneous bases and coefficients of symmetry. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. References [1] D. Bryant, M. Buchanan and I. M. Wanless, The spectrum for quasigroups with cyclic automorphisms and additional symmetries, Discrete Math. 304 (2009), 821-833. [2] D. A. Cox, J. B. Little and D. O’Shea, Using Algebraic Geometry, Springer-Verlag, New York, 1998. [3] W. Decker, G.-M. Greuel, G. Pfister and H. Sch¨onemann, Singular 3-1-3. A computer algebra system for polynomial computations, 2011. http://www.singular.uni-kl.de. [4] R. Euler, R. E. Burkard and R. Grommes, On Latin squares and the facial structure of related polytopes, Discrete Math. 62 (1986), 155-181. [5] R. M. Falc´on, Latin squares associated to principal autotopisms of long cycles. Application in Cryptography, Proceedings of Transgressive Computing 2006: a conference in honor of Jean Della Dora (2006), 213-230. [6] R. M. Falc´on, Cycle structures of autotopisms of the Latin squares of order up to 11, Ars Combinatoria (in press). Available from http://arxiv.org/abs/0709.2973. [7] R. M. Falc´on, Designs based on the cycle structure of a Latin square autotopism, Proceedings of 1st Hispano-Moroccan Days on Applied Mathematics and Statistics (2008), 479-484. [8] R. M. Falc´on and J. Mart´ın-Morales, Gr¨obner bases and the number of Latin squares related to autotopisms of order ≤7, J. Symbolic Comput. 42 (2007), 1142-1154. [9] R. M. Falc´on and J. Mart´ın-Morales, The 3-dimensional planar assignment problem and the number of Latin squares related to an autotopism, Proceedings of XI Spanish Meeting on Computational Algebra and Applications (2008), 89-92. [10] M. Ghandehari, H. Hatami, E. S. Mahmoodian, On the size of the minimum critical set of a Latin square, Discrete Math. 293 (2005) 121-127. [11] G. H. Hardy, S. and Ramanujan, Asymptotic Formulae in Combinatory Analysis, Proc. London Math. Soc. 17 (1918), 75-115. [12] A. Hulpke, P. Kaski and P. R. J. ¨ Osterg˚ard, The number of Latin squares of order 11, Math. Comp. 80 (2011), 1197-1219. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. References [13] B. Kerby and J. D. H. Smith, Quasigroup automorphisms and symmetric group characters, Comment. Math. Univ. Carol. 51 (2010), 279-286. [14] B. Kerby and J. D. H. Smith, Quasigroup automorphisms and the Norton-Stein complex, Proc. Amer. Math. Soc. 138, No.9 (2010), 3079-3088. [15] S. R. Kumar, A. Russell and R. Sundaram, Approximating Latin square extensions, Algorithmica 24 (1999), 128-138. [16] C. Laywine, An expression for the number of equivalence classes of Latin squares under row and column permutations, J. Combin. Theory Ser. A 30 (1981), 317-321. [17] C. Laywine and G. L. Mullen, Latin cubes and hypercubes of prime order, Fibonacci Quart. 23 (1985), 139-145. [18] B. D. McKay, A. Meynert and W. Myrvold. Small Latin Squares, Quasigroups and Loops, J. Comb. Designs, 15, No.2 (2007), 98-119. [19] B. D. McKay. http://cs.anu.edu.au/∼bdm/data/latin.html. [20] A. A. Sade, Autotopies des quasigroupes et des syst`emes associatives, Arch. Math. 4, No. 1 (1968), 1-23. [21] D. S. Stones, The parity of the number of quasigroups, Discrete Math. 310 (2010), 3033-3039. [22] D. S. Stones, P. Vojtˇechovsk´y and I. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares. Preprint avaliable from http://www.du.edu/media/documents/nsm/mathematics/preprints/ m1101.pdf [23] I. M. Wanless, Diagonally ciclic Latin squares, European J. Combin 25 (2004), 393-413. Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. Introduction CSAPnSizes ∆P(z) Θ-completability Further work. Thank you very much!! Ra´ul M. Falc´on Department of Applied Mathematics I University of Seville (Spain) [email protected] 23rd British Combinatorial Conference Exeter, 3rd to 8th July 2011 Ra´ul M. Falc´on Partial Latin squares related to a given autotopism. View publication statsView publication stats