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.
The search for pairs of orthogonal diagonal Latin squares (ODLS) is a hard combinatorial
problem [
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@home1 and SAT@home2 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 [
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 [
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.
The research was partially supported by Russian Foundation for Basic Research (grants 16-0700155-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. [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 2 017. Moscow: Center of Information Technologies in Mathematical Modeling of RAS, 2017. pp. 167–170.