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

Система Штейнера (названа именем Якоба Штейнера) — вариант блок-схем, точнее, t-схемы с λ = 1 и t ≥ 2.

Система Штейнера с параметрами t, k, n (записывается S(t,k,n)) — это n-элементное множество S вместе с набором k-элементных подмножеств множества S (называемых блоками) со свойством, что каждое t-элементное подмножество S содержится ровно в одном блоке. В альтернативном обозначении блок-схем S(t,k,n) обозначается как t-(n,k,1) схема.

Это определение относительно ново и обобщает классическое определение системы Штейнера, в котором дополнительно требуется, чтобы k = t + 1. Схема S(2,3,n) называлась (и по-прежнему называется) системой троек Штейнера, S(3,4,n) называлась системой четвёрок Штейнера и так далее. После обобщения определения система имён соблюдается не так строго.

В теории схем было долгое время неизвестно, существует ли нетривиальная (t < k < n) систем Штейнера с t ≥ 6, а также существует ли бесконечно много схем с t = 4 или 5. Утвердительный ответ дал Питер Киваш в 2014.

Источник: Википедия

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я