ПРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ

Том 56

2020

Вып. 1

УДК 621.391.1 : 519.1

Ю. Гуань, М. Ши , Д.С. Кротов

СИСТЕМЫ ТРОЕК ШТЕЙНЕРА ПОРЯДКА 21

С ТРАНСВЕРСАЛЬНЫМ ПОДДИЗАЙНОМ TD(3, 6)¹

Система троек Штейнера (STS) содержит трансверсальный поддизайн

TD(3, w), если в множестве ее точек имеются три попарно непересекающихся

подмножества A, B, C размера w, такие что w² блоков этой STS пресекаются

с каждым из множеств A, B, C (эти w² блоков и образуют TD(3, w)). Доказыва-

ются некоторые структурные свойства систем троек Штейнера порядка 3w + 3,

содержащих один или несколько трансверсальных поддизайнов TD(3, w). Пол-

ным перебором установлено, что имеется 2004720 классов изоморфизма систем

STS(21), содержащих поддизайн TD(3, 6) (или, что эквивалентно, латинский

квадрат порядка 6 × 6).

Ключевые слова: система троек Штейнера, поддизайн, трансверсальный ди-

зайн, латинский квадрат.

DOI: 10.31857/S0555292320010039

§ 1. Введение

Система троек Штейнера порядка v, или STS(v), - это пара (S, B), состоящая

из конечного множества S (называемого носителем, или множеством точек системы

STS) мощности v и набора B трехэлементных подмножеств множества S, называе-

мых блоками, таких что любые два различных элемента множества S встречаются

ровно в одном блоке. Трансверсальным дизайном TD(k, w) (в настоящей статье рас-

сматривается только случай k = 3) называется тройка (S, G, B), состоящая из мно-

жества точек S мощности kw, разбиения G множества S на k подмножеств (групп)

мощности w и набора B подмножеств размера k множества S (блоков), таких что

каждый блок пересекает каждую группу ровно в одной точке, а любые две точки

из разных групп содержатся ровно в одном блоке. Поскольку как носитель, так и

(в случае TD) группы однозначно определяются множеством блоков, удобно отож-

дествлять систему STS или дизайн TD с ее (его) множеством блоков. При таком

соглашении корректно говорить, что STS B может включать в себя некоторую STS

или некоторый TD C как подмножество, и в этом случае C называется подсистемой

STS или поддизайном TD системы B соответственно. Две системы STS или два ди-

зайна TD называются изоморфными, если существует биекция между их носителя-

ми (изоморфизм), переводящая блоки одной системы в блоки другой. Изоморфизм

системы B на себя называется автоморфизмом; множество всех автоморфизмов B

обозначается через Aut(B).

¹ Работа выполнена при финансовой поддержке Национального фонда естественных наук Китая

(номер проекта 61672036), Фонда поддержки выдающихся молодых ученых Фонда естественных

наук провинции Аньхой (номер проекта 1808085J20), Академического фонда для выдающихся та-

лантов в университетах (грант gxbjZD03), и Программы фундаментальных научных исследований

СО РАН № I.5.1 (номер проекта 0314-2019-0016).

Трансверсальные дизайны TD(3, w) эквивалентны латинским квадратам размера

w×w, и известно, что они существуют для любого натурального w. Классы изомор-

физма дизайнов TD(3, w) соответствуют так называемым главным классам латин-

ских квадратов; их число известно для значений w вплоть до 11 (см. [1]). Системы

троек Штейнера STS(v) существуют тогда и только тогда, когда v ≡ 1, 3 mod 6

(см., например, [2]), причем необходимое условие вытекает из простых соображений

мощности.

Число классов изоморфизма систем троек Штейнера известно [3] для порядков

вплоть до 19. Классификация STS больших порядков возможна лишь при дополни-

тельных ограничениях на структуру STS. Среди таких ограничений наиболее попу-

лярными являются ограничения на автоморфизмы (см., например, [4-10]), на макси-

мальный ранг системы [11, 12], и требование, чтобы система содержала подсистему

с некоторыми заданными параметрами.

В работе [13] было установлено, что всего имеется 284457 систем STS(19) с под-

системой STS(9). В [14] получена классификация систем STS(19) с подсистемами

STS(7) и систем STS(21), содержащих три подсистемы STS(7) с непересекающими-

ся носителями (последний класс совпадает с классом STS(21), имеющих 3-ранг не

выше 19). Недавно в [15] было найдено число всех STS(21) с подсистемой STS(9)

(а также систем STS(27) с подсистемой STS(13)). Число 12661527336 (соответствен-

но, 1356574942538935943268083236) классов изоморфизма таких систем слишком ве-

лико, чтобы было возможно какое-либо их эффективное перечисление; в частности,

невозможно вычислительными методами проверить какое бы то ни было требуемое

свойство этих классов.

В настоящей статье проведена классификация систем STS(21) с поддизайнами

TD(3, 6), или, другими словами, систем STS(21), содержащих латинский квадрат

порядка 6 × 6. Установлено, что всего существует 2004720 классов изоморфизма си-

стем троек Штейнера порядка 21 с трансверсальными поддизайнами на трех груп-

пах размера 6, в том числе 599 систем ровно с тремя поддизайнами TD(3, 6) и 12

систем ровно с семью поддизайнами TD(3, 6). Рассматриваемый класс содержит 393

неизоморфные разрешимые STS; ни одна из них не является дважды разрешимой.

В §2 доказываются некоторые факты о системах троек Штейнера порядка 3w+3,

имеющих трансверсальный поддизайн на трех группах размера w, причем в основ-

ном мы сконцентрируемся на случае w = 6. В § 3 представлены результаты компью-

терной классификации систем STS(21) с поддизайном TD(3, 6), в том числе в таб-

лице приведено количество найденных классов изоморфизма, классифицированных

по числу поддизайнов TD(3, 6), подсистем STS(9) и числу автоморфизмов. В § 4 ре-

зультаты этих вычислений подтверждены с помощью подсчета мощностей двумя

способами. В § 5 обсуждается разрешимость найденных STS и показано, что систе-

мы STS(21) с поддизайном TD(3, 6) и ровно одной подсистемой STS(9) не могут

быть разрешимыми.

§ 2. Системы троек Штейнера с трансверсальными поддизайнами

Начнем с некоторых теоретических рассуждений. Если система STS(v) имеет

поддизайн TD(3, w), то v = 3w + u, где u ≡ 1 или 3, когда w четно, и u ≡ 0 или 4,

когда w нечетно. Случай u = 0 соответствует STS(3w) типа Уилсона [16]; нетрудно

видеть, что такая система является объединением трех STS(w) со взаимно непе-

ресекающимися носителями и трансверсального дизайна TD(3, w). Случай u = 1

соответствует STS(3w + 1) типа Уилсона [16]; снова нетрудно видеть, что такая си-

стема является объединением трех STS(w+1), носители которых имеют одну общую

точку, и трансверсального дизайна TD(3, w).

Следующий случай - это u = 3. Введем связанное с ним понятие. Подмножество C

системы троек Штейнера B называется почти подсистемой STS, если C = C^′ \ {T }

для некоторой STS C^′ и некоторой тройки T из C^′ (заметим, что T не обязательно

должна быть блоком из B); эта тройка называется недостающей для почти подси-

стемы STS C.

Лемма 1. Пусть (A ∪ B ∪ C ∪ D,B) - это STS(3w + 3) с поддизайном TD

(A∪B∪C, {A, B, C}, T ), где |A| = |B| = |C| = w и |D| = 3. Тогда B = T ∪B_A∪B_B ∪B_C ,

где системы B_A, B_B и B_C имеют носители A ∪ D, B ∪ D и C ∪ D соответственно,

причем две из них являются почти подсистемами STS с недостающей тройкой D,

а третья - подсистемой STS (в частности, w + 3 ≡ 1, 3 mod 6).

Доказательство. Предположим вначале, что D - один из блоков системы B.

В этом случае нетрудно видеть, что B имеет подсистему STS(w+3) с носителем A∪D.

Выберем ее в качестве B_A. Аналогично, B имеет подсистему STS(w + 3) с носителем

B ∪ D. Удаляя блок D, получаем почти подсистему STS B_B. Аналогично находим

почти подсистему STS B_C.

Остается рассмотреть случай D ∈ B. В этом случае разделим B \ T на три под-

множества: B_A состоит из блоков, являющихся подмножествами A ∪ D, B_B - из

блоков, являющихся подмножествами B ∪ D, а B_C - из подмножеств C ∪ D (заме-

тим, что любой другой блок содержит точки по крайней мере двух множеств из

A, B, C, и поэтому обязательно принадлежит T ). Блоки из B_A, B_B и B_C покрывают

|A| · (|A| - 1) +

|B| · (|B| - 1) +

|C| · (|C| - 1) + 3|A| + 3|B| + 3|C| + 3 =

w² +

w+3

пар точек, причем блоки из B_A (аналогично, из B_B или из B_C ) покрывают не менее

|A| · (|A| - 1) + 3|A| =

w² +

но не более

|A| · (|A| - 1) + 3|A| + 3 =

w² +

w+3

из них. Поскольку число пар, покрываемых системой B_A, должно делиться на 3, оно

равно

w² +

w или

w² +

w + 3, если w ≡ 0,1 mod 3,

и равно

w² +

w + 2, если w ≡ 2 mod 3.

(

)

Последний случай невозможен, поскольку 3

w² +⁵w+2

w² +¹⁵w + 3. Сле-

довательно, одна из систем B_A, B_B и B_C , скажем, B_A, имеет

(

)

(w + 3)(w + 2)

w² +

w+3

блоков, а две другие - на один меньше. Это означает, что (A ∪ D, B_A) является

STS(w + 3), а (A ∪ D, B_B ∪ {D}) и (A ∪ D, B_B ∪ {D}) - также STS(w + 3), что и

доказывает утверждение. ▴

Итак, мы видим, что если STS(3w+3) имеет поддизайн TD(3, w), то она разбива-

ется на этот поддизайн TD(3, w), одну подсистему STS(w+3) и две почти подсистемы

STS(w + 3). В общем случае может существовать более чем один такой поддизайн

TD(3, w), и поэтому более чем одно такое разбиение. Таким образом, важно пони-

мать, как такие подсистемы могут пересекаться. Следующая лемма о пересечении

двух почти подсистем STS обобщает хорошо известный и очевидный факт, что пе-

ресечение двух подсистем STS всегда является подсистемой STS.

Лемма 2. Пусть STS B имеет две почти подсистемы STS B^′ и B^′′ с носите-

лями S^′ и S^′′ соответственно. Тогда

• либо |S^′ ∩ S^′′| = 2, а пересечение B^′ ∩ B^′′ пусто,

• либо |S^′ ∩ S^′′| ≡ 1 или 3 mod 6, а пересечение B^′ ∩ B^′′ можно дополнить до

STS(|S^′ ∩ S^′′|) путем добавления 0, 1 или 2 блоков.

Доказательство. Обозначим D := S^′∩S^′′ и D := B^′∩B^′′. Пусть B^′∪{a^′,b^′,c^′} и

B^′∪{a^′′, b^′′, c^′′} являются STS. Таким образом, любая пара точек из S^′, кроме {a^′, b^′},

{a^′, c^′} и {b^′, c^′}, содержится в одном блоке системы B^′. Аналогично для S^′′ и B^′′.

Следовательно,

(∗) Любая пара точек из D, отличная от {a^′, b^′}, {a^′, c^′}, {b^′, c^′}, {a^′′, b^′′}, {a^′′, c^′′}

и {b^′′, c^′′}, содержится в одном блоке системы D.

Кроме того,

(∗∗) Для любой точки t из D число ℓ(t) пар точек из D, содержащих t и отличных

от {a^′, b^′}, {a^′, c^′}, {b^′, c^′}, {a^′′, b^′′}, {a^′′, c^′′} и {b^′′, c^′′}, четно.

Действительно, это число вдвое больше числа блоков D, содержащих t.

Непосредственной проверкой всех случаев пересечений множеств D, {a^′, b^′, c^′} и

{a^′′, b^′′, c^′′} нетрудно убедиться, что если оба условия (∗) и (∗∗) выполнены, то имеет

место одно из следующих утверждений.

(i) Множество D содержит не более одной из точек a^′, b^′, c^′ и не более одной из

a^′′, b^′′, c^′′. В этом случае D является STS.

(ii) Множество D состоит из двух точек из a^′, b^′, c^′ или из двух из a^′′, b^′′, c^′′. Таким

образом, |D| = 2.

(iii) Множество D содержит точки a^′, b^′, c^′ и не более одной из a^′′, b^′′, c^′′, или же D

содержит a^′, b^′, c^′ и две или три точки из a^′′, b^′′, c^′′, которые совпадают с неко-

торыми из a^′, b^′, c^′. Либо, аналогично, D содержит a^′′, b^′′, c^′′ и не более одной из

a^′, b^′, c^′, или же D содержит a^′′, b^′′, c^′′ и две или три точки из a^′, b^′, c^′, которые

совпадают с некоторыми из a^′′, b^′′, c^′′. В этом случае D можно дополнить до

STS добавлением тройки {a^′, b^′, c^′} или {a^′′, b^′′, c^′′} соответственно.

(iv) Множество D включает оба множества {a^′, b^′, c^′} и {a^′′, b^′′, c^′′}, причем эти

множества пересекаются не более чем по одной точке. В этом случае D можно

дополнить до STS добавлением двух троек {a^′, b^′, c^′} и {a^′′, b^′′, c^′′}.

(v) |D| = 4, причем две точки e^′, f^′ из D входят в {a^′, b^′, c^′}, а две другие e^′′, f^′′

входят в {a^′′, b^′′, c^′′}. Нетрудно видеть, что четыре пары {e^′, e^′′}, {e^′, f^′′}, {f^′, e^′′}

и {f^′, f^′′} не могут правильным образом покрываться блоками из D.

Мы убедились, что в каждом непротиворечивом случае утверждение леммы выпол-

нено. ▴

Замечание. В отличие от случая подсистем STS, носители двух почти подсистем

STS могут пресекаться ровно по двум точкам. Такой пример нетрудно построить,

используя известные теоремы о вложении: любой набор трехэлементных множеств,

таких что никакая пара точек не встречается более чем в одном множестве, все-

гда можно вложить как подмножество в некоторую систему троек Штейнера, носи-

тель которой, вообще говоря, может быть больше носителя исходного набора тро-

ек [17,18].

Следствие. (i) Различные носители двух почти подсистем STS(9) одной и

той же STS пересекаются не более чем по трем точкам.

(ii) Различные носители двух почти подсистем STS(9) одной и той же STS(21)

пересекаются по трем точкам. Эти три точки образуют либо блок каждой из

этих почти подсистем STS(9), либо недостающую тройку одной или обеих из

этих почти подсистем STS(9).

Доказательство. Для доказательства утверждения (i) согласно лемме 2

остается проверить, что носители не могут пересекаться по семи точкам. Действи-

тельно, в такой ситуации по лемме 2 найдутся STS(7) и STS(9), имеющие по край-

ней мере пять общих блоков. Непосредственной проверкой легко убедиться, что это

невозможно.

(ii) Остается проверить, что носители, скажем, S^′ и S^′′ этих подсистем, скажем,

B^′ и B^′′, не могут пересекаться по двум, одной или нулю точек. Предположим вна-

чале, что |S^′ ∩ S^′′| = 2. Блок, содержащий S^′ ∩ S^′′, не принадлежит по крайней мере

одной из подсистем B^′ и B^′′. Без ограничения общности будем считать, что он не

принадлежит B^′′, тогда пара S^′ ∩S^′′ лежит в недостающей тройке почти подсистемы

STS B^′′. Следовательно, шесть точек a₁, . . . , a₆ из S^′′ \ S^′ не принадлежат недоста-

ющей тройке. Возьмем также точку b из S^′ \ S^′′, не принадлежащую недостающей

тройке подсистемы B^′, и рассмотрим блок, содержащий b и a_i, i ∈ {1, 2, 3, 4, 5, 6}.

Этот блок не входит ни в B^′, ни в B^′′, и поэтому он пересекается как с S^′, так и

с S^′′ только по одной точке. Таким образом, третья точка c_i этого блока не лежит

в S′ ∪S^′′. Но вне S^′∪S^′′ есть всего пять точек, что немедленно приводит к противо-

речию с определением STS. Аналогичные противоречия можно найти и в случаях

|S^′ ∩ S^′′| = 1 и |S^′ ∩ S^′′| = 0. ▴

Теперь сосредоточимся на порядке 21. Пусть имеется STS(21) (S, B). Разбиение

множества S на четыре множества A, B, C, D размера 6, 6, 6 и 3 соответственно

называется цветком со стеблем D и лепестками A, B, C, если B имеет подсистему

STS(9) и две почти подсистемы STS(9) с носителями A ∪ D, B ∪ D и C ∪ D, где

недостающей тройкой каждой из этих почти подсистем является D (вне зависимости

от того, принадлежит оно B или нет). Из леммы 1 легко выводится следующая

Лемма 3. Система STS(21) содержит цветок {A,B,C,D} со стеблем D то-

гда и только тогда, когда она имеет поддизайн TD(3, 6) с группами A, B и C.

Если имеется только один цветок {A, B, C, D} (и только один поддизайн TD(3, 6)),

то возможны два подслучая в зависимости от того, является ли стебель D блоком

или нет. В первом подслучае система STS(21) имеет три подсистемы STS(9) с носи-

телями A ∪ D, B ∪ D и C ∪ D. Во втором подслучае система STS(21) имеет только

одну подсистему STS(9). Следующая наша цель - охарактеризовать ситуацию, когда

STS(21) имеет более одного поддизайна TD(3, 6).

Лемма 4. Пусть система STS(21) имеет два различных цветка {A,B,C,D}

и {A^′, B^′, C^′, D^′} со стеблями D и D^′. Тогда

(i) D и D^′ не пересекаются;

(ii) D ∪ E = D^′ ∪ E^′ для некоторых E ∈ {A, B, C} и E^′ ∈ {A^′, B^′, C^′};

(iii) Система STS(21) имеет подсистему STS(9) с носителем D ∪ E, где E - мно-

жество из п. (ii).

Доказательство. Рассмотрим точку d из D и предположим без ограничения

общности, что она лежит в D^′ ∪ A^′. Каждая точка из D^′ ∪ A^′ лежит в одном из

множеств D ∪ A, D ∪ B и D ∪ C, и по крайней мере одна точка лежит во всех трех.

Следовательно, множество D^′ ∪ A^′ пересекается с этими тремя множествами в сред-

нем по более чем трем точкам. По следствию оно совпадает с одним из них, скажем,

с D ∪ A; таким образом, утверждение (ii) доказано. Если D и D^′ пересекаются, то

это же можно сказать про D^′ ∪ B^′ и D^′ ∪ C^′, т.е. цветки совпадают. Таким образом,

справедливо (i). Последнее утверждение также несложно, поскольку объединение

двух различных почти подсистем троек Штейнера с одинаковым носителем D ∪ A

с необходимостью является подсистемой троек Штейнера. ▴

A101

A110

A001

A010

Система STS(7) (плоскость Фано) на множестве точек {A001, A010, A011, A100, A101, A110,

A111}. Видно, что каждый из семи носителей (почти) подсистем STS(9), описанных в лем-

ме 5, является объединением трех множеств из A001, . . . , A111, соответствующих прямой на

плоскости Фано

Лемма 5. Пусть система STS(21) B имеет два различных цветка {A,B,C,D}

и {A^′, B^′, C^′, D^′} со стеблями D и D^′. Без ограничения общности предположим,

что D ∪ A = D^′ ∪ A^′. Обозначим

A₁₀₀ := B ∩ B^′,

A₁₀₁ := B ∩ C^′,

A₁₁₀ := C ∩ B^′,

A₁₁₁ := C ∩ C^′,

A₀₀₁ := D,

A₀₁₁ := A \ D^′,

A₀₁₀ := D^′

(см. рисунок, мотивирующий расположение этих формул). Имеют место следу-

ющие утверждения.

(i) Если как D, так и D^′ являются блоками B, то B содержит ровно семь под-

дизайнов TD(3, 6) с цветками

{A₀₀₁, A₀₁₀ ∪ A₀₁₁, A₁₀₀ ∪ A₁₀₁, A₁₁₀ ∪ A₁₁₁},

(1)

{A₀₁₀, A₀₀₁ ∪ A₀₁₁, A₁₀₀ ∪ A₁₁₀, A₁₀₁ ∪ A₁₁₁},

(2)

{A₀₁₁, A₀₀₁ ∪ A₀₁₀, A₁₀₀ ∪ A₁₁₁, A₁₀₁ ∪ A₁₁₀},

(3)

{A₁₀₀, A₀₀₁ ∪ A₁₀₁, A₀₁₀ ∪ A₁₁₀, A₀₁₁ ∪ A₁₁₁},

(4)

{A₁₀₁, A₀₀₁ ∪ A₁₀₀, A₀₁₀ ∪ A₁₁₁, A₀₁₁ ∪ A₁₁₀},

(5)

{A₁₁₀, A₀₀₁ ∪ A₁₁₁, A₀₁₀ ∪ A₁₀₀, A₀₁₁ ∪ A₁₀₁},

(6)

{A₁₁₁, A₀₀₁ ∪ A₁₁₀, A₀₁₀ ∪ A₁₀₁, A₀₁₁ ∪ A₁₀₀},

(7)

а также ровно семь подсистем STS(9).

(ii) Если не более чем одно из множеств D и D^′ является блоком B, то B содер-

жит ровно три поддизайна TD(3, 6) с цветками (1)-(3). Если при этом D

или D^′ является блоком, то B имеет ровно три подсистемы STS(9), а в про-

тивном случае - равно одну.

Доказательство. Отметим вначале, что согласно п. (ii) следствия множества

A₁₀₁, A₁₁₁, A₁₁₀ и A₁₀₀ являются блоками B. Далее, мы утверждаем, что

(∗) Существует почти подсистема троек Штейнера с носителем A₀₁₁∪A₁₀₀∪A₁₁₁

и недостающей тройкой A₀₁₁.

Действительно, рассмотрим блок, содержащий точку a из A₁₀₀ и точку b из A₁₁₁.

Третья точка c этого блока может принадлежать только A₀₁₁ (например, если c ∈

∈ A₀₀₁, то пара {a, c} уже покрыта блоком из почти STS на A₀₀₁ ∪ A₁₀₁ ∪ A₁₀₀;

остальные случаи приводят к аналогичным противоречиям). Таким образом, девять

таких блоков образуют TD(3, 3); дополняя блоками A₁₀₀ и A₁₁₁, получаем почти

подсистему STS(9). Аналогично

(∗∗) Существует почти подсистема троек Штейнера с носителем A₀₁₁ ∪ A₁₀₁ ∪

∪A₁₁₀ и недостающей тройкой A₀₁₁.

Итак, имеется набор из подсистемы STS(9) и шести почти подсистем STS(9) с раз-

личными носителями, соответствующими цветкам (1)-(3). Нетрудно видеть, что

(∗∗∗) Не существует подсистем STS(9) или почти подсистем STS(9) с любыми

другими носителями.

Действительно, если множество B - носитель подсистемы STS(9), то оно пересека-

ется по крайней мере по четырем точкам в общей сложности с двумя из множеств

A₀₀₁, . . ., A₁₁₀; объединение этих двух множеств содержится в носителе некоторой

из семи подсистем STS(9), и по следствию множество B совпадает с этим носителем.

Теперь рассмотрим следующие подслучаи.

Если оба множества D и D^′ входят в B, то также и A₀₁₁ ∈ B, и все эти шесть

почти подсистем троек Штейнера дополняются до подсистемы STS(9), образуя та-

ким образом в общей сложности семь различных цветков. Из леммы 5 и следствия

получаем, что больше цветков нет. Согласно (∗∗∗) имеется только семь подсистем

STS(9).

Если D ∈ B или D^′ ∈ B, то множества (4)-(7) не являются цветками. Рассуждая,

как и выше, получаем, что имеется только три цветка (1)-(3).

Если D ∈ B и D^′ ∈ B, то всегда A₀₁₁ ∈ B (в любой STS(9) дополнение двух непе-

ресекающихся блоков обязательно также является блоком). В этом случае имеются

только три подсистемы STS(9) с носителями A₀₀₁ ∪ A₀₁₁ ∪ A₀₁₀, A₀₀₁ ∪ A₁₀₁ ∪ A₁₀₀ и

A₀₀₁ ∪ A₁₁₁ ∪ A₁₁₀. Подслучай D ∈ B и D^′ ∈ B аналогичен.

Если D ∈ B и D^′ ∈ B, то недостающая тройка любой из данных шести почти

подсистем троек Штейнера не входит в B, и в B имеется только одна подсистема

STS(9) - с носителем A₀₀₁ ∪ A₀₁₁ ∪ A₀₁₀. ▴

В дальнейших рассуждениях мы будем использовать следующие два хорошо из-

вестных несложных факта.

Предложение 1. Если трансверсальный дизайн TD(3,6) (S,{A,B,C},T ) со-

держит поддизайн TD(3, 3) с группами A₀ ⊂ A, B₀ ⊂ B и C₀ ⊂ C, то T содержит

ровно три других поддизайна TD(3, 3): с группами A₀, B₁, C₁, A₁, B₀, C₁ и A₁, B₁, C₀,

где A₁ := A \ A₀, B₁ := B \ B₀ и C₁ := C \ C₀.

Предложение 2. Если D - блок системы STS(9) (S,B), то B содержит ров-

но два блока, не пересекающихся с D. Более того, эти два блока не пересекаются

между собой, а остальные девять блоков образуют поддизайн TD(3, 3).

Лемма 6. Пусть STS(21) (S,B) содержит цветок {A,B,C,D}, а T - транс-

версальный поддизайн B на лепестках A, B, C в качестве групп. Пусть D^′ - трех-

элементное подмножество A. Система B имеет второй поддизайн TD(3, 6) T^′

с носителем S \ D^′ тогда и только тогда, когда она содержит непересекающиеся

блоки B₀, B₁ ⊂ B и непересекающиеся блоки C₀, C₁ ⊂ C, такие что T разбивается

на четыре поддизайна TD(3, 3) с группами из D^′, A \ D^′, B₀, B₁, C₀ и C₁.

Доказательство. Предположим, что существует такой поддизайн T ^′. В этом

случае имеется цветок {D^′, A^′, B^′, C^′}, где D^′ ∪A^′ = D ∪A. Обозначим B₀ := B ∩B^′,

B₁ := B ∩ C^′, C₀ := C ∩ B^′ и C₁ := C ∩ C^′. По следствию множества B₀, B₁, C₀, C₁

являются блоками B. Так как система B содержит подсистему троек Штейнера с но-

сителем D^′ ∪ A^′, то по определению цветка она имеет две почти подсистемы троек

Штейнера с носителями D^′ ∪B^′ и D^′ ∪C^′. Удаляя блоки B₀, B₁, C₀, C₁ из этих почти

подсистем, получаем два TD(3, 3). Остальные два поддизайна TD(3, 3) в T гаранти-

рованы предложением 1.

В обратную сторону утверждение проверяется столь же просто с учетом леммы 3.

Если B разбивается на два блока B₀, B₁, то из определения цветка и предложения 2

видно, что имеется почти подсистема троек Штейнера с носителем B ∪ D и недо-

стающей тройкой D (которая может быть или не быть блоком системы B). Это же

верно и для носителя C ∪ D. Тогда из определения цветка следует, что B содержит

полную подсистему троек Штейнера с носителем A ∪ D. Чтобы получить цветок со

стеблем D^′, остается найти еще два лепестка. По условию имеется трансверсальный

поддизайн с группами D^′, B₀ и C₀ для некоторого блока C₀ ⊂ C. Дополняя его бло-

ками B₀ и C₀, получаем почти подсистему троек Штейнера. Аналогично находим

почти подсистему троек Штейнера с носителем D^′ ∪ B₁ ∪ C₁, C₁ := C \ C₀. Таким

образом, набор {D^′, D ∪ A \ D^′, B₀ ∪ C₀, B₁ ∪ C₁} является цветком, и по лемме 3

имеется требуемый трансверсальный поддизайн. ▴

§ 3. Классификация систем STS(21) с поддизайном TD(3, 6)

Теперь на основе вышеприведенных лемм мы готовы представить наш метод

компьютерной классификации и его результаты. Начнем с описания того, как под-

считать число классов изоморфизма систем STS(21) с единственным поддизайном

TD(3, 6).

Вначале зафиксируем цветок {A₀₀₁, A₀₁₀ ∪ A₀₁₁, A₁₀₀ ∪ A₁₀₁, A₁₁₀ ∪ A₁₁₁}, где

все множества A₀₀₁, . . ., A₁₁₁ имеют размер 3. Пусть A - множество всех 840 систем

STS(9) на A₀₀₁ ∪ A₀₁₀ ∪ A₀₁₁. Обозначим через A^′ подмножество A, состоящее из

120 систем STS(9) с блоком A₀₀₁; удаляя этот блок из всех этих STS, получаем

множество A^∗ из 120 почти STS(9) с недостающим блоком A₀₀₁. Через A^′′ обозначим

подмножество A^′, состоящее из двенадцати систем STS(9) с блоками A₀₀₁, A₀₁₀, A₀₁₁.

Аналогично определим наборы B, B^′, B^′′, B^∗ систем троек на A₀₀₁ ∪ A₁₀₀ ∪ A₁₀₁ и

наборы C, C^′, C^′′, C^∗ систем троек на A₀₀₁ ∪ A₁₁₀ ∪ A₁₁₁.

Теперь выберем представителя T из одного из двенадцати (см. [19]) классов изо-

морфизма дизайнов TD(3, 6) с группами A₀₁₀ ∪ A₀₁₁, A₁₀₀ ∪ A₁₀₁, A₁₁₀ ∪ A₁₁₁. Кроме

того, потребуем, чтобы если этот представитель разбивался на поддизайны TD(3, 3),

то эти трансверсальные поддизайны имели бы наборы групп {A₀₁₀, A₁₀₀, A₁₁₀},

{A₀₁₀, A₁₀₁, A₁₁₁}, {A₀₁₁, A₁₀₀, A₁₁₁} и {A₀₁₁, A₁₀₁, A₁₁₀} (см. предложение 1).

Далее, по лемме 3 любая система STS(21) с трансверсальным поддизайном T

разбивается на T , A, B и C, где

- либо A ∈ A^′, B ∈ B^∗, C ∈ C^∗,

- либо A ∈ A \ A^′, B ∈ B^∗, C ∈ C^∗,

- либо A ∈ A^∗, B ∈ B \ B^′, C ∈ C^∗,

- либо A ∈ A^∗, B ∈ B^∗, C ∈ C \ C^′.

Более того, по леммам 5, 6 такая STS(21) имеет ровно семь поддизайнов TD(3, 6)

тогда и только тогда, когда T разбивается на поддизайны TD(3, 3) и при этом

A∪A₀₀₁ ∈A^′′, B∪A₀₀₁ ∈B^′′, C∪A₀₀₁ ∈C^′′,

(8)

и имеет ровно три поддизайна TD(3, 6) тогда и только тогда, когда T разбивается на

поддизайны TD(3, 3) и выполнены ровно два из условий (8). Исключая эти случаи,

окончательно получаем не более 120³ + 3 · 720 · 120² систем STS(21) с единственным

поддизайном TD(3, 6), равным T . С помощью программного средства для опреде-

ления изоморфности графов [20] можно проверять их всех на изоморфность и со-

хранять соответствующие представители. Очевидным образом, любая STS(21), име-

ющая трансверсальный поддизайн, изоморфный T , изоморфна некоторой STS(21),

содержащей T . Повторяя указанные шаги для всех двенадцати неизоморфных вы-

боров T , находим все классы эквивалентности систем STS(21) с только одной под-

системой STS(9).

Аналогично можно классифицировать системы STS(21) с тремя или семью под-

системами STS(9). Единственное отличие состоит в том, что требуется также про-

верять изоморфность представителей, полученных из разных T .

Результаты вычислений отражены в таблице. Последний столбец таблицы был

вычислен путем сравнения данных из остальных столбцов с результатами рабо-

Таблица

Количество классов изоморфизма систем STS(21) с поддизайном TD(3, 6), отсортирован-

ных по числу τ6 поддизайнов TD(3, 6), числу σ9 подсистем STS(9) и числу автоморфизмов

(в скобках приведено количество неизоморфных разрешимых систем, если оно известно)

τ6 = 7

τ6 = 3

τ6 = 1

τ6 = 0

|Aut|

σ9 = 7

σ9 = 3

σ9 = 1

σ9 = 3

σ9 = 1

98 (0)

171 (0)

101621 (355)

1865036 (0)

12656035473

45 (0)

36 (0)

5271 (14)

30771 (0)

3461498

37 (0)

66 (0)

103 (8)

52 (0)

14932

18 (0)

14 (0)

321 (1)

786 (0)

10328

1 (1)

31 (0)

45 (0)

24 (1)

8 (0)

157

1 (0)

7 (0)

1 (0)

60 (5)

23 (0)

130

1 (1)

9 (0)

1 (1)

6 (0)

8 (0)

5 (0)

1 (0)

2 (0)

9 (1)

2 (1)

3 (0)

1 (0)

7 (3)

1 (0)

2 (0)

1 (0)

108

1 (0)

144

1 (0)

504

1 (0)

1008

1 (1)

Итого

12 (5)

244 (0)

355 (0)

107427 (388)

1896682 (0)

12659522616

ты [15]. Все вычисления заняли несколько часов процессорного времени на совре-

менном персональном компьютере. Полученные результаты обобщает следующая

Теорема. Всего существует 2004720 систем троек Штейнера порядка 21

с трансверсальными поддизайнами на трех группах размера 6. При этом 2004109

из них имеют ровно один такой поддизайн TD(3, 6), 599 имеют ровно три под-

дизайна TD(3, 6), а 12 - семь поддизайнов TD(3, 6) (по лемме 5 последняя группа

совпадает с двенадцатью системами STS(21), имеющими семь подсистем STS(7),

найденными в [15]).

§4. Подтверждение результатов

В этом параграфе рассматривается подсчет двумя способами, подтверждающий

результаты вычислений.

Предложение 3. Для заданного множества точек S размера 21 существу-

ет ровно

21!

· (120³ + 3 · 720 · 120²) · 812851200 = 101473423278637842432000000

3!² · 6!³

пар (B, T ), где (S, B) - система STS(21), а T - поддизайн TD(3, 6) системы B.

Доказательство. Напомним вначале, что всего есть 840 различных STS(9)

с данным носителем (см., например, [21]), причем заданная тройка точек принадле-

жит ровно 120 из них.

Количество способов разбить множество мощности 21 на цветки {A, B, C, D} рав-

но 21! · 3!-2 · 6!-3. В предположении, что D - блок, есть 120 способов выбрать почти

подсистему троек Штейнера с каждым из носителей A ∪ D, B ∪ D и C ∪ D. В пред-

положении, что D - не блок, можно тремя способами выбрать, какое из множеств

A ∪ D, B ∪ D и C ∪ D является носителем подсистемы, затем 840 - 120 = 720 спо-

собами выбрать эту подсистему, и после этого 120 способами выбрать каждую из

двух остальных почти подсистем троек Штейнера. Наконец, число способов выбрать

трансверсальный дизайн с группами A, B, C равно 812851200 (общее число различ-

ных латинских квадратов размера 6 × 6 [22]). ▴

С другой стороны, это же число можно подсчитать с помощью полученных пред-

ставителей классов изоморфизма.

Предложение 4. Пусть S - множество из 21 точек, а S - множество

представителей всех классов изоморфизма систем STS(21) на S. Число пар (B, T ),

где (S, B) - система STS(21), а T - поддизайн TD(3, 6) системы B, задается фор-

мулой

∑

21!

N (B) ·

(9)

|Aut(B)|

B∈S

где N(B) - число поддизайнов TD(3, 6) в B.

Используя данные из таблицы, можно вычислить ненулевые (имеющие N(B) > 0)

слагаемые в сумме (9), что приводит к такому же значению суммы, что и в предло-

жении 3. Это подтверждает результаты наших вычислений.

§ 5. Разрешимость

Система троек Штейнера (S, B) называется разрешимой, если B можно разбить

на параллельные классы, где параллельный класс - это разбиение S на блоки. Мы

проверили все найденные системы на разрешимость и обнаружили 393 класса изо-

морфизма разрешимых STS рассматриваемого типа. Как видно из таблицы, не су-

ществует разрешимых STS(21) с поддизайном TD(3, 6) и только одной подсистемой

STS(9). Этот факт можно доказать теоретически.

Предложение 5. Если STS(21) имеет поддизайн TD(3,6) и только одну под-

систему STS(9), то эта система D неразрешима.

Доказательство. Пусть (S,D) - система STS(21), (A ∪ B ∪ C,{A,B,C},T ) -

поддизайн TD(3, 6), соответствующий цветку {A, B, C, D}, и пусть A - единствен-

ная подсистема троек Штейнера. Без ограничения общности будем считать, что

носителем A является A ∪ D. Таким образом, имеется две почти подсистемы тро-

ек Штейнера с носителями B ∪ D и C ∪ D соответственно, а также недостающая

тройка D. По условию D ∈ D.

Пусть D = {a, b, c}. Рассуждая от противного, предположим, что система име-

ет разрешение. Рассмотрим блок U, содержащий a и b, и параллельный класс P,

содержащий этот блок. Обозначим t := |P ∩ T |. Мы утверждаем, что

(∗) Блок V из P, содержащий c, принадлежит A.

Действительно, коль скоро он принадлежит B, то |B \ V | = 4, причем t из этих

четырех точек покрываются блоками из T ∩P, а остальные 4 - t - блоками из B ∩P.

Следовательно, 4 - t ≡ 0 mod 3. С другой стороны, t из шести точек множества C

покрыты блоками из T ∩ P, а остальные 6 - t - блоками из C ∩ P. Таким образом,

6 - t ≡ 0 mod 3, противоречие. Аналогично получаем V

∈ C, т.е. утверждение (∗)

справедливо.

Так как |A \ U \ V | = 3, то t ≤ 3. Поэтому P содержит хотя бы один блок из B

и хотя бы один блок из C, причем эти блоки не имеют точек из D. То же самое

можно сказать о параллельном классе, содержащем блок с a и c. Аналогично для

параллельного класса, содержащего блок с b и c. Отсюда получаем, что B имеет

по крайней мере три блока, не пересекающихся с D. Это противоречит предложе-

нию 2. ▴

Авторы выражают благодарность Светлане Топаловой за полезные обсуждения.

СПИСОК ЛИТЕРАТУРЫ

Hulpke A., Kaski P.,

Östergard P.R.J. The Number of Latin Squares of Order 11 // Math.

Comp. 2011. V. 80. № 274. P. 1197-1219.

Colbourn C.J., Mathon R. Steiner Systems // Handbook of Combinatorial Designs. Boca

Raton: Chapman & Hall/CRC. 2007. P. 102-110.

Kaski P.,

Östergard P.R.J. The Steiner Triple Systems of Order 19 // Math. Comp. 2004.

V. 73. № 248. P. 2075-2092.

Bays S. Recherche des systèmes cycliques de triples de Steiner différents pour N premier

(ou puissance de nombre premier) de la forme 6n + 1 // J. Math. Pures Appl. (9). 1923.

V. 2. P. 73-98.

Colbourn M.J. An Analysis Technique for Steiner Triple Systems // Proc. 10th Southeast-

ern Conf. on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca

Raton, Fla., 1979). Congress. Numer. V. 23-24. Winnipeg, Man.: Utilitas Math., 1979.

P. 289-303.

Denniston R.H.F. Nonisomorphic Reverse Steiner Triple Systems of Order 19 // Ann. Dis-

crete Math. 1980. V. 7. P. 255-264.

Mathon R.A., Phelps K.T., Rosa A. A Class of Steiner Triple Systems of Order 21 and

Associated Kirkman Systems // Math. Comp. 1981. V. 37. № 155. P. 209-222; 1995. V. 64.

№ 211. P. 1355-1356.

Phelps K.T., Rosa A. Steiner Triple Systems with Rotational Automorphisms // Discrete

Math. 1981. V. 33. № 1. P. 57-66.

Tonchev V.D. Steiner Triple Systems of Order 21 with Automorphisms of Order 7 // Ars

Combin. 1987. V. 23. P. 93-96; 1995. V. 39. P. 3.

10.

Kapralov S.N., Topalova S. On the Steiner Triple Systems of Order 21 with Automorphisms

of Order 3 // Proc. 3rd Int. Workshop on Algebraic and Combinatorial Coding Theory.

Voneshta Voda, Bulgaria. June 22-28, 1992. P. 105-108.

11.

Osuna O.P. There Are 1239 Steiner Triple Systems STS(31) of 2-rank 27 // Des. Codes

Cryptogr. 2006. V. 40. № 2. P. 187-190.

12.

Jungnickel D., Magliveras S.S., Tonchev V.D., Wassermann A. The Classification of Steiner

Triple Systems on 27 Points with 3-Rank 24 // Des. Codes Cryptogr. 2019. V. 87. № 4.

P. 831-839.

13.

Stinson D.R., Seah E. 284 457 Steiner Triple Systems of Order 19 Contain a Subsystem of

Order 9 // Math. Comp. 1968. V. 46. № 174. P. 717-729.

14.

Kaski P.,

Östergard P.R.J., Topalova S., Zlatarski R. Steiner Triple Systems of Order 19

and 21 with Subsystems of Order 7 // Discrete Math. 2008. V. 308. № 13. P. 2732-2741.

15.

Kaski P.,

Östergard P.R.J., Popa A. Enumeration of Steiner Triple Systems with Subsys-

tems // Math. Comp. 2015. V. 84. № 296. P. 3051-3067.

16.

Wilson R.M. Nonisomorphic Steiner Triple Systems // Math. Z. 1974. V. 135. № 4.

P. 303-313.

17.

Lindner C.C. A Survey of Embedding Theorems for Steiner Systems // Topics on Steiner

Systems. Amsterdam: North-Holland, 1980. P. 175-202.

18.

Bryant D., Horsley D. A Proof of Lindner’s Conjecture on Embeddings of Partial Steiner

Triple Systems // J. Combin. Des. 2009. V. 17. № 1. P. 63-89.

19.

Number of Species (or “Main Classes” or “Paratopy Classes”) of Latin Squares of Order n.

Sequence A003090 in The On-Line Encyclopedia of Integer Sequences. Published electroni-

cally at http://oeis.org , 2004.

20.

McKay B.D., Piperno A. Practical Graph Isomorphism, II // J. Symbolic Comput. 2014.

V. 60. P. 94-112.