Concurrence designs based on partial Latin rectangles autotopisms

Concurrence designs based on partial Latin rectangles autotopisms. Ra´ul Falc´on Department of Applied Mathematics I University of Seville (Spain) [email protected] Introduction. IIncidence structures. IPartial Latin rectangles. Introduction. IIncidence structures. IPartial Latin rectangles. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Incidence structures. IAn incidence structure is a triple D= (V,B,I), where Vis a set of v points,Bis a set of b blocks and I⊆ V × B is an incidence relation. IDis k-uniform if every block contains exactly kpoints and it is r-regular if every point is exactly on rblocks. IA1-(v,k,r)design is an incidence structure of vpoints which is k-uniform and r-regular →b·k=v·r. ITwo blocks are equivalent if they contain the same set of points. The multiplicity mult(x)of a block xis the size of its equivalence class. IThe design is simple if all its blocks are distinct. Otherwise, it has multiple blocks. IIf all the blocks have the same multiplicity, then the design can be simplified by identifying equivalent blocks: D → D. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IPLRr,s,n={r×spartial Latin rectangles based on [n] = {1,2, ..., n}}. r×sarrays in which each cell is either empty or contains one symbol of [n], s.t. each symbol occurs at most once in each row and in each column. 1 3 2 4 5 ∈ PLR3,4,5:5 ⊂ PLR3,4,6:5 ⊂... ISize: Number of non-empty cells. →PLRr,s,n:m. Ir=s=nand m=n2:Latin square. n≤11: McKay and Wanless, 2005; Hulpke, Kaski and ¨ Osterg˚ard, 2011. Ir=s=n≤4 and m<n2:Partial Latin square. n≤4: Falc´on, 2012. Partial Latin rectangles. IGeneral case? [Falc´on, 2013; Stones, 2013.] IPOLYNOMIAL METHOD: PLRr,s,n. [Bayern, 1982; Alon, 1995; Bernasconi, 1997] P= (pij )↔xijk =(1,if pij =k, 0,otherwise. Ir,s,n≡         xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRr,s,n=V(Ir,s,n)|PLRr,s,n|= dimQ(Q[x111,...,xrsn]/Ir,s,n) PLRr,s,n:m→Pi∈[r],j∈[s],k∈[n]xijk =m. Partial Latin rectangles. IGeneral case? [Falc´on, 2013; Stones, 2013.] IPOLYNOMIAL METHOD: PLRr,s,n. [Bayern, 1982; Alon, 1995; Bernasconi, 1997] P= (pij )↔xijk =(1,if pij =k, 0,otherwise. Ir,s,n≡         xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRr,s,n=V(Ir,s,n)|PLRr,s,n|= dimQ(Q[x111,...,xrsn]/Ir,s,n) PLRr,s,n:m→Pi∈[r],j∈[s],k∈[n]xijk =m. Partial Latin rectangles. IGeneral case? [Falc´on, 2013; Stones, 2013.] IPOLYNOMIAL METHOD: PLRr,s,n. [Bayern, 1982; Alon, 1995; Bernasconi, 1997] P= (pij )↔xijk =(1,if pij =k, 0,otherwise. Ir,s,n≡         xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRr,s,n=V(Ir,s,n)|PLRr,s,n|= dimQ(Q[x111,...,xrsn]/Ir,s,n) PLRr,s,n:m→Pi∈[r],j∈[s],k∈[n]xijk =m. Partial Latin rectangles. IGeneral case? [Falc´on, 2013; Stones, 2013.] IPOLYNOMIAL METHOD: PLRr,s,n. [Bayern, 1982; Alon, 1995; Bernasconi, 1997] P= (pij )↔xijk =(1,if pij =k, 0,otherwise. Ir,s,n≡         xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRr,s,n=V(Ir,s,n)|PLRr,s,n|= dimQ(Q[x111,...,xrsn]/Ir,s,n) PLRr,s,n:m→Pi∈[r],j∈[s],k∈[n]xijk =m. Symmetries of a partial Latin rectangle. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. ISm: Symmetric group on [m]. ISr×Ss×Sn: Set of isotopisms of PLRr,s,n. Given P= (pij )∈ PLRr,s,n: IOrthogonal representation: O(P)={(i,j,pij )|i∈[r],j∈[s],pij ∈[n]}. IIsotopism (∼): Θ = (α, β, γ)∈Sr×Ss×Sn. O(PΘ) = {(α(i), β(j), γ(pij )) |(i,j,pij )∈O(P)}. IIsotopism class: In,P={Q∈ PLRr,s,n|Q∼P}. IIn(P,Q)={Θ∈Sr×Ss×Sn|PΘ=Q}. IAutotopism group: An(P)=In(P,P). IPLRΘ={P∈ PLRr,s,n|Θ∈An(P)}. IPLRΘ:m={P∈ PLRr,s,n:m|Θ∈An(P)}. |An(P)|=|An(Q)|,∀Q∈In(P).|In,P|=r!·s!·n! |An(P)|. Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. POLYNOMIAL METHOD: In,P. In,P≡                                                              xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i], aij ·(aij −1) = 0,∀i,j∈[r], bij ·(bij −1) = 0,∀i,j∈[s], cij ·(cij −1) = 0,∀i,j∈[n], Pi∈[r]aij = 1,∀j∈[r], Pj∈[r]aij = 1,∀i∈[r], Pi∈[s]bij = 1,∀j∈[s], Pj∈[s]bij = 1,∀i∈[s], Pi∈[n]cij = 1,∀j∈[n], Pj∈[n]cij = 1,∀i∈[n], aik ·bjl ·cpij m·(xklm −1) = 0,∀i,k∈[r],j,l∈[s],pij ,m∈[n], aik ·bjl ·(xklm −1) = 0,∀i,k∈[r],j,l∈[s],m∈[n],such that pij =∅. In,P=V(IP)|In,P|= dimQ(Q[x111,...,cnn]/IP) Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. POLYNOMIAL METHOD: In,P. (But Gr¨obner bases are extremely sensitive to the number of variables!!). In,P≡                                                              xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i], aij ·(aij −1) = 0,∀i,j∈[r], bij ·(bij −1) = 0,∀i,j∈[s], cij ·(cij −1) = 0,∀i,j∈[n], Pi∈[r]aij = 1,∀j∈[r], Pj∈[r]aij = 1,∀i∈[r], Pi∈[s]bij = 1,∀j∈[s], Pj∈[s]bij = 1,∀i∈[s], Pi∈[n]cij = 1,∀j∈[n], Pj∈[n]cij = 1,∀i∈[n], aik ·bjl ·cpij m·(xklm −1) = 0,∀i,k∈[r],j,l∈[s],pij ,m∈[n], aik ·bjl ·(xklm −1) = 0,∀i,k∈[r],j,l∈[s],m∈[n],such that pij =∅. In,P=V(IP)|In,P|= dimQ(Q[x111,...,cnn]/IP) Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. In order to reduce the number variables, we can consider the symmetries of P, i.e., its autotopism group An(P). It is due to the fact that autotopisms decompose Pinto blocks. P≡ 1 3 2 4 5 ∈ PLR3,4,5. A5(P) = (Θ1=Id3,4,5= ((1)(2)(3),(1)(2)(3)(4),(1)(2)(3)(4)(5)), Θ2= ((12)(3),(12)(3)(4),(12)(34)(5)). Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. In order to reduce the number variables, we can consider the symmetries of P, i.e., its autotopism group An(P). It is due to the fact that autotopisms decompose Pinto blocks. P≡ 1 3 2 4 5 ∈ PLR3,4,5. A5(P) = (Θ1=Id3,4,5= ((1)(2)(3),(1)(2)(3)(4),(1)(2)(3)(4)(5)), Θ2= ((12)(3),(12)(3)(4),(12)(34)(5)). Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. In order to reduce the number variables, we can consider the symmetries of P, i.e., its autotopism group An(P). It is due to the fact that autotopisms decompose Pinto blocks. P≡ 1 3 2 4 5 ∈ PLR3,4,5. A5(P) = (Θ1=Id3,4,5= ((1)(2)(3),(1)(2)(3)(4),(1)(2)(3)(4)(5)), Θ2= ((12)(3),(12)(3)(4),(12)(34)(5)). Θ = (α, β, γ)→xijk =xα(i)β(j)γ(k) Symmetries of a partial Latin rectangle. P= (pij )∈ PLRr,s,n. In order to reduce the number variables, we can consider the symmetries of P, i.e., its autotopism group An(P). It is due to the fact that autotopisms decompose Pinto blocks. P≡ 1 3 2 4 5 ∈ PLR3,4,5. A5(P) = (Θ1=Id3,4,5= ((1)(2)(3),(1)(2)(3)(4),(1)(2)(3)(4)(5)), Θ2= ((12)(3),(12)(3)(4),(12)(34)(5)). Θ = (α, β, γ)→xijk =xα(i)β(j)γ(k) Symmetries of a partial Latin rectangle. Θ = (α, β, γ)∈Sr×Ss×Sn. POLYNOMIAL METHOD: PLRΘ IΘ≡                xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk =xα(i)β(j)γ(k), xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRΘ=V(IΘ)|PLRΘ|= dimQ(Q[x111,...,xrsn]/IΘ). If Θ = Idr,s,n= (Idr,Ids,Idn), then IΘ=Ir,s,nand PLRΘ=PLRr,s,n. The number of variables which can be eliminated only depends on the cycle structure of Θ. Symmetries of a partial Latin rectangle. Θ = (α, β, γ)∈Sr×Ss×Sn. POLYNOMIAL METHOD: PLRΘ IΘ≡                xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk =xα(i)β(j)γ(k), xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRΘ=V(IΘ)|PLRΘ|= dimQ(Q[x111,...,xrsn]/IΘ). If Θ = Idr,s,n= (Idr,Ids,Idn), then IΘ=Ir,s,nand PLRΘ=PLRr,s,n. The number of variables which can be eliminated only depends on the cycle structure of Θ. Symmetries of a partial Latin rectangle. Θ = (α, β, γ)∈Sr×Ss×Sn. POLYNOMIAL METHOD: PLRΘ IΘ≡                xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk =xα(i)β(j)γ(k), xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRΘ=V(IΘ)|PLRΘ|= dimQ(Q[x111,...,xrsn]/IΘ). If Θ = Idr,s,n= (Idr,Ids,Idn), then IΘ=Ir,s,nand PLRΘ=PLRr,s,n. The number of variables which can be eliminated only depends on the cycle structure of Θ. Symmetries of a partial Latin rectangle. Θ = (α, β, γ)∈Sr×Ss×Sn. POLYNOMIAL METHOD: PLRΘ IΘ≡                xijk ·(xijk −1) = 0,∀i∈[r],j∈[s],k∈[n], xijk =xα(i)β(j)γ(k), xijk ·xijl = 0,∀i∈[r],j∈[s],k∈[n],l∈[n]\[k], xijk ·xilk = 0,∀i∈[r],j∈[s],k∈[n],l∈[s]\[j], xijk ·xljk = 0,∀i∈[r],j∈[s],k∈[n],l∈[r]\[i]. PLRΘ=V(IΘ)|PLRΘ|= dimQ(Q[x111,...,xrsn]/IΘ). If Θ = Idr,s,n= (Idr,Ids,Idn), then IΘ=Ir,s,nand PLRΘ=PLRr,s,n. The number of variables which can be eliminated only depends on the cycle structure of Θ. The incidence structure (PLRz:m,Sz). z∈ CSr× CSs× CSn IPLRz:m={P∈ PLRr,s,n:m| ∃Θ∈An(P) such that zΘ=z}. ISz={Θ∈Sr×Ss×Sn|zΘ=z}. IIncidence relation:P∈ PLRz:mis on Θ∈ Szif Θ ∈An(P). I|PLRΘ1:m|=|PLRΘ2:m|=∆m(z),∀Θ1,Θ2∈Sz.⇒∆m(z)-uniform. z= (2,2,221) m= 2 |PLRz:m|= 50 |Sz|= 15 ∆m(z) = 10 = 2P+ 8Q Two isotopism classes      P≡1 1→ |I5(P)|= 10 Q≡1 2→ |I5(Q)|= 40 The incidence structure (PLRz:m,Sz). z∈ CSr× CSs× CSn IPLRz:m={P∈ PLRr,s,n:m| ∃Θ∈An(P) such that zΘ=z}. ISz={Θ∈Sr×Ss×Sn|zΘ=z}. IIncidence relation:P∈ PLRz:mis on Θ∈ Szif Θ ∈An(P). I|PLRΘ1:m|=|PLRΘ2:m|=∆m(z),∀Θ1,Θ2∈Sz.⇒∆m(z)-uniform. Which are the properties of such incidence structures? -Multiplicity. -Regularity. -Parameters. The incidence structure (PLRz:m,Sz). z∈ CSr× CSs× CSn IPLRz:m={P∈ PLRr,s,n:m| ∃Θ∈An(P) such that zΘ=z}. ISz={Θ∈Sr×Ss×Sn|zΘ=z}. IIncidence relation:P∈ PLRz:mis on Θ∈ Szif Θ ∈An(P). I|PLRΘ1:m|=|PLRΘ2:m|=∆m(z),∀Θ1,Θ2∈Sz.⇒∆m(z)-uniform. Which is the minimum number of blocks which are necessary to determine all the points of the incidence structure? The incidence structure (PLRz:m,Sz). z∈ CSr× CSs× CSn IPLRz:m={P∈ PLRr,s,n:m| ∃Θ∈An(P) such that zΘ=z}. ISz={Θ∈Sr×Ss×Sn|zΘ=z}. IIncidence relation:P∈ PLRz:mis on Θ∈ Szif Θ ∈An(P). I|PLRΘ1:m|=|PLRΘ2:m|=∆m(z),∀Θ1,Θ2∈Sz.⇒∆m(z)-uniform. Which is the minimum number of blocks which are necessary to determine all the points of the incidence structure? The incidence structure (PLRz:m,Sz). z∈ CSr× CSs× CSn IPLRz:m={P∈ PLRr,s,n:m| ∃Θ∈An(P) such that zΘ=z}. ISz={Θ∈Sr×Ss×Sn|zΘ=z}. IIncidence relation:P∈ PLRz:mis on Θ∈ Szif Θ ∈An(P). I|PLRΘ1:m|=|PLRΘ2:m|=∆m(z),∀Θ1,Θ2∈Sz.⇒∆m(z)-uniform. Which is the cost of computation? The incidence structure (PLRz:m,Sz). Lemma All the blocks of (PLRz:m,Sz) have the same multiplicity. Lemma k≤ |Sz| → The number of points on a given block Θ ∈Szwhich are contained in exactly kblocks of Szdoes not depend on Θ. Proposition Θ∈Sz→If |Az(P)|=|Az(Q)|, for all P,Q∈ PLRΘ:m, then (PLRz:m,Sz) is regular. Lemma a) In,P⊆ PLRz:m, for all P∈ PLRz:m. b) |PLRΘ1:m∩In,P|=|PLRΘ2:m∩In,P|=∆P(z), for all Θ1,Θ2∈Sz. Lemma P∈ PLRz:m→ |Az(Q)|=|Az(P)|, for all Q∈In,P. The incidence structure (PLRz:m,Sz). Lemma All the blocks of (PLRz:m,Sz) have the same multiplicity. Lemma k≤ |Sz| → The number of points on a given block Θ ∈Szwhich are contained in exactly kblocks of Szdoes not depend on Θ. Proposition Θ∈Sz→If |Az(P)|=|Az(Q)|, for all P,Q∈ PLRΘ:m, then (PLRz:m,Sz) is regular. Lemma a) In,P⊆ PLRz:m, for all P∈ PLRz:m. b) |PLRΘ1:m∩In,P|=|PLRΘ2:m∩In,P|=∆P(z), for all Θ1,Θ2∈Sz. Lemma P∈ PLRz:m→ |Az(Q)|=|Az(P)|, for all Q∈In,P. The incidence structure (PLRz:m,Sz). Lemma All the blocks of (PLRz:m,Sz) have the same multiplicity. Lemma k≤ |Sz| → The number of points on a given block Θ ∈Szwhich are contained in exactly kblocks of Szdoes not depend on Θ. Proposition Θ∈Sz→If |Az(P)|=|Az(Q)|, for all P,Q∈ PLRΘ:m, then (PLRz:m,Sz) is regular. Lemma a) In,P⊆ PLRz:m, for all P∈ PLRz:m. b) |PLRΘ1:m∩In,P|=|PLRΘ2:m∩In,P|=∆P(z), for all Θ1,Θ2∈Sz. Lemma P∈ PLRz:m→ |Az(Q)|=|Az(P)|, for all Q∈In,P. The incidence structure (PLRz:m,Sz). Lemma All the blocks of (PLRz:m,Sz) have the same multiplicity. Lemma k≤ |Sz| → The number of points on a given block Θ ∈Szwhich are contained in exactly kblocks of Szdoes not depend on Θ. Proposition Θ∈Sz→If |Az(P)|=|Az(Q)|, for all P,Q∈ PLRΘ:m, then (PLRz:m,Sz) is regular. Lemma a) In,P⊆ PLRz:m, for all P∈ PLRz:m. b) |PLRΘ1:m∩In,P|=|PLRΘ2:m∩In,P|=∆P(z), for all Θ1,Θ2∈Sz. Lemma P∈ PLRz:m→ |Az(Q)|=|Az(P)|, for all Q∈In,P. The incidence structure (PLRz:m,Sz). Lemma All the blocks of (PLRz:m,Sz) have the same multiplicity. Lemma k≤ |Sz| → The number of points on a given block Θ ∈Szwhich are contained in exactly kblocks of Szdoes not depend on Θ. Proposition Θ∈Sz→If |Az(P)|=|Az(Q)|, for all P,Q∈ PLRΘ:m, then (PLRz:m,Sz) is regular. Lemma a) In,P⊆ PLRz:m, for all P∈ PLRz:m. b) |PLRΘ1:m∩In,P|=|PLRΘ2:m∩In,P|=∆P(z), for all Θ1,Θ2∈Sz. Lemma P∈ PLRz:m→ |Az(Q)|=|Az(P)|, for all Q∈In,P. The 1-design (In,P,Sz). = + Proposition The pair (In,P,Sz) is a 1-(|In,P|,∆P(z),|Az(P)|) design, with the incidence relation inherited from (PLRz:m,Sz), such that: IAll its blocks have the same multiplicity. IAll its points have the same multiplicity. IAll its connected components are isomorphic. Proposition Q∈In,P→The number of points which are concurrent with Qon exactly λ blocks does not depend on the choice of Q. Θ∈Sz→The number of blocks which are incident with Θ on exactly λ points does not depend on the choice of Θ. Theorem The 1-design (In,P,Sz) and its dual are m-concurrence designs. Imult(In,P) = maxλ∈Λ{λ}+ 1. The 1-design (In,P,Sz). = + Proposition The pair (In,P,Sz) is a 1-(|In,P|,∆P(z),|Az(P)|) design, with the incidence relation inherited from (PLRz:m,Sz), such that: IAll its blocks have the same multiplicity. IAll its points have the same multiplicity. IAll its connected components are isomorphic. Proposition Q∈In,P→The number of points which are concurrent with Qon exactly λ blocks does not depend on the choice of Q. Θ∈Sz→The number of blocks which are incident with Θ on exactly λ points does not depend on the choice of Θ. Theorem The 1-design (In,P,Sz) and its dual are m-concurrence designs. Imult(In,P) = maxλ∈Λ{λ}+ 1. The 1-design (In,P,Sz). = + Proposition The pair (In,P,Sz) is a 1-(|In,P|,∆P(z),|Az(P)|) design, with the incidence relation inherited from (PLRz:m,Sz), such that: IAll its blocks have the same multiplicity. IAll its points have the same multiplicity. IAll its connected components are isomorphic. Proposition Q∈In,P→The number of points which are concurrent with Qon exactly λ blocks does not depend on the choice of Q. Θ∈Sz→The number of blocks which are incident with Θ on exactly λ points does not depend on the choice of Θ. Theorem The 1-design (In,P,Sz) and its dual are m-concurrence designs. Imult(In,P) = maxλ∈Λ{λ}+ 1. The 1-design (In,P,Sz). The 1-design (In,P,Sz). In general, (In,P,Sz) is not a PBIBD: z= (1,21,221) ∈ CS1× CS3× CS5. P≡1 2                          |In,P|= 60, |Sz|= 45, ∆P(z) = 4, |Az(P)|= 3, mult(In,P) = 2, mult(Sz) = 1, 3 connected components. (Λ = {0,1,3}, n1= 52,n2= 6,n3= 1. Θ=(Id,(12)(3),(12)(34)(5)) Θ = (Id,(12)(3),(12)(35)(4)) Θ=(Id,(12)(3),(12)(45)(3)) 330000110000111100000000000000000000000000000000000000000000 003300000011110000110000000000000000000000000000000000000000 000000000000000000000033000000000011000000000011001100000000 When a m-concurrence design related to a PLR is a PBIBD? The 1-design (In,P,Sz). In general, (In,P,Sz) is not a PBIBD: z= (1,21,221) ∈ CS1× CS3× CS5. P≡1 2                          |In,P|= 60, |Sz|= 45, ∆P(z) = 4, |Az(P)|= 3, mult(In,P) = 2, mult(Sz) = 1, 3 connected components. (Λ = {0,1,3}, n1= 52,n2= 6,n3= 1. Θ=(Id,(12)(3),(12)(34)(5)) Θ = (Id,(12)(3),(12)(35)(4)) Θ=(Id,(12)(3),(12)(45)(3)) 330000110000111100000000000000000000000000000000000000000000 003300000011110000110000000000000000000000000000000000000000 000000000000000000000033000000000011000000000011001100000000 When a m-concurrence design related to a PLR is a PBIBD? References. IN. Alon, Combinatorial Nullstellensatz, Recent trends in combinatorics (M´atrah´aza, 1995). Combin. Probab. Comput. 8 (1999) no. 1–2, 7–29. IA. Bernasconi, B. Codenotti, V. Crespi and G. Resta, Computing Groebner Bases in the Boolean Setting with Applications to Counting, 1st Workshop on Algorithm Engineering (WAE). Venice, Italy, 1997, pp. 209–218. ID. A. Bayer, The division algorithm and the Hilbert scheme. PhD thesis, Harvard University, 1982. IR. M. Falc´on, Clasificaci´on de cuadrados latinos parciales de orden menor o igual a 4. Avances en Matem´atica Discreta en Andaluc´ıa, vol. 2 (2011) 5–12. IR. M. Falc´on, Classification of 5-compressible partial Latin rectangles (2013). Submitted. IA. Hedayat and E. Seiden, F-square and orthogonal F-squares design: A generalization of Latin square and orthogonal Latin squares design, Ann. Math. Statist. (1970) no. 41, 2035–2044. IA. Hulpke, P. Kaski and P. R. J. ¨ Osterg˚ard, The number of Latin squares of order 11, Math. Comp. 80 (2011) no. 274, 1197–1219. IR. G. Jarrett, Definitions and properties for m-concurrence designs, J. Roy. Statist. Soc. Ser. B 45 (1983) no. 1, 1–10. IB. D. McKay and I. M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005) no. 3, 335–344. IS. C. Saxena, On simplification of certain types of BIBDs, Indian J. Pure Appl. Math. 16 (1985) no. 2, 103–106. ID. S. Stones, Petr Vojt˘echovsk´y and I. M. Wanless, Cycle structure of autotopisms of quasigroups and Latin squares, J. Combin. Des. 20 (2012) no. 20, 227–263. Thank you!!