Система Штейнера
Систе́ма Ште́йнера, пара , где – конечное множество из элементов, а – совокупность -подмножеств множества (называемых блоками) такая, что каждое -подмножество множества содержится точно в одном блоке множества (). Число называется порядком системы Штейнера . Система Штейнера является частным случаем блок-схемы, а также тактической конфигурации. Система Штейнера с является уравновешенной неполной блок-схемой (BIB-схемой), а при , – конечной проективной плоскостью. Необходимым условием существования системы Штейнера является условие того, что числодолжно быть целым при всех таких , что . Доказана достаточность этого условия при (см. Lindner. 1978; Hanani. 1975).
В 1844 г. У. Вулхаус (W. Woolhouse) поставил проблему существования системы Штейнера, а П. Киркман (Р. Kirkman) в 1847 г. решил её для (системы троек Штейнерa). В 1853 г. Я. Штейнер (Steiner. 1853) рассмотрел
Для системы Штейнера обычно рассматриваются задачи:
1) определения максимального числа попарно неизоморфных систем Штейнера данного порядка ;
2) существования систем Штейнера с заданной группой автоморфизмов;
3) вложения частичных систем Штейнера (не содержащих некоторых -подмножеств ) в конечную систему Штейнера;
4) существования разрешимых систем Штейнера (с , представимой как объединение разбиений );
5) максимальной упаковки (минимального покрытия) полного множества -подмножеств попарно не пересекающимися (с помощью системы Штейнера).
Большинство результатов по системе Штейнера относятся к небольшим значениям и (см. Xолл. 1970; Lindner. 1978; Hanani. 1975).