Система Штейнера

Систе́ма Ште́йнера, пара ${\displaystyle (V,B)}$, где ${\displaystyle V}$ – конечное множество из ${\displaystyle v}$ элементов, а ${\displaystyle B}$ – совокупность ${\displaystyle k}$-подмножеств множества ${\displaystyle V}$ (называемых блоками) такая, что каждое ${\displaystyle t}$-подмножество множества ${\displaystyle V}$ содержится точно в одном блоке множества ${\displaystyle B}$ (${\displaystyle t<k}$). Число ${\displaystyle v}$ называется порядком системы Штейнера ${\displaystyle S(t,k,v)}$. Система Штейнера является частным случаем блок-схемы, а также тактической конфигурации. Система Штейнера с ${\displaystyle t=2}$ является уравновешенной неполной блок-схемой (BIB-схемой), а при ${\displaystyle v=s^{2}+s+1}$, ${\displaystyle \ k=s+1}$ – конечной проективной плоскостью. Необходимым условием существования системы Штейнера ${\displaystyle S(t,k,v)}$ является условие того, что число

${\displaystyle \left({\begin{array}{l}v-s\\t-s\end{array}}\right){\Big /}\left({\begin{array}{l}k-s\\t-s\end{array}}\right)}$

должно быть целым при всех таких ${\displaystyle s}$, что ${\displaystyle 0\leqslant s<t}$. Доказана достаточность этого условия при ${\displaystyle (k,t)=(3,2),(4,2),(5,2),(4,3)}$ (см. ^[1]; ^[2]).</t<></math></k<></math>

В 1844 г. У. Вулхаус (W. Woolhouse) поставил проблему существования системы Штейнера, а П. Киркман (Р. Kirkman) в 1847 г. решил её для ${\displaystyle k=3}$ (системы троек Штейнерa). В 1853 г. Я. Штейнер (^[3]) рассмотрел ${\displaystyle S(t,t+1,v)}$.

Для системы Штейнера обычно рассматриваются задачи:
1) определения максимального числа попарно неизоморфных систем Штейнера данного порядка ${\displaystyle v}$;
2) существования систем Штейнера с заданной группой автоморфизмов;
3) вложения частичных систем Штейнера (не содержащих некоторых ${\displaystyle t}$-подмножеств ${\displaystyle V}$) в конечную систему Штейнера;
4) существования разрешимых систем Штейнера (с ${\displaystyle B}$, представимой как объединение разбиений ${\displaystyle V}$);
5) максимальной упаковки (минимального покрытия) полного множества ${\displaystyle k}$-подмножеств ${\displaystyle V}$ попарно не пересекающимися ${\displaystyle S(t,k,v)}$ (с помощью системы Штейнера).

Большинство результатов по системе Штейнера относятся к небольшим значениям ${\displaystyle k}$ и ${\displaystyle t}$ (см. ^[4]; Lindner. 1978; Hanani. 1975).