Speaker
Eduard Vatutin
(Southwest State University)
Description
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. According to some estimations, only 1 DLS of order 10 out of 32 millions has an orthogonal mate. Authors of the volunteer computing pro-ject Gerasim@home and SAT@home maintain the collection of pairs of ODLS of order 10. It contains more than 580 000 canonical forms (isotopy classes) of DLS of order 10 as for June 2018.
DLSs from the collection can be classified by the number of their orthogo-nal mates. According to this classification, about 550 000 of DLSs are bachelor – i.e. each of them has exactly one orthogonal mate. About 7 500 of DLSs are line-2 – i.e. that each of them has exactly two orthogonal mates. There are also 63 line-3, 283 fours, 2 fives, 9 sixes, 1 sevens, 7 eights and 1 ten (see Fig. 1). This classification can be expanded.
Table 1 contains examples of DLSs of order 10 that are part of structures depicted in Figure 1. 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 some plane; comprehensive search for general symmetric DLSs; random search for partially symmetric DLSs.
The found combinatorial structures are new and were not published before. Due to their simplicity they allow a trivial classification based on a vector of de-grees of vertices which is sorted in ascending order. In fact, in this case a degree of a vertex is the number of ODLS for the chosen DLS.
The research was partially supported by Russian Foundation for Basic Re-search (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 for their participation.
Bibliography
1. Colbourn C.J., Dinitz J.H. Handbook of Combinatorial Designs. Second Edi-tion. Chapman&Hall, 2006. 984 p.
Primary authors
Eduard Vatutin
(Southwest State University)
Maxim Manzyuk
(BOINC.ru, Moscow, Russia)
Ms
Natalia Nikitina
(Institute of Applied Mathematical Research, Karelian Research Center RAS)
Mr
Oleg Zaikin
(Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences)
Stepan Kochemazov
(Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk, Russia)
Vitaly Titov
(Southwest State University, Kursk, Russia)
