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

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

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

пример

В Самолет Фано

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

• А попарно сбалансированный дизайн (или PBD) - это набор Икс вместе с семейством подмножеств Икс (которые не обязательно должны иметь одинаковый размер и могут содержать повторы), так что каждая пара отдельных элементов Икс содержится ровно в λ (натуральных) подмножествах. Набор Икс может быть одним из подмножеств, и если все подмножества являются копиями Икс, PBD называется банальный. Размер Икс является v а количество подмножеств в семье (с учетом кратности) равно б.

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

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

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

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

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

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

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

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

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

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

Пример BTD (3) дается формулой

Столбцы БТД (п) обеспечить 1-факторизация полного графа на 2п вершины, K_2п.^[13]

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

• Бент функции
• Массивы Костаса
• Факторные дизайны
• А частотный квадрат (F-квадрат) является обобщением высшего порядка Латинский квадрат. Позволять S = {s₁,s₂, ..., s_м} набор различных символов и (λ₁, λ₂, ..., λ_м) а частотный вектор натуральных чисел. А частотный квадрат порядка п является п × п массив, в котором каждый символ s_я происходит λ_я раз, я = 1,2, ..., m в каждой строке и столбце. В порядок п = λ₁ + λ₂ + ... + λ_м. F-квадрат находится в стандартная форма если в первой строке и столбце все вхождения s_я предшествуют тем из s_j всякий раз, когда я < j.

Квадрат частоты F₁ порядка п на основе набора {s₁,s₂, ..., s_м} с частотным вектором (λ₁, λ₂, ...,λ_м) и частотный квадрат F₂, также по порядку п, на основе набора {т₁,т₂, ..., т_k} с частотным вектором (μ₁, μ₂, ...,μ_k) находятся ортогональный если каждая заказанная пара (s_я, т_j) появляется точно λ_яμ_j раз, когда F₁ и F₂ накладываются.

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

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

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

Каждая система троек Штейнера эквивалентна системе троек Штейнера. квазигруппа (идемпотент, коммутативный и сытно (ху)у = Икс для всех Икс и у). Система троек Холла эквивалентна квазигруппе Штейнера, которая является распределительный, то есть удовлетворяет а(ху) = (топор)(ай) для всех а,Икс,у в квазигруппе.^[15]

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

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

Пример ЧАС(4,6) - это

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

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

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

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

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

Лото дизайн модели любой лотерея который выполняется следующим образом: Покупка физическими лицами Билеты состоящий из k числа, выбранные из набора п числа. В определенный момент продажа билетов прекращается и набор п числа выбираются случайным образом из п числа. Эти выигрышные числа. Если какой-либо проданный билет содержит т или более выигрышных номеров, приз достается держателю билета. Более крупные призы получают билеты с большим количеством матчей. Значение L (п,k,п,т) представляет интерес как для игроков, так и для исследователей, поскольку это наименьшее количество билетов, которое необходимо приобрести, чтобы гарантировать выигрыш.

Венгерская лотерея - это (90,5,5,т) -лотто и известно, что L (90,5,5,2) = 100. Лотереи с параметрами (49,6,6,т) также популярны во всем мире, и известно, что L (49,6,6,2) = 19. Однако в целом эти числа трудно вычислить и они остаются неизвестными.^[18]

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

• Магические квадраты
• А (v,k,λ) -Дизайн Мендельсона, или MD (v,k,λ),это v-набор V и набор β упорядоченных k-наборы различных элементов V (называется блоки), такая, что каждая упорядоченная пара (Икс,у) с участием Икс ≠ у элементов V циклически смежна в λ блоки. Заказанная пара (Икс,у) различных элементов циклически смежный в блоке, если элементы отображаются в блоке как (...,Икс,у,...) или (у,...,Икс). Доктор медицины (v,3,λ) это Тройная система Мендельсона, МТС (v,λ). Примером MTS (4,1) на V = {0,1,2,3} является:

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

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

Если (Q, ∗) - идемпотентный полусимметричный квазигруппа, это, Икс ∗ Икс = Икс (идемпотентный) и Икс ∗ (у ∗ Икс) = у (полусимметричный) для всех Икс, у в Q, пусть β = {(Икс,у,Икс ∗ у): Икс, у в Q}. Потом (Q, β) - тройная система Мендельсона MTS (|Q|, 1). Эта конструкция обратима.^[19]

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

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

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

• Площадь комнат
• А сферический дизайн конечное множество Икс точек в (d - 1) -мерный сфера так что для некоторого целого т, среднее значение на Икс каждого полинома

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

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

• Системы Turán
• An р × п тосканскийk прямоугольник на п символы имеет р ряды и п столбцы такие, что:

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

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

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

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

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

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

Обратите внимание, что в следующем примере проекта 3- {12, {4,6}, 1) на основе набора Икс = {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

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

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

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

• Алгебраическая статистика
• Гиперграф
• Гипотеза Вильямсона

Заметки

использованная литература