Симметричное расположение конечных множеств
Комбинаторная теория дизайна является частью комбинаторного математика, которая имеет дело с существованием, построением и свойствами систем конечных множеств, расположение которых удовлетворяет обобщенным концепциям баланса и / или симметрии. Эти концепции не уточняются, чтобы можно было рассматривать широкий спектр объектов как находящиеся под одним зонтом. Иногда это может включать числовые размеры множественных пересечений, как в блочных схемах, в то время как в других случаях это может включать пространственное расположение записей в массиве, как в решетки судоку.
Комбинаторная теория проектирования может быть применен к области дизайна экспериментов. Некоторые из основных теорий комбинаторных планов возникли в работе статистика Рональда Фишера по планированию биологических экспериментов. Современные приложения также можно найти в широком диапазоне областей, включая конечную геометрию, планирование турниров, лотереи, математическую химию, математическая биология, разработка и анализ алгоритмов, создание сетей, групповое тестирование и криптография.
Содержание
- 1 Пример
- 2 История
- 3 Фундаментальные комбинаторные планы
- 4 Другие комбинаторные планы
- 5 См. Также
- 6 Примечания
- 7 Ссылки
Пример
Плоскость Фано Учитывая определенное количество людей n, можно ли распределить их по наборам так, чтобы каждый человек был хотя бы в одном наборе, каждая пара людей вместе составляла ровно один набор, каждые два набора имели ровно одного общего человека, и ни один набор не содержал все, все, кроме одного человека, или ровно один человек? Ответ зависит от n.
Это имеет решение, только если n имеет вид q + q + 1. Менее просто доказать, что решение существует, если q является степенью простого числа. Предполагается, что это единственные решения. Далее было показано, что если существует решение для q, конгруэнтного 1 или 2 mod 4, то q является суммой двух квадратных чисел. Этот последний результат, теорема Брука – Райзера, доказывается комбинацией конструктивных методов, основанных на конечных полях и применении квадратичных форм.
Когда такая структура существует, она называется конечной проективной плоскостью ; таким образом показывая, как пересекаются конечная геометрия и комбинаторика. Когда q = 2, проективная плоскость называется плоскостью Фано.
История
Комбинаторные конструкции восходят к древности, а Квадрат Ло Шу является ранней магией. квадрат. Одно из самых ранних датируемых приложений комбинаторного дизайна можно найти в Индии в книге Варахамихиры «Брихат Самхита», написанной около 587 г. н.э., с целью создания духов с использованием 4 веществ, выбранных из 16 различных веществ, с использованием магического квадрата.
Комбинаторные конструкции развивались вместе с общим развитием комбинаторики с 18 века, например с латинскими квадратами в 18 веке и системами Штейнера в 19 веке.. Дизайн также был популярен в развлекательной математике, такой как задача школьницы Киркмана (1850), и в практических задачах, таких как планирование круговых турниров (решение опубликовано в 1880-х гг.). В 20-м веке схемы применялись к плану экспериментов, особенно к латинским квадратам, конечной геометрии и схемам ассоциаций, в результате чего получилась область алгебраических статистика.
Фундаментальные комбинаторные планы
Классическое ядро предмета комбинаторных планов строится вокруг сбалансированных неполных блочных планов (BIBD), матриц Адамара и планов Адамара, симметричные BIBD, латинские квадраты, разрешаемые BIBD, разностные наборы и попарно сбалансированные планы (PBD). Другие комбинаторные планы связаны с этими фундаментальными или были разработаны на их основе.
- A сбалансированная неполная блочная конструкция или BIBD (обычно называемая для краткости блочная конструкция ) представляет собой набор B из b подмножеств (называемых блоками) конечного набора X v элементов, таких, что любой элемент X содержится в одном и том же количестве блоков r, каждый блок имеет одинаковое количество элементов k, и каждая пара различных элементов появляется вместе в одном и том же количестве λ блоков. BIBD также известны как 2-конструкции и часто обозначаются как 2- (v, k, λ) конструкции. Например, когда λ = 1 и b = v, мы имеем проективную плоскость : X - это набор точек плоскости, а блоки - это прямые.
- A симметричная сбалансированная неполная конструкция блока или SBIBD - это BIBD, в котором v = b (количество точек равно количеству блоков). Они представляют собой наиболее важный и хорошо изученный подкласс BIBD. Проективные плоскости, бипланы и 2-схемы Адамара - все это SBIBD. Они представляют особый интерес, так как являются экстремальными примерами неравенства Фишера (b ≥ v).
- A разрешимый BIBD - это BIBD, блоки которого могут быть разбиты на множества (называемые параллельными классы), каждый из которых образует разбиение точечного множества BIBD. Множество параллельных классов называется разрешением проекта. Решение знаменитой 15 задачи школьницы - это решение BIBD с v = 15, k = 3 и λ = 1.
- A Латинский прямоугольник представляет собой r × n матрица, содержащая числа 1, 2, 3,..., n в качестве элементов (или любой другой набор из n различных символов), при этом ни одно число не встречается более одного раза в любой строке или столбце, где r ≤ n. Латинский прямоугольник размером n × n называется латинским квадратом. Если r < n, then it is possible to append n − r rows to an r × n Latin rectangle to form a Latin square, using Теорема Холла о браке.
- Два латинских квадрата порядка n называются ортогональными, если набор всех упорядоченных пар, состоящих из соответствующих элементов в двух квадратах, имеет n различных элементов (встречаются все возможные упорядоченные пары). Набор латинских квадратов одного порядка образует набор взаимно ортогональных латинских квадратов (MOLS), если каждая пара латинских квадратов в наборе ортогональна. В наборе МОЛП порядка n может быть не более n - 1 квадрата. Набор из n - 1 МОЛП порядка n может быть использован для построения проективной плоскости порядка n (и наоборот).
- A (v, k, λ) разница set - это подмножество Dиз группы G, так что order из G равен v, размер из D равен k, и каждый неидентификационный элемент G может быть выражен как произведение d 1d2элементов D точно в λ способами (когда G записывается с помощью мультипликативной операции).
- Если D - разностный набор, а g в G, то g D = {gd: d in D } также является набором различий и называется translate of D . Набор всех трансляций разностного набора D образует симметричную блочную конструкцию. В такой конструкции есть v элементов и v блоков. Каждый блок схемы состоит из k точек, каждая точка содержится в k блоках. Любые два блока имеют ровно λ общих элементов, и любые две точки входят вместе в λ блоков. Этот SBIBD называется развитием D.
- . В частности, если λ = 1, то разностный набор порождает проективную плоскость. Пример (7,3,1) разности, установленной в группе (абелева группа, записанная аддитивно) является подмножеством {1,2,4}. Развитие этого набора разностей дает плоскость Фано.
- Поскольку каждый набор разностей дает SBIBD, набор параметров должен удовлетворять теореме Брука – Райзера – Чоула, но не каждый SBIBD дает разницу
- Матрица Адамара порядка m - это матрица m × m H, элементы которой равны ± 1, такие что HH = m Im, где H - это транспонированная матрица H, а Im- единичная матрица размера 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.
- A попарно сбалансированная схема (или PBD) - это множество X вместе с семейством подмножеств X (которые не обязательно должны иметь одинаковый размер и могут содержать повторы), так что каждая пара различных элементов X содержится ровно в λ (положительное целое число) подмножеств. Множеству X разрешается быть одним из подмножеств, и если все подмножества являются копиями X, PBD называется тривиальным. Размер X равен v, а количество подмножеств в семействе (с учетом кратности) равно b.
- Неравенство Фишера выполняется для PBD: для любого нетривиального PBD v ≤ b.
- Этот результат также обобщает знаменитую теорему Эрдеша – Де Брейна : для PBD с λ = 1, не имеющего блоков размера 1 или размера v, v ≤ b, с равенством тогда и только тогда, когда PBD является проективная плоскость или почти карандаш.
Другие комбинаторные конструкции
Справочник по комбинаторным схемам (Colbourn Dinitz 2007) содержит, среди прочего, 65 глав, каждая из которых посвящена к комбинаторному плану, отличному от приведенного выше. Частичный список приведен ниже:
- Схемы ассоциации
- A сбалансированный тройной дизайн BTD (V, B; ρ 1, ρ 2, R; K, Λ) представляет собой расположение V элементов в B мультимножества (блоки), каждое из которых имеет мощность K (K ≤ V), удовлетворяющую:
- Каждый элемент появляется R = ρ 1 + 2ρ 2 раз вместе, с кратностью один ровно в ρ 1 блоках и кратностью два ровно в ρ 2 блоках.
- Каждая пара отдельных элементов появляется Λ раз (с учетом кратности); то есть, если m vb - кратность элемента v в блоке b, то для каждой пары отдельных элементов v и w .
- Например, один из двух неизоморфных BTD (4,8; 2,3,8; 4,6) s (блоки являются столбцами):
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.
- A схема сбалансированного турнира порядка n (BTD (n)) - это размещение всех различных неупорядоченных пар 2n-множества V в n × (2n - 1) массив такой, что
- каждый элемент V появляется ровно один раз в каждом столбце, а
- каждый элемент 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) s можно использовать для планирования круговых турниров : строки представляют местоположения, столбцы - раунды игры, а записи - это
- Бент-функции
- Массивы Костаса
- Факториальные планы
- A квадрат частот (F-квадрат) - это обобщение более высокого порядка для латинского квадрата. Пусть S = {s 1,s2,..., s m } будет набором различных символов и (λ 1, λ 2,..., λ m) частотный вектор положительных целых чисел. Частотный квадрат порядка n - это массив n × n, в котором каждый символ s i встречается λ i раз, i = 1,2,..., m, в каждой строке и столбец. Порядок n = λ 1 + λ 2 +... + λ m. F-квадрат имеет стандартную форму, если в первой строке и столбце все вхождения s i предшествуют s j всякий раз, когда i < j.
- квадрат частоты F 1 порядка n на основе набора {s 1,s2,..., s m } с вектором частоты (λ 1, λ 2,..., λ m) и частотный квадрат F 2, также порядка n, на основе набора {t 1,t2,..., t k } с частотным вектором (μ 1, μ 2,..., μ k) ортогональны, если каждая упорядоченная пара (s i, t j) появляется ровно λ iμjраз при наложении F 1 и F 2.
- тройные системы Холла (HTS) - это системы троек Штейнера (STS) (но блоки называются линиями) с тем свойством, что субструктура, порожденная двумя пересекающимися линиями, изоморфна конечной аффинной плоскости AG (2,3).
- Любое аффинное пространство AG (n, 3) дает пример HTS. Такая HTS является аффинной HTS. Также существуют неаффинные HTS.
- Количество точек HTS равно 3 для некоторого целого m ≥ 2. Неаффинные HTS существуют для любого m ≥ 4 и не существуют для m = 2 или 3.
- Каждая система троек Штейнера эквивалентна квазигруппе Штейнера (идемпотент, коммутативная и удовлетворяющая (xy) y = x для всех x и y). Система троек Холла эквивалентна квазигруппе Штейнера, которая дистрибутивна, то есть удовлетворяет a (xy) = (ax) (ay) для всех a, x, y в квазигруппе.
- Пусть S - набор из 2n элементов. Дизайн Хауэлла, H (s, 2n) (на наборе символов S) представляет собой массив s × s, такой что:
- Каждая ячейка массива либо пуста, либо содержит неупорядоченную пару из S,
- Каждый символ встречается ровно один раз в каждой строке и столбце массива, и
- Каждая неупорядоченная пара символов встречается не более чем в одной ячейке массива.
- Пример символа 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, и, таким образом, конструкции Хауэлла обобщают концепцию квадратов помещений.
- Пары символов в ячейках конструкции Хауэлла можно рассматривать как ребра регулярного графа. на 2n вершинах, называемых базовым графом схемы Хауэлла.
- Циклические конструкции Хауэлла используются в качестве движений Хауэлла в дублирующих турнирах по бриджу. Строки рисунка представляют собой раунды, столбцы представляют доски, а диагонали представляют таблицы.
- Линейные промежутки
- (n, k, p, t) -lotto design - это n-множество V элементов вместе с множеством β k-элементных подмножеств V (блоков), так что для любого p-подмножества P из V существует блок B в β, для которого | P ∩ B | ≥ т. 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}.
- Lotto моделирует любую лотерею, которая проводится следующим образом: люди покупают билеты, состоящие из k номеров, выбранных из набора из n чисел. В определенный момент продажа билетов останавливается, и из n чисел случайным образом выбирается набор из p номеров. Это выигрышные числа. Если какой-либо проданный билет содержит t или более выигрышных номеров, приз предоставляется держателю билета. Более крупные призы получают билеты с большим количеством матчей. Значение L (n, k, p, t) представляет интерес как для игроков, так и для исследователей, поскольку это наименьшее количество билетов, которое необходимо приобрести, чтобы гарантировать выигрыш.
- Венгерская лотерея - это a (90,5,5, t) -лотто дизайн и известно, что L (90,5,5,2) = 100. Лотереи с параметрами (49,6,6, t) также популярны во всем мире, и это известно, что L (49,6,6,2) = 19. В целом, эти числа трудно вычислить и они остаются неизвестными.
- Геометрическая конструкция одного из таких рисунков приведена в Трансильванской лотерее.
- Магические квадраты
- A (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, б), но, как показывает пример, обратное утверждение неверно.
- Если (Q, ∗) - идемпотентная полусимметричная квазигруппа, то есть x ∗ x = x (идемпотент) и x ∗ (y ∗ x) = y (полусимметричный) для всех x, y в Q, пусть β = {(x, y, x ∗ y): x, y в Q}. Тогда (Q, β) - тройная система Мендельсона MTS (| Q |, 1). Эта конструкция обратима.
- Ортогональные массивы
- A квази-3 схема - это симметричная конструкция (SBIBD), в которой каждая тройка блоков пересекается либо в точках x, либо в y, для фиксированных x и y, называемых тройным пересечением числа (x < y). Any symmetric design with λ ≤ 2 is a quasi-3 design with x = 0 and y = 1. The point-hyperplane design of PG(n, q) представляет собой схему квази-3 с x = (q - 1) / (q - 1) и y = λ = (q - 1) / (q - 1). Если y = λ для схемы квази-3, эта схема изоморфна плану PG (n, q) или проекционной плоскости.
- A t- (v, k, λ) плану. D квазисимметричный с числами пересечения x и y (x < y) if every two distinct blocks intersect in either x or y points. These designs naturally arise in the investigation of the duals of designs with λ = 1. A non-symmetric (b>v) 2- (v, k, 1) план квазисимметричен с x = 0 и y = 1. Множество (повторить все блоков определенное количество раз) симметричного 2- (v, k, λ) плана является квазисимметричным с x = λ и y = k. 3-схемы Адамара (расширения 2-планов Адамара ) являются квазисимметричный.
- Каждая квазисимметричная блочная конструкция порождает строго регулярный граф (как его блочный граф), но не все SRG возникают таким образом.
- Матрица инцидентности квазисимметричного 2- (v, k, λ) дизайна с k ≡ x ≡ y (mod 2) генерирует двоичный самоортогональный код (с рамкой, если k нечетное).
- Квадраты помещения
- A сферический дизайн - это конечное множество X точек в (d - 1) -мерной сфере таких, что для некоторого целого t среднее значение на X каждого многочлена
- общей степени не более t равно среднему значению f на всей сфере, то есть интеграл от f, деленного на площадь сферы.
- Системы Турана
- Прямоугольник r × n тосканский-k на n символах имеет r строк и n столбцов, таких что:
- каждая строка представляет собой перестановку n символов и
- для любых двух различных символов 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 гамильтоново направленных путей.
- В последовательности визуальных впечатлений одна флэш-карта может иметь некоторое влияние на впечатление, производимое следующей. Это смещение можно устранить, используя n последовательностей, соответствующих строкам квадрата n × n тосканского-1.
- A сбалансированный по t план (или t BD) типа t - (v, K, λ) является v-множеством X вместе с семейством подмножеств X (называемых блоками), размеры которых находятся в множестве K, так что каждое t-подмножество различных элементов X содержится ровно в λ блоках. Если 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
- A Квадрат Юдена представляет собой прямоугольный массив размером k × v (k < v) of v symbols such that each symbol appears exactly once in each row and the symbols appearing in any column form a block of a symmetric (v, k, λ) design, all the blocks of which occur in this manner. A Youden square is a Latin rectangle. The term "square" in the name comes from an older definition which did use a square array. An example of a 4 × 7 Youden square is given by:
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 (a симметричный (7,4,2) -конструкция).
См. также
Примечания
Ссылки