2-ТРАНСВЕРСАЛИ В ПАРАХ ОРТОГОНАЛЬНЫХ ДИАГОНАЛЬНЫХ ЛАТИНСКИХ КВАДРАТОВ.
УДК 681.3 Э.И. Ватутин
evatutin@rambler.comЮго-Западный государственный университет, Курск
В работе предложено понятие 2-трансверсалей (диагональных и общего вида) в парах ОЛК/ОДЛК, показана их связь с задачей построения троек взаимно ортогональных ЛК/ДЛК и приведено краткое описание их свойств.
Латинские квадраты (ЛК) и диагональные латинские квадраты (ДЛК) представляют собой достаточно известные типы комбинаторных объектов, исследованию которых посвящено достаточно большое количество научных публикаций. Одной из наиболее известных открытых математических проблем является попытка построения тройки взаимно ортогональных ЛК/ДЛК (ВОЛК/ВОДЛК) порядка 10 N = либо доказательство ее несуществования.
Для построения ортогональных соквадратов (ОЛК/ОДЛК) к заданному квадрату наиболее эффективным является метод Эйлера-Паркера, базирующийся на построении множества трансверсалей, и последующем поиске покрытия из N попарно не пересекающихся трансверсалей (диагональных трансверсалей при поиске ОДЛК и трансверсалей общего вида при поиске ОЛК).
Введем в рассмотрение понятие 2-трансверсалей, определенных в парах ОЛК/ОДЛК. Так 2-трансверсалью в паре ОЛК/ОДЛК A и B будем называть такую трансверсаль, которая одновременно является трансверсалью как в квадрате A, так и в квадрате B.
Аналогично, диагональной 2-трансверсалью в паре ОДЛК будем называть такую диагональную трансверсаль, которая одновременно является диагональной трансверсалью в обоих ДЛК пары.
Несложно показать, что необходимым и достаточным условием существования третьего квадрата C, ортогонального обоим квадратам A и B пары, является наличие N попарно не пересекающихся 2-трансверсалей. Следовательно, при поиске тройки ВОЛК/ВОДЛК имеет смысл сконцентрироваться на целенаправленном построении пар ОЛК/ОДЛК с большим числом 2-трансверсалей, для чего необходимо исследование их свойств. Пример пары ОДЛК порядка 9 и диагональной 2-трансверсали приведен на рисунке.
00 11 22 33 44 55 66 77 88
82 53 36 08 27 60 41 15 74
46 04 17 20 65 78 52 83 31
35 87 58 61 13 24 70 06 42
28 45 64 12 76 81 37 50 03
14 68 73 47 80 32 05 21 56
57 26 01 75 38 43 84 62 10
71 30 85 54 02 16 23 48 67
63 72 40 86 51 07 18 34 25
Рис. Пример пары ОДЛК порядка 9 и диагональной 2-трансверсали [1 0 3 2 4 6 5 8 7] (выделена жирным).
Также указанная пара ОДЛК имеет еще 3 диагональных 2-трансверсали: [2 6 7 0 4 1 8 3 5], [3 5 1 8 4 7 0 2 6] и [5 3 8 1 4 0 7 6 2]
С использованием построенных ранее коллекций ОДЛК можно посчитать следующие числовые ряды для 2-трансверсалей:
• минимальное число 2-трансверсалей в парах ОДЛК – 1, 0, 0, 4, 10, 0, 2, 2,2, 2, 2, 2 (диагонали ДЛК по определению являются трансверсалями, поэтому для всех порядков N, для которых существуют ОДЛК, ( )2a N ³ );
• максимальное число 2-трансверсалей в парах ОДЛК – 1, 0, 0, 4, 10, 0, 28,96, 648, ()1028a³, ( )11
1782a³, ()12 108a³;
• мощность спектра числа 2-трансверсалей в парах ОДЛК – 1, 0, 0, 1, 1, 0, 3,7, 66, ()10 17a³, ( )11 35a³, () 12 42a³; и для диагональных 2-трансверсалей:
• минимальное число диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 (вероятно далее с ростом размерности N ряд будет состоять из нулевых значений);
• максимальное число диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 0, 0, 0, 14, 32, 140, ()10 8a³ , ( )11 320a³, () 12 38a³, () 13 992a³;
• мощность спектра числа диагональных 2-трансверсалей в парах ОДЛК – 1, 0, 0, 1, 1, 0, 3, 4, 53, () 106a³ , ( ) 11 37a³, ()12 11a³, () 13 14a³.
Все посчитанные числовые ряды не представлены в OEIS и планируются к добавлению в состав энциклопедии. Для порядка 11 N = ДЛК в составе рекордных пар ОДЛК являются либо циклическими, либо DSODLS/ESODLS (либо одновременно); для порядка 12 N =– по-видимому, диагонализированными составными квадратами вида 34´ с максимально возможным для данной размерности числом трансверсалей, равным 198 144 (см. числовые ряды A287644 и A344105 в OEIS).
Для порядка 10 N =рекордным числом общих 2-трансверсалей (как диагональных, так и общего вида) обладают ДЛК, являющиеся SODLS/ESODLS с относительно небольшим числом трансверсалей (124/932 и 128/932 соответственно при известных максимальных значениях 890/5504), что делает актуальной задачу бестрансверсального поиска ESODLS с использованием схем отображения ячеек CMS [1].
В перспективе при необходимости введенное определение 2-трансверсалей может быть расширено на 3-трансверсали в тройках ВОЛК/ВОДЛК, 4-трансверсали в четверках ВОЛК/ВОДЛК и т.д.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. Vatutin E.I., Zaikin O.S., Manzuk M.O., Nikitina N.N. Searching for Orthogonal Latin Squares via Cells Mapping and BOINC-Based Cube-And-Conquer // Communications in Computer and Information Science. 2021. Vol. 1510. pp. 498–512. DOI: 10.1007/978-3-030-92864-3_38.
https://boinc.ru
