Two-line graphs of partial Latin rectangles

Two-line graphs of partial Latin rectangles Eiran Danan 1 Department of Computer Science, Tel-Hai College, Upper Galilee, Israel Ra´ul M. Falc´on 2 School of Building Engineering, Universidad de Sevilla, Sevilla, Spain Dani Kotlar 3 Department of Computer Science, Tel-Hai College, Upper Galilee, Israel Trent G. Marbach 4 College of Computer and Control Engineering, Nankai University, Tianjin, China Rebecca J. Stones 5 College of Computer and Control Engineering, Nankai University, Tianjin, China Abstract Two-line graphs of a given partial Latin rectangle are introduced as vertex-and- edge-coloured bipartite graphs that give rise to new autotopism invariants. They reduce the complexity of any currently known method for computing autotopism groups of partial Latin rectangles. Keywords: partial Latin rectangle, autotopism group, entry invariant, adequate partition. 1 Introduction Let [n]:={1,...,n}.Anr×spartial Latin rectangle based on [n]isanr×s array L=(L[i, j]) containing symbols from the set [n]∪{·}such that each row and each column contains at most one copy of any symbol in [n]. The set of such rectangles is denoted PLR(r, s, n). The partial Latin rectangle L is uniquely determined by its entry set Ent(L):={(i, j, L[i, j]) : i∈[r],j ∈[s],L[i, j]∈[n]}. Any triple (i, j, L[i, j]) ∈Ent(L) is called an entry of L, and any pair (i, j)∈ [r]×[s]isacell. Any cell (i, j)inLcontaining the symbol ·is said to be empty.IfLdoes not have empty cells, then it is a Latin rectangle. This is a Latin square of order nif r=s=n. For each t∈N,letStdenote the symmetric group on [t]. An isotopism θ=(α, β, γ)∈Sr×Ss×Snacts on the set PLR(r, s, n), by permuting the rows, columns, and symbols of any L∈PLR(r, s, n)byα,β,andγ,respectively. This is an autotopism of Lif θ(L)=L. The set Atop(L) of autotopisms of Lforms a group, called its autotopism group. Although autotopism groups of Latin rectangles have received much attention in the literature (see [1,4,11,12,13] and many others), those of partial Latin rectangles have only recently been studied [5,7,9]. Methods for obtaining such groups are based either on a backtracking computation of non-polynomial time complexity, or on the computation of the automorphism group of a related graph [6,12]. The problem of computing the autotopism group of a (partial) Latin rectangle is, therefore, as difficult as solving the graph isomorphism problem [2,3]. In order to reduce as low as possible the related complexity, different autotopism invariants of (partial) Latin rectangles have been described [6,8,10,11,14]. All of them yield a series of partitions of the entries, rows, columns and/or symbols of the corresponding (partial) Latin rectangle so that all their parts are preserved by autotopisms. Nevertheless, no invariant whose corresponding partitions are optimal is currently known. Here we introduce new autotopism invariants that give rise to partitions that are closer to optimal than before. 1Email: [email protected] 2Email: [email protected] 3Email: [email protected] 4Email: [email protected] 5Email: [email protected] 54 2 Adequate partitions and derived refinement Let Sbe a finite set. From here on, let a∼Pbdenote the fact that two elements a, b ∈Sare in the same part of a partition Pof S. Let L=(L[i, j]) ∈PLR(r, s, n). Any partition Pof the set [r] constitutes arow-partition of L.Thisisadequate if it is preserved by any autotopism (α, β, γ)∈Atop(L), that is, if i∼Pα(i), for all i∈[r]. The concepts of (adequate) column-,symbol- and entry–partitions are analogously introduced with respect to the sets [s], [n]andEnt(L), respectively. A system of partitions on Lis a triple P=(Prow,Pcol,Psym), whose components are, respectively, a row-, a column- and a symbol-partition of L. This is adequate if its three components are. Further, Pproduces a partition E(P) of the entry set E(L) so that (i, j, L[i, j]) ∼E(P)(i,j,L[i,j]) if and only if i∼Prow i,j∼Pcol j and L[i, j]∼Psym L[i,j]. If we label the entries of Lso that two entries have the same label whenever they belong to the same part of E(P), then we can define a new system of partitions D(P)=(D(Prow),D(Pcol),D(Psym)) of L. Here, two rows are in the same part of D(Prow) if and only if the multisets of labels corresponding to their entries coincide. The partitions D(Pcol)and D(Psym) are similarly defined. We call D(P)thederivation of P. Example 2.1 The row type,column type and symbol type of L∈PLR(r, s, n) are defined [10,14], respectively, as the number of entries per row, the number of entries per column, and the number of appearances of each symbol in the set [n] within L. The respective distributions of rows, columns and symbols of Laccording to these types determine a system of partitions on L, which we denote PT(L). Then, D(PT(L)) = PSEI(L), where PSEI(L) is the system of partitions on Lthat arises from the so-called strong entry invariants [6,8].  A system Pdefined on Lis finer than Pif each component of Pis finer than the corresponding component of P.WedenotethisfactasP≤P. Theorem 2.2 Let Pbe a system of partitions on a partial Latin rectangle. Then, (i) if Pis adequate, so is D(P), (ii) D(P)≤P, and (iii) if Pis another system of partitions so that P≤P, then D(P)≤D(P). For each given adequate system of partitions P, let us consider the sequence ... ≤P(2) ≤P(1) ≤P(0) =P,whereP(i):= DP(i−1),foreach i>0, until we find a positive integer m>0 so that P(m)=P(m−1).Wecall the resulting adequate system of partitions D[P]thederived refinement of P. 55 3 The two-lines invariant In this section we define a system of partitions whose derived refinement is finer than the derived refinement of the system of partitions arising from the strong entry invariants, which is described in Example 2.1. To this end, let L=(L[i, j]) ∈PLR(r, s, n). For each pair (r1,r 2) of different row indexes in L, we define their two-row graph of Las the vertex-and-edge-coloured bipartite graph Gr1r2(L):=(Vr1(L)∪Vr2(L),E r1r2(L)) as follows: •For each i∈{r1,r 2}, the set Vi(L) is identified with the set {(i, j, L[i, j]) ∈ E(L): j∈[s]}. The vertices in Vr1(L) are coloured white and labeled as wL[r1,j], whereas those in Vr2(L) are colored black and labeled as bL[r2,j]. •For each j∈[s] such that wL[r1,j]∈Vr1(L)andbL[r2,j]∈Vr2(L), we draw the edge wL[r1,j]bL[r2,j]as a solid line. •For each k∈[n]suchthatwk∈Vr1(L)andbk∈Vr2(L), we draw the edge wkbkas a dashed line. •There are no other edges in the graph. Example 3.1 Let L≡2·3·6·1 4 3 2 ·6·4·5 ∈PLR(2,8,6). Then, G12(L)≡ w2w3w6w1w4 b3b2b6b4b5  Two-column and two-symbol graphs of Lare similarly defined by taking the corresponding two-rows graphs of L(12) and L(13), respectively. Here, for each pair of distinct elements i, j ∈{1,2,3}, the partial Latin rectangle L(ij)is obtained from Lby swapping the ith and jth components of each of its entries. We use the general term two-lines graph for these three types of graphs. Since all of them consist of disjoint paths and cycles, verifying whether two graphs are isomorphic can be done in linear time complexity. Let us use this fact to construct new adequate systems of partitions. 56 If r1,r 2,r 3,r 4are rows in Lsuch that r1=r2and r3=r4, then we write (r1,r 2)∼(r3,r 4)ifGr1r2is isomorphic to Gr3r4.Now,letPbe an adequate row-partition of L. Then, we define an equivalence relation ∼G(P)on the rows of Las follows: r1∼G(P)r2if and only if (i) r1∼Pr2, (ii) for any row ri=r1, there exists a row rj=r2such that ri∼Prj,and (r1,r i)∼(r2,r j), and (iii) for any row ri=r2, there exists a row rj=r1such that ri∼Prj,and (r2,r i)∼(r1,r j). This relation gives rise to an adequate row-partition G(P)≤P, which can be refined again by repeating this procedure. In this way, we define a sequence ... ≤P (2) ≤P (1) ≤P (0) =P,whereP(i)=G(P(i−1)), for all i>0, until no further refinement is achieved. We call the resulting adequate row-partition G[P]thetwo-row graph refinement of P. Refinements of columns and symbols are described in a similar manner. Thus, from an adequate system of partitions P=(Prow,Pcol,Psym), we compute the two-line graph refinement G[P]:= (G[Prow],G[Pcol],G[Psym]). This works even if Pis the system of singletons. Theorem 3.2 Let Pand Pbe two systems of partitions on a partial Latin rectangle L.IfP≤P, then G[P]≤G[P]. Theorem 3.3 The complexity of the two-line graph refinement of an adequate system of partitions on a partial Latin rectangle L∈PLR(r, s, n)in the worst case scenario is at most O(M6log M), where M= max(r, s, n). Theorem 3.4 Let Pbe an adequate system of partitions on a given partial Latin rectangle L. Then, D[G[P]] ≤D[PSEI(L)]. The two-line graph refinement is particularly more effective than the strong entry invariants when dealing with very sparse or very dense partial Latin rectangles, since in those cases the strong entry invariants yield a very coarse system of partitions (or just the singleton system of partitions in the case of a Latin rectangle). Experimental evidence, obtained from running the algorithm on thousands of randomly generated partial Latin rectangles, shows that the two-line graph refinement yields systems of partitions that are close to optimal, and, in fact, optimal in most cases. This improves the current computational complexity of finding autotopism groups of random partial Latin rectangles. 57 References [1] R. Artzy,A note on the automorphisms of special loops, Riveon Lematematika, 8 (1954), p. 81. In Hebrew. [2] L. Babai,Graph isomorphism in quasipolynomial time, (2016). arXiv:1512.03547. [3] L. Babai, W. M. Kantor, and E. M. Luks,Computational complexity and the classification of finite simple groups, in Proc. 24th IEEE FOCS, 1983, p. 162171. [4] R. A. Bailey,Latin squares with highly transitive automorphism groups,J. Aust. Math. Soc., 33 (1982), pp. 18–22. [5] R. M. Falc´ on,The set of autotopisms of partial Latin squares, Discrete Math., 313 (2013), pp. 1150–1161. [6] R. M. Falc´ on, D. Kotlar, and R. J. Stones,Computing autotopism groups of partial latin rectangles: a pilot study, (2018). Submitted. [7] R. M. Falc´ on and R. J. Stones,Classifying partial Latin rectangles, Electron. Notes Discrete Math., 49 (2015), pp. 765–771. [8] ,Partial Latin rectangle graphs and autoparatopism groups of partial Latin rectangles with trivial autotopism groups, Discrete Math., 340 (2017), pp. 1242– 1260. [9] ,Enumerating partial latin rectangles, (2018). Submitted. [10] A. D. Keedwell,Critical sets and critical partial latin squares, in Proc. Third China-USA International Conf. on Graph Theory, Combinatorics, Algorithms and Applications, World Sci. Publishing, NJ, 1994. [11] D. Kotlar,Computing the autotopy group of a Latin square by cycle structure, Discrete Math., 331 (2014), pp. 74–82. [12] B. D. McKay, A. Meynert, and W. Myrvold,Small Latin squares, quasigroups, and loops, J. Combin. Des., 15 (2007), pp. 98–119. [13] E. Sch¨ onhardt,¨ Uber lateinische Quadrate und Unionen, J. Reine Angew. Math., 163 (1930), pp. 183–229. [14] D. S. Stones,Symmetries of partial Latin squares, European J. Combin., 34 (2013), pp. 1092–1107. 58