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