Комбинаторная схема

Теория комбинаторных схем — это часть комбинаторики (раздела математики), рассматривающая существование, построение и свойства семейств конечных множеств, структура которых удовлетворяет обобщённым концепциям равновесия и/или симметрии. Эти концепции не определены точно, так что объекты широкого диапазона могут пониматься как комбинаторные схемы. Так, в одном случае комбинаторные схемы могут представлять собой пересечения множеств чисел, как в блок-схемах, а в другом случае могут отражать расположение элементов в судоку.

Теорию комбинаторных схем можно использовать при планировании экспериментов. Некоторые из основных комбинаторных схем приведены в работе Рональда Фишера по теории биологических экспериментов. Сейчас комбинаторные схемы можно найти в широком ряде областей, включая конечную геометрию, создание графиков турниров, лотереи, математическую биологию, разработку и анализ алгоритмов, вычислительные сети, групповое тестирование и криптографию.

Определение

Обозначим $v$ - множество элементов $m_{1},m_{2},...,m_{v}$. Рассмотрим подмножества этого множества $M_{1},M_{2},...,M_{b}$. Каждое подмножество $M_{j}$ называется блоком, а число элементов множества $M_{j}$ в нем называется объемом блока и обозначается как $k_{j}$. Пусть $r_{i}$ - число подмножеств $M$, содержащих этот элемент. Число повторений (неупорядоченных пар) обозначается как $\lambda _{p}$. Тогда множество блоков $M_{1},M_{2},...,M_{b}$ образует комбинаторную схему (или блок-схему) с параметрами $v,b,r_{i},k_{j},\lambda _{p}$.

Пример

Плоскость Фано

Если имеется n людей, можно ли составить из них множества, такие, что каждый человек принадлежит по меньшей мере одному множеству, каждая пара принадлежит в точности одному множеству, каждые два множества имеют в пересечении только одного человека и ни одно из множеств не состоит из всех людей, всех людей без одного или в точности одного человека? Ответ зависит от n.

Ответ положителен, только если n имеет вид q² + q + 1. Сложнее доказать, что решение существует, если q является степенью простого числа. Существует гипотеза, что других решений нет. Было доказано, что если решение существует для q, сравнимых с 1 или 2 по модулю 4, то q является суммой двух полных квадратов. Этот результат, теорема Брука — Райзера — Човла, был доказан путём комбинации методов построения, основывающихся на конечных полях, и квадратичных формах.

Когда такая структура существует, она называется конечной проективной плоскостью. Это показывает, как пересекаются теория конечных геометрий и комбинаторика. В случае q = 2, проективная плоскость называется плоскостью Фано.

История

Комбинаторные схемы известны ещё со времён античности в виде квадрата Ло Шу, который являлся ранней версией магического квадрата. Комбинаторные схемы развивались с развитием комбинаторики начиная с 18-го столетия, например, в виде латинских квадратов в 18-м веке и систем Штейнера в 19-м веке. Комбинаторные схемы популярны также в занимательной математике, как, например, в задаче Киркмана о школьницах (1850), и практических задачах, таких как составление расписания круговых турниров (решение опубликовано в 1880-х годах). В 20-м веке комбинаторные схемы были применены к планированию экспериментов, конечным геометриям и схемам отношений и привели к возникновению алгебраической статистики.

Фундаментальные комбинаторные схемы

Классическое ядро предмета комбинаторных схем строится вокруг сбалансированных неполноблочных схем (en:Balanced Incomplete Block Design, BIBD), матриц и схем Адамара, симметричных BIBD, латинских квадратов, разрешимых BIBD, разностных множеств и попарно сбалансированных схем (en: Pairwise Balanced Design, PBD). Другие комбинаторные схемы связаны с перечисленными или основываются на этих схемах.

• Сбалансированная неполноблочная схема (BIBD), которую для краткости называют блок-схемами, это набор B из b подмножеств (которые называются блоками) конечного множества X из v элементов, такой, что любой элемент множества X содержится в некотором числе r блоков, каждый блок имеет одинаковое число элементов (= k) и каждая пара различных элементов появляется в одинаковом числе ($=\lambda$) блоков. Схемы BIBD известны также как 2-схемы и часто обозначаются как $2-(v,k,\lambda )$ схемы. В качестве примера, для случая $\lambda =1$ и b = v мы получаем проективную плоскость — X в этом случае является множеством точек на плоскости, а блоки являются прямыми.
• Симметричная сбалансированная неполноблочная схема или SBIBD (en:Symmetric Balanced Incomplete Block Design) — это BIBD, в которой v  =  b (число точек равно числу блоков). Это наиболее важный и хорошо изученный подкласс BIBD. Проективные плоскости, биплоскости и 2-схемы Адамара являются SBIBD-схемами. Эти схемы представляют интерес как экстремальные примеры неравенства Фишера ($b\geqslant v$).
• Разрешимая сбалансированная неполная блок-схема — это BIBD, блоки которого могут быть разбиты на множества (называемые параллельными классами), каждое из которых образует разбиение точек BIBD. Множество параллельных классов называется разрешением схемы. Решение знаменитой задачи о 15 школьниках является разрешением BIBD с v  = 15, k  = 3 и $\lambda =1$.
• Латинский прямоугольник — это r × n ( r ≤ n) матрица, имеющая в качестве элементов числа 1, 2, 3, ..., n (или любое другое множество n различных символов), в которой никакое число не появляется дважды в любой строке или столбце. Латинский прямоугольник с размерами n × n называется латинским квадратом. Если r < n, то можно добавить n − r строк к латинскому прямоугольнику с размерами r × n, чтобы сформировать латинский квадрат, используя теорему Холла о свадьбах theorem.

Говорят, что два латинских квадрата порядка n ортогональны если множество всех упорядоченных пар, состоящих из соответствующих элементов двух квадратов, состоит из n² различных пар (то есть встречаются все возможные упорядоченные пары). Множество латинских квадратов одного порядка образует множество взаимно ортогональных латинских квадратов (en: Mutually Orthogonal Latin Squares, MOLS)), если любая пара латинских квадратов в множестве ортогональна. Может существовать максимум n − 1 квадратов в таком множестве квадратов порядка n. Множество n − 1 квадратов MOLS порядка n можно использовать для построения проективной плоскости порядка n (и наоборот).

• Разностное множество $(v,k,\lambda )$ — это подмножество D группы G порядка v, имеющее размер k, а любой не равный единице элемент группы G может быть представлен в виде произведения d₁d₂⁻¹ элементов D в точности $\lambda$ способами (если G представлено операцией умножения).

Если D — разностное множество и g принадлежит G, то $g\mathbf {D} ={gd\colon d\in \mathbf {D} }$ также является разностным множеством и называется переносом множества D. Множество переносов разностного множества D образует симметричную блок-схему. В такой схеме имеется v элементов и v блоков. Каждый блок схемы состоит из k точек, каждая точка содержится в k блоках. Любые два блока имеют в точности $\lambda$ общих элементов и любые две точки появляются вместе в $\lambda$ блоках. Эта схема SBIBD называется развитием множества D.

В частности, если $\lambda =1$, разностное множество образует проективную плоскость. Например, разностное множество (7,3,1) над группой $\mathbb {Z} /7\mathbb {Z}$ (абелева группа с аддитивной записью) — это подмножество {1,2,4}. Развитие этого разностного множества даёт плоскость Фано.

Поскольку любое разностное множество даёт SBIBD, множество параметров должно удовлетворять теореме Брука – Райзера – Човла, но не любая SBIBD-схема даёт разностное множество.

• Матрица Адамара порядка m — это m × m матрица H с элементами ±1, такая, что HH^⊤  = mE_m, где H^⊤ является транспонированной к H, а E_m — m × m единичная матрица. Матрицу Адамара можно привести к стандартизованной форме (то есть преобразовать в эквивалентную матрицу Адамара), в которой элементы первой строки и первого столбца равны +1. Если порядок m > 2, то m должно делиться на 4.

Если дана матрица Адамара порядка 4a в стандартизованной форме, удалим первую строку и первый столбец, а затем заменим все −1 на 0. Получившаяся 0–1 матрица M является матрицей инцидентности симметричной $2-(4a-1,2a-1,a-1)$ схемы, называемой адамаровой 2-схемой. Это построение обратимо, так что матрица инцидентности симметричной 2-схемы с такими параметрами может быть использована для получения матрицы Адамара порядка 4a. В случае a = 2 мы получаем уже знакомую плоскость Фано (как 2-схему Адамара).

• Попарно сбалансированная схема (en:Pairwise Balanced Design, PBD) — это множество X вместе с семейством подмножеств X (не обязательно одного размера и подмножества могут быть одинаковыми), таком, что любая пара различных элементов из X содержится точно в $\lambda$ (положительное число) подмножеств. Разрешается, чтобы множество X входило в семейство, а если все подмножества являются копиями множества X, схема PBD называется тривиальной. Размер множества X равен v, а число подмножеств в семействе (одинаковые подмножества подсчитываются отдельно) равно b.

Неравенство Фишера для схем PBD выполняется — для любой нетривиальной PBD-схемы выполняется $v\leqslant b$.

Этот результат обобщает знаменитую теорему де Брёйна — Эрдёша — для любой PBD-схемы с $\lambda =1$, не имеющей блоков размера 1 или v, выполняется $v\leqslant b$, при этом равенство имеет место тогда и только тогда, когда схема является проективной плоскостью или почти пучком.

Другие комбинаторные схемы

Книга «Handbook of Combinatorial Designs» (справочник по комбинаторным схемам) Колбурна и Диница содержит, среди прочих, 65 глав, посвящённых комбинаторным схемам, отличным от приведённых выше. Частичный список дан ниже.

• Схемы отношений
• Сбалансированные троичные схемы (en: Balanced Ternary Design) $BTD(V,B;\rho _{1},\rho _{2},R;K,\Lambda )$ — расстановка V элементов в B мультимножеств (блоков, мощность каждого множества K (K ≤ V)), удовлетворяющая условиям:

1. Каждый элемент появляется $R=\rho _{1}+2\rho _{2}$ раз с кратностью 1 (1 экземпляр в мультимножестве) точно в $\rho _{1}$ блоках, а с кратностью 2 — точно в $\rho _{2}$ блоках.
2. Каждая пара различных элементов появляется $\Lambda$ раз (учитывая кратность). То есть, если m_vb — кратность элемента v в блоке b, то для любой пары различных элементов v и w выполняется $\sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda$.

Например, одна из двух неизоморфных схем BTD(4,8;2,3,8;4,6) (блоками служат столбцы) — это

1	1	1	2	2	3	1	1
1	1	1	2	2	3	2	2
2	3	4	3	4	4	3	3
2	3	4	3	4	4	4	4

Матрица инцидентности BTD схемы (элементами которой служат кратности элементов в блоках) может быть использована для образования троичных исправляющих ошибки кодов аналогично построению двоичных кодов из матриц инцидентности BIBD схем.

• Сбалансированная турнирная схема порядка n (BTD(n)) — это размещение всех различных неупорядоченных пар 2n-множества V в массиве n × (2n − 1), такое что

1. каждый элемент множества V появляется ровно один раз в каждом столбце
2. каждый элемент множества V появляется не более двух раз в каждой строке.

Пример схемы BTD(3)

1 6	3 5	2 3	4 5	2 4
2 5	4 6	1 4	1 3	3 6
3 4	1 2	5 6	2 6	1 5

Столбцы схемы BTD(n) дают 1-факторизацию полного графа с 2n вершинами, K_2n.

Схемы BTD(n) могут быть использованы для составления расписания круговых турниров — строки представляют места, столбцы представляют туры (раунды, круги), а элементы таблицы задают игроков или команды.

• Бент-функции
• Массивы Костаса
• Полные факторные эксперименты
• Частотный квадрат (F-квадрат) является обобщением латинского квадрата. Пусть S = {s₁,s₂, ..., s_m} — множество различных символов, а $(\lambda _{1},\lambda _{2},...,\lambda _{m})$ — частотный вектор положительных чисел. Частотный квадрат порядка n $(n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})$ — это n × n массив, в котором каждый символ s_i встречается $\lambda _{i}$ раз (i = 1,2,...,m) в каждой строке и в каждом столбце. Частотный квадрат имеет стандартный вид, если в первой строке и первом столбце элементы s_i предшествуют s_j при i < j.

Частотный квадрат F₁ порядка n над множеством {s₁,s₂, ..., s_m} с частотным вектором $(\lambda _{1},\lambda _{2},...,\lambda _{m})$ и частотный квадрат F₂ также порядка n над множеством $\{t_{1},t_{2},...,t_{k}\}$ с частотным вектором $(\mu _{1},\mu _{2},...,\mu _{k})$ ортогональны, если любая упорядоченная пара (s_i, t_j) появляется ровно $\lambda _{i}\mu _{j}$ раз, когда F₁ и F₂ налагаются друг на друга.

• Системы троек Холла (en:Hall Triple Systems, HTS) — это системы троек Штейнера (en:Steiner Triple Systems, STS) (в ней блоки называются прямыми) со свойством, что подструктура, образованная пересечением двух прямых изоморфна конечной аффинной плоскости AG(2,3).

Любое аффинное пространство AG(n,3) даёт пример схемы HTS, такие схемы называются аффинными HTS. Неаффинные схемы HTS также существуют.

Число точек в схеме HTS равно 3^m для некоторого целого $m\geqslant 2$. Неаффинные схемы HTS существуют для любого $m\geqslant 4$ и не существуют для $m=2$ или 3.

Любая система троек Штейнера эквивалентна штейнеровской квазигруппе (идемпотентна, коммутативна и выполняется $(xy)y=x$ для всех x и y). Система троек Холла эквивалентна штейнеровской квазигруппе со свойством дистрибутивности, то есть выполняется $a(xy)=(ax)(ay)$ для всех a,x,y в квазигруппе .

• Пусть S — множество из 2n элементов. Схема Хауэлла, H(s,2n) (на множестве символов S) — это массив s × s, такой, что:

1. Каждая ячейка массива либо пуста, либо содержит неупорядоченную пару из S,
2. Каждый символ появляется в точности один раз в каждой строке и каждом столбце массива,
3. Каждая неупорядоченная пара появляется не более чем в одной ячейке массива.

Пример схемы H(4,6)

0 4		1 3	2 5
2 3	1 4	0 5
	3 5	2 4	0 1
1 5	0 2		3 4

H(2n − 1, 2n) — это Квадрат Рума со стороной 2n − 1, так что схемы Хауэлла обобщают концепцию квадратов Рума.

Пары символов в ячейках схемы Хауэлла можно рассматривать как рёбра s регулярного графа с 2n вершинами, который называется основным графом схемы Хауэлла.

Циклические схемы Хауэлла используются как передвижения Хауэлла (схема комплектации участников игр) в турнирах двойного бриджа. Строки схемы представляют туры (круги), столбцы представляют коробки (с подготовленными заранее сдачами, см. «Бридж — подготовка к игре»), а диагонали представляют столы.

• Линейные пространства
• Схема лото (n,k,p,t) — это множество V из n элементов вместе с набором $\beta$ k-элементных подмножеств (блоков), таких, что для любого подмножества P, состоящего из p элементов множества V, существует блок B в $\beta$, для которого $|P\cap B|\geqslant t$. L(n,k,p,t) означает наименьшее число блоков в любой схеме лото (n,k,p,t). Схема лото (7,5,4,3) с наименьшим возможным числом блоков:

{1,2,3,4,7}       {1,2,5,6,7}       {3,4,5,6,7}.

Схема лото моделирует любую лотерею, работающую по следующим правилам: Игрок покупает билеты, содержащие k чисел, выбранные из множества, содержащего n чисел. В некоторый момент времени продажа билетов прекращается и выбирается случайный набор из p чисел, содержащихся в исходном множестве из n чисел. Это выигрышные числа. Если проданный билет содержит t или более выигрышных номеров, приз отдаётся владельцу билета. Чем больше совпадений, тем выше выигрыш. Число L(n,k,p,t) интересно как для игроков, так и для исследователей, так как представляет наименьшее число билетов, которые следует купить, чтобы гарантировать выигрыш.

Венгерская лотерея — это схема лото (90,5,5,t) и известно, что L(90,5,5,2) = 100. Лотереи с параметрами (49,6,6,t) популярны во всём мире и известно, что L(49,6,6,2) = 19. В общем случае эти числа трудно вычислить и они остаются неизвестными.

Геометрическое построение одной из таких схем приведено в статье «Трансильванская лотерея».

• Магические квадраты
• Схема Мендельсона $(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda }})$ ($MD(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda }})$) — это множество V из v элементов и набор $\beta$ упорядоченных k-кортежей различных элементов множества V (называемых блоками), таких, что каждая упорядоченная пара (x,y) элементов из V (x ≠ y) циклически смежна в $\lambda$ блоках (упорядоченная пара (x,y) различных элементов циклически смежна в блоке, если элементы появляются в блоке рядом — либо (...,x,y,...), либо (y,...,x)). Схема $MD(\mathbf {v} ,\mathbf {3} ,{\boldsymbol {\lambda }})$ — это система троек Мендельсона, имеющая обозначение MTS$(\mathbf {v} ,{\boldsymbol {\lambda }})$. Пример MTS(4,1) над V = {0,1,2,3}:

(0,1,2)     (1,0,3)     (2,1,3)     (0,2,3)

Любая система троек может быть преобразована в систему троек Мендельсона путём замены неупорядоченной тройки {a,b,c} парой упорядоченных троек (a,b,c) и (a,c,b), но обратное, как показывает пример, неверно.

Пусть (Q,∗) — идемпотентная полусимметрическая квазигруппа, то есть в ней выполняется x ∗ x = x (идемпотентность) и x ∗ (y ∗ x) = y (полусимметричность) для всех x, y из Q. Пусть $\beta =\{(x,y,x\ast y)\colon x,y\in Q\}$. Тогда $(Q,\beta )$ является системой троек Мендельсона MTS(|Q|,1). Это построение обратимо.

• Ортогональные таблицы
• Квази-3 схема — это симметричная схема (SBIBD), в которой каждая тройка блоков пересекается либо в x, либо в y точках для фиксированных чисел x и y, называемых числами пересечений троек (x < y). Любая симметричная схема с $\lambda \leqslant 2$ является квази-3 схемой с $x=0$ и $y=1$. Схема точка-гиперплоскость геометрии PG(n,q) является квази-3 схемой с $x=(q^{n-2}-1)/(q-1)$ и $y=\lambda =(q^{n-1}-1)/(q-1)$. Если $y=\lambda$ для квази-3 схемы, схема изоморфна PG(n,q) или проективной плоскости.
• Схема $Dt-(v,k,\lambda )$ является квазисимметричной с числами пересечения x и y (x < y), если любые два различных блока имеют в пересечении либо x, либо y точек. Эти схемы возникают естественным образом при изучении двойственных схем с $\lambda =1$. Несимметричная схема (b > v) 2-(v,k,1) является квазисимметричной с x = 0 и y = 1. Кратные (блоки повторяются некоторое определённое число раз) симметричные 2-$(v,k,\lambda )$ схемы квазисимметричны с $x=\lambda$ и y = k. Адамаровы 3-схемы (расширение 2-схем Адамара) квазисимметричны.

Любая квазисимметричная блок-схема порождает сильно регулярный граф (как её блоковый граф), но не все схемы SRG порождаются таким образом.

Матрица инцидентности квазисимметричной схемы 2-$(v,k,\lambda )$ с k ≡ x ≡ y (mod 2) образует двоичный самоортогональный код.

• Квадраты Рума
• Сферический дизайн — это конечное множество X точек на a (d − 1)-мерной сфере, такое, что для некоторого целого t, среднее значение на X полинома

$f(x_{1},\ldots ,x_{d})\$

со степенью, не превосходящей t, равно среднему значению f на всей сфере (то есть интегралу функции f, делённому на площадь сферы).

• Системы Турана
• Тосканский r × n k-прямоугольник над n символами имеет r строк и n столбцов, при этом

1. каждая строка является перестановкой n символов
2. для любых двух различных символов a и b и для каждого числа m от 1 до k существует не более одной строки , в которой b находится в m шагах правее a.

Если r = n и k = 1, схемы называются тосканскими квадратами, а в случае r = n и k = n - 1 они называются флорентийскими квадратами. Римский квадрат — это тосканский квадрат, являющийся одновременно латинским квадратом (такие квадраты известны также как полные по строкам латинские квадраты). Ватиканский квадрат — это флорентийский квадрат, являющийся одновременно латинским квадратом.

Пример тосканского 1-квадрата на 7 символах, не являющегося 2-квадратом:

6	1	5	2	4	3	7
2	6	3	5	4	7	1
5	7	2	3	1	4	6
4	2	5	1	6	7	3
3	6	2	1	7	4	5
1	3	2	7	5	6	4
7	6	5	3	4	1	2

Тосканский квадрат на n символах эквивалентен декомпозиции полных графов с n вершинами на n гамильтоновых ориентированных путей.

• t-кратная сбалансированная схема (или t BD) типа t-$(v,K,\lambda )$ — это множество X из v элементов вместе с семейством подмножеств X (называемых блоками), размеры которых содержатся в наборе K, таком, что любое t-подмножество различных элементов X содержится в точности в $\lambda$ блоках. Если K — набор положительных целых чисел строго между t и v, то схема t BD называется собственной. Если все k-подмножества X для некоторого k являются блоками, схема t BD называется тривиальной.

Заметим, что в примере 3-{12,{4,6},1) схемы на множестве X = {1,2,...,12} некоторые пары появляются четыре раза (например, пара {1,2}), в то время, как другие появляются пять раз (например, пара {6,12}).

1 2 3 4 5 6            1 2 7 8      1 2 9 11      1 2 10 12      3 5 7 8      3 5 9 11      3 5 10 12      4 6 7 8      4 6 9 11      4 6 10 12

7 8 9 10 11 12      2 3 8 9      2 3 10 7      2 3 11 12      4 1 8 9      4 1 10 7      4 1 11 12      5 6 8 9      5 6 10 7      5 6 11 12

                             3 4 9 10      3 4 11 8      3 4 7 12      5 2 9 10      5 2 11 8      5 2 7 12      1 6 9 10      1 6 11 8      1 6 7 12

                             4 5 10 11      4 5 7 9      4 5 8 12      1 3 10 11      1 3 7 9      1 3 8 12      2 6 10 11      2 6 7 9      2 6 8 12

                             5 1 11 7      5 1 8 10      5 1 9 12      2 4 11 7      2 4 8 10      2 4 9 12      3 6 11 7      3 6 8 10      3 6 9 12

• Неполный латинский квадрат — это k × v прямоугольный массив (k < v) v символов, таких, что каждый символ появляется в точности один раз в каждой строке и символы, появляющиеся в любом столбце, образуют блоки симметричной схемы $(v,k,\lambda )$, все блоки которой появляются в точности один раз. Неполный латинский квадрат является латинским прямоугольником. Термин "квадрат" в названии появился из более старого определения, которое использовало квадратный массив. Пример неполного латинского 4 × 7 квадрата:

1	2	3	4	5	6	7
2	3	4	5	6	7	1
3	4	5	6	7	1	2
5	6	7	1	2	3	4

Семь блоков (столбцов) образует биплоскость порядка 2 (симметричная схема (7,4,2)).