Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 ORTHOGONALITY-BASED CLASSIFICATION OF DIAGONAL LATIN SQUARES OF ORDER 10 Eduard Vatutin 1, a, Vitaly Titov 1, Oleg Zaikin 2, Stepan Kochemazov 2, Maxim Manzuk 3, Natalia Nikitina 4 1 Southwest State University, Russia, Kursk 2 Matrosov Institute for System Dynamics and Control Theory SB RAS, Russia, Irkutsk 3 BOINC.ru, Russia, Moscow 4 Institute of Applied Mathematical Research KRC RAS, Russia, Petrozavodsk E-mail: a evatutin@rambler.ru The article describes combinatorial structures based on diagonal Latin squares (DLS) of order 10 and the orthogonality condition between pairs of such squares. These structures are novel and interesting in the context of the well-known open problem aimed at finding a triple of mutually orthogonal DLSs of order 10. The structures were found in the BOINC-based volunteer computing projects SAT@home and Gerasim@home. Keywords: combinatorics, diagonal Latin square, orthogonal mate, volunteer computing, BOINC. © 2018 Eduard Vatutin, Vitaly Titov, Oleg Zaikin, Stepan Kochemazov, Maxim Manzuk, Natalia Nikitina 282 Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 Introduction The search for pairs of orthogonal diagonal Latin squares (ODLS) is a hard combinatorial problem [1]. According to the Euler-Parker approach, a set of diagonal transversals is constructed for a given DLS of order N. If a subset of N non-overlapping transversals is found, then an orthogonal mate for the DLS can be easily constructed. Applying volunteer computing to find canonical forms of diagonal Latin squares of order 10 with orthogonal mates According to some estimations, only 1 DLS of order 10 out of 32 millions has an orthogonal mate. Authors of the volunteer computing projects Gerasim@home 1 and SAT@home 2 maintain a collection of pairs of ODLS of order 10. As of September 2018, the collection contains more than 1 300 000 different canonical forms (CFs) or isotopy classes of DLS of order 10 [2]. DLSs from the collection can be naturally classified by the number of their orthogonal mates. This classification can be expanded [3]. Figure 1 and Table 1 contain examples of DLSs of order 10 that are part of corresponding combinatorial structures. These DLSs were constructed during several computational experiments: random search for DLSs with consequent attempt to construct their orthogonal mates; comprehensive search for DLSs that are symmetric according to one plane (for example, horizontal); comprehensive search for generalized symmetric DLSs for some set of generalized symmetries; random search for partially generalized symmetric DLSs. The found combinatorial structures (graphs from DLSs on the orthogonality binary relation set) are novel and were not published before. Due to their simplicity they allow a trivial classification based on a vector of degrees of vertices which is sorted in ascending order [4]. In fact, in this case a degree of a vertex is the number of ODLS for the chosen DLS. 1 http://gerasim.boinc.ru 2 http://sat.isa.ru 283 Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 a) b) c) C e) C d) A A B A B C A B A B D f) g) F C D D E E h) A B A B E i) D G H C D E C F G F A B E A B F j) k) C B B D I H G l) A C F C m) A B A F A D D D C F C D n) B E E G A B C D p) D q) o) B G B H A B C D E A E C H C I F A F r) C D J s) D A B E F E K B E D L A F t) u) v) C B G A B G C C H B C w) I J A F A D G H K D I D G A B E E J F C E F E D F y) G H B E A D x) C E F B A D C G H Figure 1. Combinatorial structures based on the orthogonality of DLSs of order 10: a – square with no mate (bachelor); b – line-2 or once; c – line-3; d – triple; e – four; f – five; g – six; h – seven; i – eight; j – rhombus-3; k – rhombus-4; l – loop-4; m – fish; n – line-4; o – line-5; p – flyer; q – daedalus-10; r – cross; s – tree; t – daedalus-8; u – venus; v – rhombus-5; w – ten; x – robot; y – stingray 284 Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 Table 1. Examples of DLSs from various combinatorial structures. For each structure only one DLS is presented, all other DLSs can be easily constructed too. DLS elements are written row by row Number of vertexes and Combinatorial arcs, ascending sorted structure Values of DLS elements vector of degrees of type vertexes 012345678912045398673561874092947832160527 1, 0 a 309851466859247310469701325870461985238315 [1] 6029745982760431 012345678912043659782015634897345798162057 2, 1 b 498021636981247305837601925496307285417568 [1, 1] 1904324892573016 012345678912043659782035814697469718203597 3, 2 c 865431203478091256694172850378506394125319 [1, 1, 2] 2708648562907341 012345678912370985464096371825968451307259 4, 3 d 687024313459280617870163529423759641087512 [1, 1, 1, 3] 8493606840127953 012345678912043659782351098467859672304137 5, 4 e 491805264068271395748063915269125478039675 [1, 1, 1, 1, 4] 8142305837902614 012345678912048795639317680425379504821625 6, 5 f 869371047948261350863150497264703258914059 [1, 1, 1, 1, 1, 5] 7126385862193047 012345678912340956782340819567987654321087 7, 6 g 659043216491278053350872194650176328947659 [1, 1, 1, 1, 1, 1, 6] 1804324982367105 012345678912043795683940715826903184765258 8, 7 h 976201437568092431647513829026195843078352 [1, 1, 1, 1, 1, 1, 1, 7] 9610744786203915 012345678912305496784968271305687490521373 9, 8 i 591804629487632150359172804687460935215012 [1, 1, 1, 1, 1, 1, 1, 1, 8] 3678942605814937 012345678912370489656059312478890462153778 5, 6 j 619352043675284091249086715345861793209748 [2, 2, 2, 3, 3] 5036125312790846 012345678912043659782315904867346978015278 6, 8 k 915420365680179324974263851049378216058576 [2, 2, 2, 2, 4, 4] 0932416058217493 012345678932960178457830695124934720865126 4, 4 l 859304171978543206456278109384013695725719 [2, 2, 2, 2] 8243606054172938 012345678912043679588796524031694518237045 6, 6 m 107398262057813694937160854238692704155438 [1, 1, 2, 2, 2, 4] 0912677682945103 012345678912386709457964083512461970285338 4, 3 n 025194678597341206245086739190862351745741 [1, 1, 2, 2] 9286306375194028 012345678912043659782349180567876590432194 5, 4 o 826371505830279614769854103235170928464076 [1, 1, 2, 2, 2] 8132956951728403 285 Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 012345678912043659782349180567876590432194 8, 10 p 826371505830279614769854103235170928464076 [1, 1, 2, 2, 2, 4, 4, 4] 8132956951728403 012345678912045379689762385140751869203439 12, 14 q 867412052459810376483026951786759034216391 [1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 0748525047128693 4, 10] 012345678912047986534659827310654837109290 6, 5 r 126835475796234801387016942529675401388431 [1, 1, 1, 1, 2, 4] 9052767385012964 012345678912046798538475910632706123859498 7, 6 s 365214073792084165654789321026103459785389 [1, 1, 1, 1, 2, 3, 3] 7620414958107326 012345678912067934583864025197291738460540 10, 12 t 528379165791240863758061932463791085429648 [1, 1, 1, 1, 2, 2, 2, 2, 4, 8] 5712308435962071 012345678912047896357385601492591683720436 8, 8 u 529180479078542316459027316884671905236841 [1, 1, 2, 2, 2, 2, 2, 4] 3259702739064851 012345678912307986546875903241531402789695 7, 10 v 876143204692831075845637910229481605377069 [2, 2, 2, 2, 2, 5, 5] 2854133701542968 012345678912048795637542918306278103569486 11, 10 w 395074219458261037509764381263157829403860 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1942754976320158 10] 012345678912047859632381604597453916207874 8, 8 x 605198329675038214509834762169428731508716 [1, 1, 1, 1, 2, 2, 4, 4] 2903453857921406 012345678912046789355836720194378594261029 5, 5 y 108653476341097528459728106376583194029462 [1, 2, 2, 2, 3] 5038718079134256 Conclusion As of September 2018, the collection of different combinatorial structures with more than 1 DLS per structure includes: 1 250 250 different CFs owned by the line-2 structure, 55 293 CFs by line-3, 96 CFs by line-4, 51 CFs by line-5, 1 944 CFs by loop-4, 312 CFs by triples, 1 708 CFs by fours, 12 CFs by fives, 53 CFs by sixes, 8 CFs by seven, 58 CFs by eights, 10 CFs by rhombus-3, 104 CFs by rhombus-4, 16 CFs by fishes, 4 CFs by tree, 24 CFs by crosses, 12 CFs by daudalus-10, 8 CFs by flyer, 5 CFs by venus, 6 CFs by daudalus-8, 5 CFs by rhombus-5, 6 CFs by ten, 10 CFs by robot and 5 CFs by stingray. The structures seven, tree, daedalus-8, daedalus-10, flyer, venus, rhombus-5, ten, robot and stingray are found in a single copy only. In the future, we are planning to find novel combinatorial structures using different partial symmetries neighborhoods. A triple of MODLS of order 10 has not been found so far as a part of any mentioned structures. Acknowledgement The research was partially supported by Russian Foundation for Basic Research (grants 16-07- 00155-a, 17-07-00317-a, 18-07-00628-a, 18-37-00094-mol-a) and by Council for Grants of the President of the Russian Federation (stipend SP-1829.2016.5). Authors thank citerra [Russia Team] from the internet portal BOINC.ru for his help in the development and implementation of some algorithms. Also, authors thank all the volunteers of SAT@home and Gerasim@home projects for their participation. 286 Proceedings of the VIII International Conference "Distributed Computing and Grid-technologies in Science and Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018 References [1] Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs. Second Edition. Chapman&Hall, 2006. 984 p. [2] Zaikin O.S., Vatutin E.I., Zhuravlev A.D., Manzyuk M.O. Applying High-Performance Computing to Searching for Triples of Partially Orthogonal Latin Squares of Order 10 (in Russian) // Bulletin of the South Ural State University. Series: Computational Mathematics and Software Engineering. 2016. Vol. 5, No. 3. pp. 54–68. DOI: 10.14529/cmse160304. [3] Vatutin E.I., Titov V.S., Zaikin O.S., Kochemazov S.E., Manzuk M.O. An analysis of the combinatorial structures from the diagonal Latin squares of order 10 on the binary relation of orthogonality (in Russian) // Information technologies and mathematical modeling of a systems 2017. Moscow: Center of Information Technologies in Mathematical Modeling of RAS, 2017. pp. 167–170. [4] Vatutin E.I., Titov V.S. Strategies for verifying correctness of methods for graph isomorphism checking using grid-systems (in Russian) // Proceeding of Southwest State University. 2014. № 1 (52). pp. 26–30. 287