New advances concerning critical sets based on Latin square autotopisms

New advances concerning critical sets based on Latin square autotopisms Ra´ul M. Falc´on∗ Department of Applied Maths I. Universidad de Sevilla. [email protected] Kongunadu Arts and Science College. Tamil Nadu, India. January 29, 2021. 4th International Conference on Current Scenario in Pure and Applied Mathematics (ICCSPAM 2021) ∗Joint work with Laura Johnson (University of St. Andrews) and Stephanie Perkins (University of South Wales). 12345 21453 34512 45231 53124 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 1 / 43 CONTENTS 1Preliminaries. 2Critical sets based on Latin square autotopisms. 3Open questions. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 2 / 43 CONTENTS 1Preliminaries. 2Critical sets based on Latin square autotopisms. 3Open questions. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 3 / 43 Quasigroup. Ruth Moufang (1935) Aquasigroup is a pair Q= (S,·)formed by •a finite set S •a product · such that both equations a·x=band y·a=b have unique solutions x,y∈S, for all a,b∈S. The multiplication table of Qis a Latin square. 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 ∈LS4 Associative quasigroup = Group. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 4 / 43 Latin square. Arthur Cayley (1854) Leonhard Euler (1767) Choe Seok-Jeong (1700) Ram´on Llull (1283) Ra´ul M. Falc´on Critical sets on Latin square autotopisms 5 / 43 Latin square. Ahmad al-Buni (1225) Earrings founded in Damascus (1000) ≡ 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 6 / 43 Partial Latin square. L= (lij )≡ 1 2 3 · ·3· · 3·1 4 ·1·3 Entry set:Ent(L) := {(row,column,symbol)}={(i,j,lij )}. Ent(L) = {(1,1,1),(1,2,2),(1,3,3) (2,2,3), (3,1,3),(3,3,1),(3,4,4), (4,2,1),(4,4,3)}. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 7 / 43 Critical set. 1· · 4 ·1 4 · 3·2 1 431· uniquely completable to 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 Critical set: Uniquely completable PLS such that any proper subset of entries is not uniquely completable. 1· · 4 ·1· · 3·2· · · · · → 1· · 4 ·1· · 3 4 2 1 · · · · → 1· · 4 ·1 4 · 3 4 2 1 4·1· → 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 8 / 43 Latin square isotopism. Sn≡Symmetric group on [n] := {1,...,n}. Sn×Sn×Sn≡Isotopism group. Θ = (α, β, γ)∈Sn×Sn×Snand L∈LSn. Ent(LΘ) = {(α(i), β(j), γ(k)|(i,j,k)∈Ent(L)}. Row-permutations (α), column-permutations (β), symbol-permutations (γ). L≡ ·2 4 · ·1· · 3 5 2 4 · · · · {(1,2,2),(1,3,4),(2,2,1),(3,1,3)} ⊂ Ent(L). ⇓Θ = ((1 2)(3),(1 2 3 4),(12)(345)) ∈S3×S4×S5. LΘ≡ · · 2· · · 1 5 5 4 3 1 · · · · {(2,3,1),(2,4,5),(1,3,2),(3,2,4)} ⊂ Ent(L). Ra´ul M. Falc´on Critical sets on Latin square autotopisms 9 / 43 Latin square autotopism. If LΘ=L, then Θ is called an autotopism of L. Atop(L)={Autotopisms of L} ≡ Autotopism group L≡ 3·2 ·3 1 2 1 · Θ = ((1 2)(3),(1 2)(3),(12)(3)) ∈Atop(L). Applications: Enumeration and classification of discrete structures. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 12 / 43 Origin of the concept of isotopism [Albert, 1942]. Abraham Adrian Albert United States, 1905-1972 Two algebras (A1,·) and (A2,◦) are isotopic if there exist three nonsingular linear transformations α, β, γ :A1→A2 such that α(x)◦β(y) = γ(x·y), for all x,y∈A1. Isotopism:Θ=(α, β, γ). If α=β=γ, then this is an isomorphism. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 13 / 43 Isotopism of quasigroups [Bruck, 1944]. Richard Hubert Bruck United States, 1914-1991 Two quasigroups (Q1,·) and (Q2,◦) are isotopic if there exist three bijections α, β, γ :Q1→Q2 such that α(x)◦β(y) = γ(x·y), for all x,y∈Q1. •Isotopism:Θ=(α, β, γ). •α=β=γ⇒Isomorphic. In its related Latin square: α: Permutation of rows. β: Permutation of columns. γ: Permutation of symbols.                    L≡ 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 Θ = ((1 2)(3 4),(2 3),Id) ⇒LΘ≡ 2 4 3 1 1 3 2 4 4 2 1 3 3 1 4 2 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 14 / 43 A historical perspective of the theory of isotopisms. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 15 / 43 LS isotopism ≡Graph isomorphism. McKay, B.D., Meynert, A., Myrvold, W. Small Latin Squares, Quasigroups and Loops. J. Combin. Des. 15 (2007), 98–119. Brendan D. McKay Alison M. Meynert Wendy Myrvold 1 2 2 1 ≡ Isotopic Latin squares ≡Isomorphic coloured graphs Ra´ul M. Falc´on Critical sets on Latin square autotopisms 16 / 43 LS isotopism ≡Graph isomorphism. McKay, B.D., Meynert, A., Myrvold, W. Small Latin Squares, Quasigroups and Loops. J. Combin. Des. 15 (2007), 98–119. Brendan D. McKay Alison M. Meynert Wendy Myrvold Cycle structure:π= (1234)(56)(78)(9) →zπ= 41221. Known for all LS of order n≤17 [Falc´on, 2012; Stones, 2012]. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 17 / 43 LS isotopism ≡Graph isomorphism. McKay, B.D., Meynert, A., Myrvold, W. Small Latin Squares, Quasigroups and Loops. J. Combin. Des. 15 (2007), 98–119. Brendan D. McKay Alison M. Meynert Wendy Myrvold Cycle structure:π= (1234)(56)(78)(9) →zπ= 41221. Known for all LS of order n≤17 [Falc´on, 2012; Stones, 2012]. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 17 / 43 CONTENTS 1Preliminaries. 2Critical sets based on Latin square autotopisms. 3Open questions. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 18 / 43 Θ-critical set. Θ = ((12)(34),(12)(34),Id)∈Atop(L) 1· · 4 ·1 4 · 3·2 1 4 3 1 · Θ-uniquely completable to 1234 2143 3421 4312 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 19 / 43 Θ-critical set. Θ = ((12)(34),(12)(34),Id)∈Atop(L) · · · 4 ·1· · 3·2 1 4· · · Θ-uniquely completable to 1234 2143 3421 4312 Critical set: Uniquely completable PLS such that any proper subset of entries is not uniquely completable. 1· · 4 ·1· · 3·2· · · · · → 1· · 4 ·1· · 3 4 2 1 · · · · → 1· · 4 ·1 4 · 3 4 2 1 4·1· → 1 2 3 4 2 1 4 3 3 4 2 1 4 3 1 2 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 20 / 43 Three main questions. L∈LSnand Θ ∈Atop(L) Determine the exact values of |CSΘ(L)|:= Number of Θ-critical sets of L. scsΘ(L):= Size of the smallest Θ-critical set of L. lcsΘ(L):= Size of the largest Θ-critical set of L. Lemma These values only depend on The cycle structure of the autotopism Θ. The main class∗of the Latin square L. ∗Two Latin squares belong to the same main class if they coincide up to isotopism and permutation among the three components of their entries. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 25 / 43 The case n≤5. L2≡1 2 2 1 L3≡ 1 2 3 2 3 1 3 1 2 L4.1≡ 1234 2143 3412 4321 L4.2≡ 1234 2143 3421 4312 LΘ∈Atop(L)zΘ|CSΘ(L)|scsΘ(L)lcsΘ(L) L2(Id2,Id2,Id2) (12 ,12 ,12) 4 1 1 ((12),(12),Id2) (2,2,12) 4 1 1 L3(Id3,Id3,Id3) (13 ,13 ,13) 27 2 3 ((12),(12),(13)) (21,21,21) 14 1 2 ((123),(132),Id3)) (3,3,13) 27 2 2 ((123),(123),(132)) (3,3,3) 9 1 1 L4.1(Id4,Id4,Id4) (14 ,14 ,14) 576 5 7 ((12)(34),(12)(34),Id4) (22 ,22 ,14) 192 4 4 ((23),(14),(14)) (212 ,212 ,212) 256 4 4 ((12)(34),(13)(24),(14)(23)) (22 ,22 ,22) 256 3 3 ((243),(134),(134)) (31,31,31) 90 2 2 ((1234),(1234),(24)) (4,4,212) 64 2 2 L4.2(Id4,Id4,Id4) (14 ,14 ,14) 736 4 6 ((12)(34),(12)(34),Id4) (22 ,22 ,14) 192 4 4 ((13)(24),(14)(23),(34)) (22 ,22 ,212) 224 3 3 ((12),(12),(34)) (212 ,212 ,212) 256 4 4 ((1324),(1324),(12)(34)) (4,4,22) 64 2 2 ((1423),(1324),Id4) (4,4,14) 256 3 3 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 26 / 43 The case n≤5. L5.1≡ 12345 23451 34512 45123 51234 L5.2≡ 12345 21453 34512 45231 53124 LΘ∈Atop(L)zΘ|CSΘ(L)|scsΘ(L)lcsΘ(L) L5.1(Id5,Id5,Id5) (15 ,15 ,15) 53250 6 10 ((12)(35),(13)(45),(14)(23)) (221,221,221) 3088 3 5 ((2354),(1243),(1243)) (41,41,41) 832 3 3 ((12345),(15432),Id5) (5,5,15) 3125 4 4 ((12345),(12345),(13524)) (5,5,5) 250 2 2 L5.2(Id5,Id5,Id5) (15 ,15 ,15) 48462 7 11 ((13)(45),(25)(34),(13)(45)) (221,221,221) 2896 3 5 ((345),(345),(345)) (312 ,312 ,312) 8424 5 6 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 27 / 43 The case n= 2. L∈LSnand Θ ∈Atop(L) Proposition 0<scsΘ(L)≤lcsΘ(L)≤ |OrbΘ(L)|. Θ = ((12),(12),Id) L2≡1 2 2 1 . lcsΘ(L2)≤2. Every entry is Θ-forced by any other given entry. So, scsΘ(L2) = lcsΘ(L2) = 1 and |CSΘ(L2)|= 4. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 28 / 43 The case n= 3. Proposition If there exist msecondary parallel Θ-orbits of the same type, then every Θ-critical set of Lcontains at least m−1entries. Hence, m−1≤scsΘ(L). Θ = ((123),(132),Id) L3≡ 1 2 3 2 3 1 3 1 2 2≤scsΘ(L3)≤lcsΘ(L3)≤3. Every entry is Θ-forced by any two entries of two distinct secondary Θ-orbits. So, scsΘ(L3) = lcsΘ(L3) = 2 and |CSΘ(L3)|= 27. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 29 / 43 L∈LSnand Θ = (α, β, Id)∈Atop(L) Theorem If zα=zβ=n, then a) scsΘ(L) = lcsΘ(L) = n−1. b) |CSΘ(L)|=nn. Θ = ((12),(12),Id) Θ = ((123),(132),Id) 1 2 2 1 123 231 312 scsΘ(L2) = lcsΘ(L2)=1 scsΘ(L3) = lcsΘ(L3) = 2 |CSΘ(L2)|= 4 |CSΘ(L3)|= 27 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 30 / 43 The case n= 3. Θ = ((123),(123),(132)) L3≡ 1 2 3 2 3 1 3 1 2 Any of its entries gives rise to a Θ-critical set of order one. So, scsΘ(L3) = lcsΘ(L3) = 1 and |CSΘ(L3)|= 9. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 31 / 43 The case n= 4. Θ = ((1234),(1234),(24)) L4.1≡ 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 Every Θ-critical set is a PLS of order two containing: One entry of a symbol-monotone Θ-orbit. One entry of a non-monotone Θ-orbit. So, scsΘ(L4.1) = lcsΘ(L4.1) = 2 and |CSΘ(L4.1)|= 64. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 32 / 43 The case n= 5. Θ = ((12345),(12345),(13524)) L5.1≡ 1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4 Every entry is Θ-forced by any two entries of a pair of different Θ-orbits. So, scsΘ(L5.1) = lcsΘ(L5.1) = 2 and |CSΘ(L5.1)|= 250. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 33 / 43 Trivial orbits. Lemma If there exists exactly one trivial orbit, then no Θ-critical set contains that entry. Θ = ((12),(12),(13)) L3≡ 1 2 3 2 3 1 3 1 2 Every Θ-critical set of L3contains exactly either one entry of the principal Θ-orbit; or two entries of two distinct secondary Θ-orbits. So, scsΘ(L3)=1<lcsΘ(L3)=2and |CSΘ(L3)|= 14. 1 2 3 2 3 3 3 Ra´ul M. Falc´on Critical sets on Latin square autotopisms 34 / 43 Open questions. Question What is the computational complexity of deciding whether a partial Latin square is Θ-completable? Question Does a Θ-critical set of size mexist for every m∈ {scsΘ(L),...,lcsΘ(L)}? Question Find lower and upper bounds for: scsΘ(n):= Smallest size of a Θ-critical set for every LS of order n. lcsΘ(n):= Largest size of a Θ-critical set for every LS of order n. Question Is it possible to find general formulas of scsΘ(L),lcsΘ(L)and |CSΘ(L)|for some specific cycle structures? Ra´ul M. Falc´on Critical sets on Latin square autotopisms 41 / 43 Open questions. Question The existence of non-monotone Θ-orbits is common for LS of higher orders. Θ = ((123456),(123)(456),(14)(25)(36)) ∈S6×S6×S6 1 2 3 4 5 6 6 4 5 3 1 2 2 3 1 5 6 4 4 5 6 1 2 3 3 1 2 6 4 5 5 6 4 2 3 1 How many types of non-monotone orbits exist? What is the role played by each one of them in the construction of Θ-critical sets? Ra´ul M. Falc´on Critical sets on Latin square autotopisms 42 / 43 REFERENCES Albert, A.A. Non-Associative Algebras: I. Fundamental Concepts and Isotopy. Ann. Math. 43 (1942), 685–707. Bruck, R.H. Some results in the theory of linear non-associative algebras. Trans. Am. Math. Soc. 56 (1944), 141–199. Falc´on, R.M. Cycle structures of autotopisms of the Latin squares of order up to 11. Ars Combinatoria 103 (2012), 239–256. Falc´on, R.M., Falc´on, O.J., N´u˜nez, J. A Historical Perspective of the Theory of Isotopisms, Symmetry 10:8 (2018), paper 322, 1–21. Falc´on, R.M., Johnson, L., Perkins, S. A census of critical sets based on non-trivial autotopisms of Latin squares of order up to five. AIMS Mathematics 6:1 (2021) 261–295. McKay, B.D., Meynert, A., Myrvold, W. Small Latin Squares, Quasigroups and Loops. J. Combin. Des. 15 (2007), 98–119. Moufang, R. Zur Struktur von Alternativk¨orpern. Math. Ann. 110 (1935), 416–430. Stones, D.S., Vojtˇechovsk´y, Wanles, I.M. Cycle structure of autotopisms of quasigroups and latin squares. J. Comb. Des. 20:5 (2012) 227–263. Ra´ul M. Falc´on Critical sets on Latin square autotopisms 43 / 43 Many thanks! New advances concerning critical sets based on Latin square autotopisms Ra´ul M. Falc´on∗ Department of Applied Maths I. Universidad de Sevilla. [email protected] Kongunadu Arts and Science College. Tamil Nadu, India. January 29, 2021. 4th International Conference on Current Scenario in Pure and Applied Mathematics (ICCSPAM 2021) ∗Joint work with Laura Johnson (University of St. Andrews) and Stephanie Perkins (University of South Wales). Ra´ul M. Falc´on Critical sets on Latin square autotopisms 44 / 43 View publication statsView publication stats