Комбинаторный дизайн

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

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

Пример

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

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

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

История

Комбинаторные конструкции восходят к древности, а квадрат Ло Шу был ранним магическим квадратом . Одно из самых ранних датируемых применений комбинаторного дизайна можно найти в Индии в книге Варахамихиры «Брихат Самхита» , написанной около 587 года нашей эры, с целью создания духов с использованием 4 веществ, выбранных из 16 различных веществ с помощью магического квадрата. ^[2]

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

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

Классическое ядро предмета комбинаторных планов построено вокруг сбалансированных неполных блочных планов (BIBD) , матриц Адамара и планов Адамара , симметричных BIBD , латинских квадратов , разрешимых BIBD , разностных множеств и попарно сбалансированных планов (PBD). ^[3] Другие комбинаторные схемы связаны с изучением этих фундаментальных моделей или были разработаны в результате их изучения.

Сбалансированная неполная блочная конструкция или BIBD (обычно называемая для краткости блочной конструкцией ) — это совокупность B из b подмножеств (называемых блоками ) конечного набора X из v элементов, такая, что любой элемент X содержится в том же числе r блоков, каждый блок имеет одинаковое количество k элементов, и каждая пара различных элементов появляется вместе в одном и том же количестве λ блоков. BIBD также известны как 2-схемы и часто обозначаются как 2-( v , k ,λ) конструкции. Например, когда λ = 1 и b = v , у нас есть проективная плоскость : X — множество точек плоскости, а блоки — это прямые.
Симметричная сбалансированная неполная блочная конструкция или SBIBD — это BIBD, в которой v = b (количество точек равно количеству блоков). Это самый важный и хорошо изученный подкласс BIBD. Проективные плоскости, бипланы и 2-планы Адамара — все это SBIBD. Они представляют особый интерес, поскольку являются экстремальными примерами неравенства Фишера ( b ≥ v ).
Разрешимый BIBD — это BIBD, блоки которого могут быть разделены на множества (называемые параллельными классами ), каждый из которых образует раздел множества точек BIBD. Набор параллельных классов называется разрешением проекта. Решение знаменитой задачи о 15 школьницах — это решение BIBD с v = 15, k = 3 и λ = 1. ^[4]
Латинский прямоугольник — это матрица размера r × n , в которой в качестве элементов имеются числа 1, 2, 3, ..., n (или любой другой набор из n различных символов), при этом ни одно число не встречается более одного раза в любой строке или столбце, где р ≤ п . Латинский прямоугольник размера n × n называется латинским квадратом . Если r < n , то можно добавить n − r строк к латинскому прямоугольнику размером r × n , чтобы сформировать латинский квадрат, используя теорему Холла о браке . ^[5]

Два латинских квадрата порядка n называются ортогональными, если множество всех упорядоченных пар, состоящих из соответствующих элементов в двух квадратах, имеет n ² различных членов (встречаются все возможные упорядоченные пары). Набор латинских квадратов одного и того же порядка образует набор взаимно ортогональных латинских квадратов (MOLS), если каждая пара латинских квадратов в наборе ортогональна. В наборе МОЛС порядка n может быть не более n − 1 квадратов . Набор из n - 1 MOLS порядка n можно использовать для построения проективной плоскости порядка n (и наоборот).

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

Если D — разностное множество, а g в G , то g D = { gd : d в D } также является разностным множеством и называется трансляцией D. Набор всех трансляций разностного набора D образует симметричный BIBD . В такой конструкции есть v -элементы и v -блоки. Каждый блок конструкции состоит из k точек, каждая точка содержится в k блоках. Любые два блока имеют ровно λ общих элементов, и любые две точки встречаются вместе в λ блоках. Этот SBIBD называется развитием D. ^[7]

В частности, если λ = 1, то разностное множество порождает проективную плоскость . Примером разностного множества (7,3,1) в группе (абелева группа, записанная аддитивно) является подмножество {1,2,4}. Развитие этого множества разностей дает плоскость Фано .

\mathbb {Z} /7\mathbb {Z}

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

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

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

Попарно сбалансированный план ( или PBD) — это набор X вместе с семейством подмножеств X (которые не обязательно должны иметь одинаковый размер и могут содержать повторы) такие, что каждая пара различных элементов X содержится ровно в λ (положительный целое число) подмножества. Множество X может быть одним из подмножеств, и если все подмножества являются копиями X , PBD называется тривиальным . Размер X равен v , а количество подмножеств в семействе (с учетом кратности) равно b .

Неравенство Фишера справедливо для PBD: ^[9] Для любого нетривиального PBD v ≤ b .

Этот результат также обобщает знаменитую теорему Эрдеша-Де Брюйна : для PBD с λ = 1, не имеющего блоков размера 1 или размера v , v ≤ b , с равенством тогда и только тогда, когда PBD является проективной плоскостью или почти карандашом. . ^[10]

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

« Справочник по комбинаторным планам» (Колборн и Диниц, 2007), среди прочего, содержит 65 глав, каждая из которых посвящена комбинаторным планам, отличным от приведенных выше. Частичный список приведен ниже:

Схемы ассоциации
Сбалансированная троичная конструкция BTD( V , B ; ρ ₁ , ρ ₂ , R ; K , Λ) представляет собой расположение элементов V в B мультимножества (блоки), каждый из которых имеет мощность K ( K ≤ V ), удовлетворяющее:

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

Например, один из двух неизоморфных BTD(4,8;2,3,8;4,6) (блоки являются столбцами): ^[11]

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

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

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

Пример BTD(3) дан:

Столбцы BTD( n ) обеспечивают 1-факторизацию полного графа по 2 n вершинам, K _{2 n} . ^[13]

BTD( n ) можно использовать для планирования турниров по круговой системе : строки обозначают локации, столбцы — раунды игры, а записи — соревнующиеся игроки или команды.

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

Квадрат частоты F ₁ порядка n на основе набора { s ₁ , s ₂ , ..., s _m } с вектором частоты ( λ ₁ , λ ₂ , ..., λ _m ) и квадрата частоты F ₂ , также порядка n , на основе набора { t ₁ , t ₂ , ..., t _k } с частотным вектором ( µ ₁ , µ ₂ , ..., µ _k ) ортогональны , если каждая упорядоченная пара ( s _i , t _j ) появляется ровно λ _i µ _j раз, когда F ₁ и F ₂ накладываются.

Системы троек Холла (HTS) представляют собой системы троек Штейнера (STS) (но блоки называются линиями ) со свойством, что подструктура, порожденная двумя пересекающимися прямыми, изоморфна конечной аффинной плоскости AG(2,3).

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

Число точек HTS равно 3 ^m для некоторого целого числа m ≥ 2. Неаффинные HTS существуют для любого m ≥ 4 и не существуют для m = 2 или 3. ^[14]

Каждая система троек Штейнера эквивалентна квазигруппе Штейнера ( идемпотентной , коммутативной и удовлетворяющей условиям ( xy ) y = x для всех x и y ). Система троек Холла эквивалентна квазигруппе Штейнера, которая является дистрибутивной , то есть удовлетворяет условию a ( xy ) = ( ax )( ay ) для всех a , x , y в квазигруппе. ^[15]

Пусть S — набор из 2n элементов . Дизайн Хауэлла H ( s ,2 n ) (на наборе символов S ) представляет собой массив размером s × s , такой что:

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

Пример H (4,6):

H(2 n - 1, 2 n ) - это квадрат комнаты со стороной 2 n - 1, и, таким образом, конструкции Хауэлла обобщают концепцию квадратов комнаты.

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

Циклические конструкции Хауэлла используются в качестве движений Хауэлла в дублирующих турнирах по бриджу. Ряды рисунка представляют раунды, столбцы — доски, а диагонали — столы. ^[16]

Линейные пространства
Схема ( n , k , p , t )-лотереи представляет собой n -множество V элементов вместе с набором β из k -элементных подмножеств V (блоков), так что для любого p -подмножества P из V существует блок B в β , для которого |P ∩ B | ≥ т . L( n , k , p , t ) обозначает наименьшее количество блоков в любой ( n , k , p , t )-схеме лотереи. Ниже приведена (7,5,4,3)-лотерея с наименьшим возможным количеством блоков: ^[17]

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

Проекты лотереи моделируют любую лотерею , которая проводится следующим образом: люди покупают билеты , состоящие из k номеров, выбранных из набора из n чисел. В определенный момент продажа билетов прекращается и из n номеров случайным образом выбирается набор из p чисел . Это выигрышные номера . Если какой-либо проданный билет содержит 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. Однако в целом эти числа трудно вычислить и они остаются неизвестными. ^[18]

Геометрическая конструкция одного из таких рисунков представлена в трансильванской лотерее .

Магические квадраты
( v , k , λ ) -план Мендельсона , или MD( v , k , λ ), представляет собой v -множество V и набор β упорядоченных k -кортежей различных элементов V (называемых блоками ), таких, что каждый упорядоченная пара ( x , y ) с x ≠ y элементов V циклически смежна в λ блоках. Упорядоченная пара ( x , y ) различных элементов является циклически смежной в блоке, если элементы появляются в блоке как (..., x , y ,...) или ( y ,..., x ). MD( v ,3, λ ) — это система троек Мендельсона , MTS( v , λ ). Пример 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 , пусть β = {( x , y , x ∗ y ): x , y в Q }. Тогда ( Q , β) — система троек Мендельсона MTS(| Q |,1). Эта конструкция обратима. ^[19]

Ортогональные массивы
План квази-3 — это симметричный проект (SBIBD), в котором каждая тройка блоков пересекается либо в точках x , либо в точках y , для фиксированных x и y , называемых числами тройного пересечения ( x < y ). Любой симметричный план с λ ≤ 2 представляет собой квази-3-план с x = 0 и y = 1. План «точка-гиперплоскость» PG ( n , q ) представляет собой квази-3-план с x = ( q ^{n −2} − 1 )/( q − 1) и y = λ = ( q ^{n −1} − 1)/( q − 1). Если y = λ для плана квази-3, план изоморфен PG ( n , q ) или проективной плоскости . ^[20]
Схема D t -( v , k , λ ) является квазисимметричной с числами пересечения x и y ( x < y ) , если каждые два различных блока пересекаются либо в точках x , либо в y . Эти планы естественным образом возникают при исследовании двойственных планов с λ = 1. Несимметричный ( b > v ) 2-( v , k ,1) план квазисимметричен с x = 0 и y = 1. Кратный ( повторить все блоки определенное количество раз) симметричной 2-( v , k , λ ) конструкции квазисимметрична с x = λ и y = k . 3-схемы Адамара (расширения 2-схем Адамара ) квазисимметричны. ^[21]

Каждая квазисимметричная блочная конструкция приводит к сильно регулярному графу (как и его блочный граф), но не все SRG возникают таким образом. ^[22]

Матрица инцидентности квазисимметричной 2-( v , k , λ ) схемы с k ≡ x ≡ y (mod 2) генерирует двоичный самоортогональный код (когда он ограничен, если k нечетно). ^[23]

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

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

суммарной степени не более t равна среднему значению f на всей сфере, т. е. интегралу от f , деленному на площадь сферы.

Системы Туран
Тосканский прямоугольник размера r × n на n символах имеет r строк и n столбцов такие, что :

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

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

Следующий пример представляет собой квадрат тосканского-1 из 7 символов, который не является тосканским-2: ^[24]

Тосканский квадрат на n символах эквивалентен разложению полного графа с n вершинами на n гамильтоновых направленных путей. ^[25]

В последовательности зрительных впечатлений одна флеш-карта может оказывать определенное влияние на впечатление, производимое следующей. Эту предвзятость можно устранить, используя n последовательностей, соответствующих строкам тосканского квадрата размера n × n . ^[26]

t-сбалансированный план ( или t BD) типа t − ( v ,K, λ ) представляет собой v -множество X вместе с семейством подмножеств X (называемых блоками ), размеры которых находятся в множестве K, такое, что каждое t -подмножество различных элементов X содержится ровно в λ блоках. Если K — набор натуральных чисел строго между t и v , то tBD является собственным . Если все k -подмножества X для некоторого k являются блоками, tBD является тривиальной конструкцией . ^[27]

Обратите внимание, что в следующем примере схемы 3-{12,{4,6},1), основанной на наборе X = {1,2,...,12}, некоторые пары появляются четыре раза (например, 1, 2) а другие появляются пять раз (например, 6,12). ^[28]

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

Матрицы взвешивания . Обобщение матриц Адамара, допускающее нулевые записи, используются в некоторых комбинаторных конструкциях. В частности, план экспериментов для оценки индивидуального веса нескольких объектов за несколько испытаний. ^[29]
Квадрат Юдена — это прямоугольный массив k × v ( k < v ) символов v , такой, что каждый символ появляется ровно один раз в каждой строке, а символы, появляющиеся в любом столбце, образуют блок симметричной ( v , k , λ ) конструкции, все блоки которого происходят таким образом. Квадрат Юдена – это латинский прямоугольник. Термин «квадрат» в названии происходит от более старого определения, в котором использовался квадратный массив. ^[30] Пример квадрата Юдена 4 × 7:

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

Смотрите также

Примечания

^ Стинсон 2003, стр.1
^ Хаяси, Такао (2008). «Магические квадраты в индийской математике». Энциклопедия истории науки, технологий и медицины в незападных культурах (2-е изд.). Спрингер. стр. 1252–1259. дои : 10.1007/978-1-4020-4425-0_9778. ISBN 978-1-4020-4559-2.
^ Стинсон 2003, стр. IX
^ Бет, Юнгникель и Ленц 1986, стр. 40 Пример 5.8
^ Райзер 1963, стр. 52, Теорема 3.1.
^ Когда группа G является абелевой группой (или записанной аддитивно), определяющее свойство выглядит как d ₁ –d ₂ , из которого происходит набор терминов разностей .
^ Бет, Юнгникель и Ленц 1986, стр. 262, Теорема 1.6.
^ Стинсон 2003, стр. 74, Теорема 4.5.
^ Стинсон 2003, стр. 193, Теорема 8.20.
^ Стинсон 2003, стр. 183, Теорема 8.5.
^ Колборн и Диниц 2007, стр. 331, Пример 2.2
^ Колборн и Диниц 2007, стр. 331, замечание 2.8.
^ Колборн и Диниц 2007, стр. 333, замечание 3.3.
^ Колборн и Диниц 2007, стр. 496, Теорема 28.5.
^ Колборн и Диниц 2007, стр. 497, Теорема 28.15.
^ Колборн и Диниц 2007, стр. 503, замечание 29.38.
^ Колборн и Диниц 2007, стр. 512, Пример 32.4
^ Колборн и Диниц 2007, стр. 512, замечание 32.3.
^ Колборн и Диниц 2007, стр. 530, Теорема 35.15.
^ Колборн и Диниц 2007, стр. 577, Теорема 47.15.
^ Колборн и Диниц 2007, стр. 578-579.
^ Колборн и Диниц 2007, стр. 579, Теорема 48.10.
^ Колборн и Диниц 2007, стр. 580, Лемма 48.22.
^ Колборн и Диниц 2007, стр. 652, Примеры 62.4
^ Колборн и Диниц 2007, стр. 655, Теорема 62.24.
^ Колборн и Диниц 2007, стр. 657, замечание 62.29.
^ Колборн и Диниц 2007, стр. 657
^ Колборн и Диниц 2007, стр. 658, Пример 63.5
^ Рагхаварао и Пэджетт 1988, стр. 305-308
^ Колборн и Диниц 2007, стр. 669, замечание 65.3.