Partial latin squares with no non-trivial autotopisms and six autoparatopisms

Partial Latin Squares with no Non-trivial Autotopisms and Six Autoparatopisms Rebecca J. Stones (Nankai University, China) joint work with Ra´ul Falc´on (University of Seville, Spain). June 16, 2015 Partial Latin squares No symbol repeats in any row, or any column. nrows ncolumns nsymbols: mnon-empty cells (its weight) Every row, column, and symbol is “used”. Partial Latin squares No symbol repeats in any row, or any column. nrows ncolumns nsymbols: mnon-empty cells (its weight) Every row, column, and symbol is “used”. Partial Latin squares No symbol repeats in any row, or any column. nrows ncolumns nsymbols: mnon-empty cells (its weight) Every row, column, and symbol is “used”. Isotopisms and autotopisms Starting with a partial Latin square, if we permute the rows, permute the columns, and permute the symbols we obtain another partial Latin square.            1234 · · 231 · · · · · · 5· · · · · 6 5 · · · · · 6 5 · · · · · 6            swap first two rows swap last two columns −−−−−−−−−−−−−→            231 · · · 1234 · · · · · 5· · · · · 6·5 · · · · 5 6 · · · · 6·            These operations are called isotopisms. If we end up with original partial Latin square, it’s called an autotopism. "1· ·2# swap the two rows swap the two columns swap the two symbols −−−−−−−−−−−−−→ "1· ·2# Isotopisms and autotopisms Starting with a partial Latin square, if we permute the rows, permute the columns, and permute the symbols we obtain another partial Latin square.            1234 · · 231 · · · · · · 5· · · · · 6 5 · · · · · 6 5 · · · · · 6            swap first two rows swap last two columns −−−−−−−−−−−−−→            231 · · · 1234 · · · · · 5· · · · · 6·5 · · · · 5 6 · · · · 6·            These operations are called isotopisms. If we end up with original partial Latin square, it’s called an autotopism. "1· ·2# swap the two rows swap the two columns swap the two symbols −−−−−−−−−−−−−→ "1· ·2# Paratopisms and autoparatopisms Partial Latin squares are equivalent to their entries, (row, column, symbol) triples: "12 2·#←→ (1,1,1) (1,2,2) (2,1,2) We have another operation which preserves “partial Latin square”-ness: we uniformly permute the coordinates of the entries. (1,1,1) (1,2,2) (2,1,2) swap first two coordinates −−−−−−−−−−−−−−−→ (1,1,1) (2,1,2) (1,2,2) Combining this operation with isotopism, gives us paratopisms (α, β, γ;δ)∈(Sn×Sn×Sn)oS3. A paratopism that maps a partial Latin square to itself is called an autoparatopism. (isotopism, autotopism ⇐⇒ δ=id) Paratopisms and autoparatopisms Partial Latin squares are equivalent to their entries, (row, column, symbol) triples: "12 2·#←→ (1,1,1) (1,2,2) (2,1,2) We have another operation which preserves “partial Latin square”-ness: we uniformly permute the coordinates of the entries. (1,1,1) (1,2,2) (2,1,2) swap first two coordinates −−−−−−−−−−−−−−−→ (1,1,1) (2,1,2) (1,2,2) Combining this operation with isotopism, gives us paratopisms (α, β, γ;δ)∈(Sn×Sn×Sn)oS3. A paratopism that maps a partial Latin square to itself is called an autoparatopism. (isotopism, autotopism ⇐⇒ δ=id) Paratopisms and autoparatopisms Partial Latin squares are equivalent to their entries, (row, column, symbol) triples: "12 2·#←→ (1,1,1) (1,2,2) (2,1,2) We have another operation which preserves “partial Latin square”-ness: we uniformly permute the coordinates of the entries. (1,1,1) (1,2,2) (2,1,2) swap first two coordinates −−−−−−−−−−−−−−−→ (1,1,1) (2,1,2) (1,2,2) Combining this operation with isotopism, gives us paratopisms (α, β, γ;δ)∈(Sn×Sn×Sn)oS3. A paratopism that maps a partial Latin square to itself is called an autoparatopism. (isotopism, autotopism ⇐⇒ δ=id) The first step... Claim: These partial Latin squares...   123 2 3 · 3·1     1234 234· 3 4 · · 4· · 1           12345 2345· 345· · 4 5 ··· 5···1               123456 23456· 3456· · 456··· 5 6 · · · · 6· · · · 1         ...have no non-trivial autotopisms, and... ...have six autoparatopisms. To prove , we observe that most rows and columns contain a unique number of entries. [+ a bit of tidying up.] To prove , we just identify two generators of the autoparatopism group (the easy one is the matrix transpose). The first step... Claim: These partial Latin squares...   123 2 3 · 3·1     1234 234· 3 4 · · 4· · 1           12345 2345· 345· · 4 5 ··· 5···1               123456 23456· 3456· · 456··· 5 6 · · · · 6· · · · 1         ...have no non-trivial autotopisms, and... ...have six autoparatopisms. To prove , we observe that most rows and columns contain a unique number of entries. [+ a bit of tidying up.] To prove , we just identify two generators of the autoparatopism group (the easy one is the matrix transpose). The first step... Claim: These partial Latin squares...   123 2 3 · 3·1     1234 234· 3 4 · · 4· · 1           12345 2345· 345· · 4 5 ··· 5···1               123456 23456· 3456· · 456··· 5 6 · · · · 6· · · · 1         ...have no non-trivial autotopisms, and... ...have six autoparatopisms. To prove , we observe that most rows and columns contain a unique number of entries. [+ a bit of tidying up.] To prove , we just identify two generators of the autoparatopism group (the easy one is the matrix transpose). The first step... Claim: These partial Latin squares...   123 2 3 · 3·1     1234 234· 3 4 · · 4· · 1           12345 2345· 345· · 4 5 ··· 5···1               123456 23456· 3456· · 456··· 5 6 · · · · 6· · · · 1         ...have no non-trivial autotopisms, and... ...have six autoparatopisms. To prove , we observe that most rows and columns contain a unique number of entries. [+ a bit of tidying up.] To prove , we just identify two generators of the autoparatopism group (the easy one is the matrix transpose). The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The second step... Claim: These partial Latin squares also...           1234567 234567· 3 4 ·6 7 · · 4567··· 567· · · · 6 7 ····· 7······                       12345678 2345678· 3 4 · · 7 8 · · 4 5 ·7 8 ··· 5678· · · · 678····· 7 8 ······ 8·······                           123456789 23456789· 3 4 ···8 9 · · 4 5 · · 8 9 ··· 5 6 ·8 9 · · · · 6789····· 789······ 8 9 ······· 9········               ...have no non-trivial autotopisms, and... ...have six autoparatopisms. We delete all entries except those in the first two rows, the first two columns, or with the last two symbols. To prove , we observe (a) the first two rows/columns map to themselves (unique no. entries), implying autotopisms have the form (α, α, α;id) where αfixes 1 and 2, and (b) the entry (2,i,i+ 1) exists for i∈ {2,3,...,n−1}, so we get the induction “ifixed =⇒i+ 1 fixed”. ( : same as before.) The 1.5-nd step... We deleted entries that belong to orbits under the autoparatopism group apar(· · · ). If we delete the orbit of an entry, we can only increase the number of symmetries (autotopisms and autoparatopisms). So, if we only delete entries belonging to some of those orbits: apar(delete all indicated orbits) ≥apar(delete some orbits) ≥apar(delete no orbits) And we just showed the these two have size six. So, we get a bunch of partial Latin squares of order nwith no non-trivial autotopisms and six autoparatopisms. Deleting orbits... The orbits we can delete have sizes 1, 3, or 6.                           1 2 3 4 5 6 7 8 9 10 11 12 13 2 3 4 5 6 7 8 9 10 11 12 13 · 3 4 5 6 7 8 9 10 11 12 13 · · 4 5 6 7 8 9 10 11 12 13 · · · 5 6 7 8 9 10 11 12 13 · · · · 6 7 8 9 10 11 12 13 · · · · · 7 8 9 10 11 12 13 · · · · · · 8 9 10 11 12 13 · · · · · · · 9 10 11 12 13 · · · · · · · · 10 11 12 13 · · · · · · · · · 11 12 13 · · · · · · · · · · 12 13 · · · · · · · · · · · 13 · · · · · · · · · · · 1                           We can delete some selections of these orbits, giving, for a given n, a range of weights mfor which there exists a partial Latin square of order nweight mwith no non-trivial autotopisms and six autoparatopisms. Where we are now... This is where we are now. We still need to fill in the gaps: We can do m≡0,1 (mod 3) in this way; but what about m≡2 (mod 3)? These partial Latin squares have at most n+1 2+ 1 entries; can we give such constructions with more entries? Where we are now... This is where we are now. We still need to fill in the gaps: We can do m≡0,1 (mod 3) in this way; but what about m≡2 (mod 3)? These partial Latin squares have at most n+1 2+ 1 entries; can we give such constructions with more entries?