тройки Штейнера

[Вилл в носочках]

Помогите, пожалуйста, совсем запуталась)

Системой троек Штейнера называется такое разбиение множества N={1,... n} на подмножества по 3 элемента, что для любых двух элементов из N существует одна и только одна тройка, содержащая их обоих.
Для n=7, система троек Штейнера выглядит так:
(1,2,3) , (1,4,6), (1,7,5), (2,5,6), (2,4,7), (6,3,7), (3,4,5).
Это не единственный вариант системы троек Штейнера для n=7. Например, поменяв во всех этих тройках местами 2 любых элемента (скажем, 2 везде заменить на 4, а 4 на 2), мы получим изоморфную систему.

Задача как раз заключается в том, чтобы описать группу автоморфизмов систем троек Штейнера при n=7

решение

Понятно, что в числе элементов группы автоморфизмов будут всевозможные замены двух элементов друг на друга (a<->b). Таких замен всего C(2,7) = 21.
Еще можно менять "блоками по 2", например, "2<->7, 3<->4".
Дальше туплю =(. Всего систем троек Штейнера (n=7) у меня аналитически получилось 30. 21 штука уходит на замены по одному элементу, остается 9. Но замен по 2 элемента, вроде получается очень много... И почему других каких-нибудь автоморфизмов нет, тоже не ясно

@темы: Теория групп, Дискретная математика, Комбинаторика

Comments

[вейко]

как понимается в этом контексте изоморфизм?

порядок следования в тройке не важен?

[Вилл в носочках]

порядок следования не важен.
изоморфизм - подстановка длины n, отображающая тройки в тройки.

[Вилл в носочках]

или вот так лучше: Перестановки элементов N, сохраняющие систему Штейнера, называются её автоморфизмами.

[Trotil]

www.tcs.hut.fi/~pkaski/sts19.ps

Про тройки Штейнера порядка 19.

[Alidoro]

Пока видно, что это проективная плоскость. Каждая тройка это прямая. Любые две точки определяют единственную прямую и любые две прямые пересекаются в единственной точке. То есть это автоморфизмы проективной плоскости. Может быть, в конечных геометриях поискать?
Вот здесь есть картинка этой плоскости.

[kostyaknop]

НЯП, "проективная" картинка помогает понять,что к чему, но объяснить все можно и в терминах троек.
Итак, пусть 1 -> x1, 2 -> x2, 3 -> x3. Тогда в получившейся системе троек должна быть тройка (x1,x2,x3).
Если, кроме этого, 4 -> x4, то образы всех остальных чисел (и все остальные тройки) уже определены однозначно. Например, 6 должно перейти в число, которое образует тройку с x1 и x4. 5 должно перейти в третье число тройки с x3 и x4, 7 должно перейти в третье число тройки c x2 и x4.

Ну вот, собственно, и все. Это полностью характеризует автоморфизм. Для любой подстановки (1,2,3,4)->(x1,x2,x3,x4) изоморфная система троек оказывается задана, причем однозначно.

[Вилл в носочках]

kostyaknop, спасибо!
но если, например, 1 -> 1, 2 -> 4, 3 -> 6, 4 -> 2, то мы получим исходную систему. И таких случаев много. Это не самый удачный вариант описания, потому что мне еще надо выписать все эти 3ки =)

[Alidoro]

Файл ps можно преобразовать в pdf чем-нибудь. Я сделал это online на сайте Adobe. Но для этого надо иметь на сайте регистрацию. Вот результат преобразования: zalil.ru/32925400 (Файл будет удален через 10 дней после последнего скачивания.)

[Гость]

Зеркало
www.onlinedisk.ru/file/847143/

[Вилл в носочках]

Alidoro, спасибо, уже нашла, там же где и ps лежит pdf =)

Такой вопрос, я верно посчитала число всевозможных систем троек Штейнера для n=7?

Рассмотрим тройки, содержащие "1". Их 3 штуки в любой системе.
В любой системе есть тройка, содержащая 1 и 2. Тройки могут быть:
(1,2,3) (1,2,4) (1,2,5) (1,2,6) (1,2,7) - всего 5 шт.
Если какая-то из этих троек лежит в нашей системе (=> никакая из оставшихся 4ех не лежит), то еще две тройки с "1" можно добрать 3 способами:
Пусть есть тройка (1,2,3), тогда вместе с ней могут лежать тройки:
(1,4,5) и (1,6,7), или
(1,4,6) и (1,5,7), или
(1,4,7) и (1,5,6).

Таким образом, есть 5*3 вариантов выбрать 3 тройки, содержащие "1", и удовлетворяющие системе Штейнера.
Имея 3 тройки с "1", есть всего 2 варианта, как дополнить их до системы троек Штейнера. Так как, например, для элемента "3" осталось всего 4 тройки, в которых "3" может содержаться, две из них будут определять одну систему, а две другие - другую.
При наличии уже пяти троек Штейнера, оставшиеся 2 достраиваются однозначно.

Т.о. всего различных систем троек Штейнера (n=7) 5*3*2=30.

[Вилл в носочках]

kostyaknop, с однозначностью тоже вопрос

пусть (1,2,3,4)->(x1,x2,x3,x4)

оставшиеся 5,6,7 -> (x5,x6,x7) или в (x6,x7,x5), или в (x7,x5,x6), нет?

[Alidoro]

Вот здесь обсуждают данную группу.
reslib.com/book/Osnovi_proektivnoj_geometrii#31

[Вилл в носочках]

Аналогия с геометрией и точками вообще не понятна.

Но, походу, любая перестановка (1,2,3,4,5,6,7)->(x1,x2,x3,x4,x5,x6,x7) будет являться автоморфизмом для множества S={все системы троек Штейнера n=7}. Другое дело, что некоторые из них будут давать одинаковый результат.

[Alidoro]

"проективная" картинка помогает понять,что к чему, но объяснить все можно и в терминах троек.

Понятно, что это так. Уже готовые факты и доказательства, касающиеся плоскости Фано, можно изложить на языке троек.

[Alidoro]

Коллинеации это те элементы `S_7`, которые сохраняют прямые, т. е. тройки. Их `7*6*5`. Они образуют подгруппу. Фактор-группа `S_7` по этой группе действует на трехэлементных подмножествах множества `{1,2,3,4,5,6,7}`. Число элементов в ней `1*2*3*4`. Насколько я понимаю, именно эту группу вам надо описать?

[Вилл в носочках]

Alidoro, может быть 0_о
В ком `1*2*3*4` элементов?

[Alidoro]

В той группе, которую по моему предположению вы ищете, т. е. в факторгруппе, которую я описал.

[Вилл в носочках]

Alidoro, любая перестановка чисел (1,2,3,4,5,6,7) будет переводить систему троек Штейнера, в некоторую другую систему троек Штейнера, возможно аналогичную.
Также в литературе было найдено без доказательства, что для n=7 все системы троек Штейнера изоморфны (для любых двух систем троек можно найти перестановку, переводящую одну систему в другую). Почему это так, мне пока не понятно.
Для примера, есть 2 не изоморфные системы троек Штейнера при n=13.

Я не понимаю описание вашей фактор-группы.

[Alidoro]

Вы, наверно, это читаете: reslib.com/book/Kombinatornij_analiz#67

[Вилл в носочках]

Alidoro, да, Холла. И еще Рыбникова.

[Вилл в носочках]

Alidoro, Вы описывали такие преобразования элементов 1,2...7, которые приведут данную систему троек в ту же систему троек?

Я так понимаю, надо найти все п: S{все системы троек Штейнера n=7} -> {все системы троек Штейнера n=7}

[Alidoro]

Мы берем те подстановки из 7 элементов, которые оставляют тройки на месте. На языке геометрии это те отображения точек на себя, которые переводят прямые в прямые. Это подгруппа. Любой элемент этой подгруппы однозначно задается образом трех точек. Но нам нужно найти такие подстановки, которые меняют систему троек (на изоморфную, естественно). Любая подстановка, которая принадлежит одному и тому же смежному классу по описанной подгруппе меняет эту систему троек одинаково. То есть искомая группа изоморфна фактор группе. Здесь надо еще убедиться, что подгруппа является нормальным делителем. И, конечно, придумать как описать элемент факторгруппы.

[Вилл в носочках]

Alidoro, что значит "оставляет тройки на месте" на языке троек? Точнее, какая подстановка "не оставит тройки на месте", на языке троек же.

[Alidoro]

Значит образом тройки является какая-то тройка. Ну и наоборот.

[Вилл в носочках]

Alidoro, все перестановки "оставляют тройки на местах", я вот об этом.

[Alidoro]

Точнее. Одна тройка может переместиться в другую тройку. Но сам набор троек будет тот же.

[Вилл в носочках]

???

[Alidoro]

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

[Вилл в носочках]

Alidoro, ну, это очевидно, и что? до подстановки была (1,2,3) после подстановки (1->x1, 2->x2, 3->x3) будет тройка (x1,x2,x3).
Любая подстановка из S_7 даст не какую-нибудь фигню, а снова систему троек Штейнера. Другое дело, что она может дать ту же самую систему с точностью до перестановки троек и чисел внутри троек. Это я написала уже давно.
Значит искомая группа автоморфизмов Aut(S) содержит S_7.

[Alidoro]

Это я написала уже давно.

Вообще-то я писал другое.

Значит искомая группа автоморфизмов Aut(S) содержит S_7.

содержится в S_7 вы хотели сказать? Формально это не так. Элементы этих групп это отображения разных множеств.
Утверждение, что первая группа изоморфна некоторой подгруппе из S_7 тоже сомнительно, хотя случайно может оказаться верным.
Очевидно лишь то, о чем вы "написали уже давно", что существует гомоморфизм группы S_7 на искомую группу. Ядро этого гомоморфизма (коллинеации плоскости Фано) и исследуется у Хартсхорна.

Может быть, я, не особо вникая в задачу, пишу очевидные для вас вещи, тогда извините.