Combinatorial design

Введение

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

Пример

Если у нас есть определенное число людей, можно ли распределить их на множества, так что каждый человек входит в по крайней мере один набор, каждая пара людей входит в один набор вместе, каждые две группы имеют точно одного человека, и ни одна группа не содержит всех, кроме одного человека, или только одного человека? Ответ зависит от n. Это имеет решение только в том случае, если n имеет форму q2 + q + 1. Менее просто доказать, что решение существует, если q является простой степенью. Предполагается, что это единственные решения. Далее было показано, что если для q существует решение, соответствующее 1 или 2 модус 4, то q является суммой двух квадратных чисел. Этот последний результат, теорема Брукка-Райзера, доказывается комбинацией конструктивных методов, основанных на конечных полях и применении квадратных форм. Когда такая структура существует, она называется конечной проективной плоскостью; таким образом, показывает, как пересекаются конечная геометрия и комбинаторика. Когда q = 2, проективная плоскость называется плоскостью Фано.

История

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

Основные комбинаторные конструкции

Классическое ядро предмета комбинаторных конструкций построено вокруг сбалансированных неполных блок-конструкций (BIBD), матриц Хадамарда и конструкций Хадамарда, симметричных BIBD, латинских квадратов, разрешимых BIBD, множеств различий и парно сбалансированных конструкций (PBD). Другие комбинаторные конструкции связаны с этими фундаментальными или были разработаны на основе их изучения. Сбалансированный неполный блок-дизайн или BIBD (обычно называемый кратко блок-дизайн) представляет собой коллекцию B из b подмножеств (называемых блоками) конечного множества X из v элементов, таким образом, что любой элемент X содержится в одном и том же числе r блоков, каждый блок имеет одинаковое количество k элементов, и каждая пара различных элементов появляется вместе в одном и том же числе λ блоков. BIBD также известны как 2 дизайна и часто обозначаются как 2 (v,k,λ) дизайна. Например, когда λ = 1 и b = v, у нас есть проективная плоскость: X - это множество точек плоскости, а блоки - это линии. Симметрично сбалансированная неполная конструкция блока или SBIBD - BIBD, в которой v = b (число точек равно количеству блоков). Они являются единственным наиболее важным и хорошо изученным подклассом BIBD. Проективные самолеты, бипланы и конструкции Hadamard 2 все являются SBIBD. Они представляют особый интерес, поскольку являются крайними примерами неравенства Фишера (b ≥ v). Разрешимый BIBD - это BIBD, блоки которого могут быть разделены на множества (называемые параллельными классами), каждый из которых образует разделы набора точек BIBD. Набор параллельных классов называется разрешением конструкции. Решение известной проблемы 15 школьниц - это решение BIBD с v = 15, k = 3 и λ = 1. Латинский прямоугольник - это матрица r × n, в которой в качестве входов имеются числа 1, 2, 3, , n (или любой другой набор из n различных символов), при этом ни одно число не встречается более одного раза в любом ряду или столбце, где r ≤ n. Латинский прямоугольник n × n называется латинским квадратом. Если r < n, то можно приложить n − r строк к латинскому прямоугольнику r × n, чтобы сформировать латинский квадрат, используя теорему о браке Холла. Два латинских квадрата порядка n называются ортогональными, если множество всех упорядоченных пар, состоящих из соответствующих записей в двух квадратах, имеет n2 различных членов (все возможные упорядоченные пары встречаются). Набор латинских квадратов одного и того же порядка образует набор взаимно ортогональных латинских квадратов (MOLS), если каждая пара латинских квадратов в наборе является ортогональной. В наборе МОЛ порядка n может быть не более n − 1 квадратов. Набор n − 1 МОЛ порядка n может быть использован для построения проективной плоскости порядка n (и наоборот). Множество различий (v, k, λ) представляет собой подмножество D группы G, такое, что порядок G равен v, размер D равен k, и каждый элемент неидентичности G может быть выражен как произведение d1d2−1 элементов D точно по λ способам (когда G записывается с помощью умножающей операции). Если D - множество различий, а g в G, то g D = {gd: d в D} также является множеством различий, и называется транслятом D. Совокупность всех транслятов множества различий D образует симметричную BIBD. В такой конструкции есть v элементов и v блоков. Каждый блок конструкции состоит из k точек, каждая точка содержится в k блоках. Любые два блока имеют точно λ элементов общего и любые две точки появляются вместе в λ блоках. Этот SBIBD называется развитием D. В частности, если λ = 1, то множество различий дает начало проективной плоскости. Примером множества различий (7,3,1) в группе (абелева группа, написанная адитивно) является подмножество {1,2,4}. Развитие этого множества различий дает плоскость Фано. Поскольку каждый набор различий дает SBIBD, набор параметров должен удовлетворять теореме БрукРайзерЧоула, но не каждый SBIBD дает набор различий. Матрица Хадамарда порядка m представляет собой матрицу H m, входящие в неё величины ±1, так что HH = mIm, где H является транспозицией H, а Im - матрицей тождества m × m. Матрицу Хадамарда можно преобразовать в стандартизированную форму (то есть преобразовать в эквивалентную матрицу Хадамарда), где в первом ряду и первом столбце все значения равны +1. Если порядок m > 2, то m должно быть кратным 4. При матрице Адамарда порядка 4a в стандартизированной форме, удалите первый ряд и первую колонку и преобразуйте каждый -1 в 0. Полученная матрица 01 M является матрицей частоты возникновения симметричной 2 − (4a − 1, 2a − 1, a − 1) конструкции, называемо...

The classical core of the subject of combinatorial designs is built around balanced incomplete block designs (BIBDs), Hadamard matrices and Hadamard designs, symmetric BIBDs, Latin squares, resolvable BIBDs, difference sets, and pairwise balanced designs (PBDs). Other combinatorial designs are related to or have been developed from the study of these fundamental ones. A balanced incomplete block design or BIBD (usually called for short a block design) is a collection B of b subsets (called blocks) of a finite set X of v elements, such that any element of X is contained in the same number r of blocks, every block has the same number k of elements, and each pair of distinct elements appear together in the same number λ of blocks. BIBDs are also known as 2 designs and are often denoted as 2 (v,k,λ) designs. As an example, when λ = 1 and b = v, we have a projective plane: X is the point set of the plane and the blocks are the lines. A symmetric balanced incomplete block design or SBIBD is a BIBD in which v = b (the number of points equals the number of blocks). They are the single most important and well studied subclass of BIBDs. Projective planes, biplanes and Hadamard 2 designs are all SBIBDs. They are of particular interest since they are the extremal examples of Fisher's inequality (b ≥ v). A resolvable BIBD is a BIBD whose blocks can be partitioned into sets (called parallel classes), each of which forms a partition of the point set of the BIBD. The set of parallel classes is called a resolution of the design. A solution of the famous 15 schoolgirl problem is a resolution of a BIBD with v = 15, k = 3 and λ = 1. A Latin rectangle is an r × n matrix that has the numbers 1, 2, 3, , n as its entries (or any other set of n distinct symbols) with no number occurring more than once in any row or column where r ≤ n. An n × n Latin rectangle is called a Latin square. If r < n, then it is possible to append n − r rows to an r × n Latin rectangle to form a Latin square, using Hall's marriage theorem. Two Latin squares of order n are said to be orthogonal if the set of all ordered pairs consisting of the corresponding entries in the two squares has n2 distinct members (all possible ordered pairs occur). A set of Latin squares of the same order forms a set of mutually orthogonal Latin squares (MOLS) if every pair of Latin squares in the set are orthogonal. There can be at most n − 1 squares in a set of MOLS of order n. A set of n − 1 MOLS of order n can be used to construct a projective plane of order n (and conversely). A (v, k, λ) difference set is a subset D of a group G such that the order of G is v, the size of D is k, and every nonidentity element of G can be expressed as a product d1d2−1 of elements of D in exactly λ ways (when G is written with a multiplicative operation). If D is a difference set, and g in G, then g D = {gd: d in D} is also a difference set, and is called a translate of D. The set of all translates of a difference set D forms a symmetric BIBD. In such a design there are v elements and v blocks. Each block of the design consists of k points, each point is contained in k blocks. Any two blocks have exactly λ elements in common and any two points appear together in λ blocks. This SBIBD is called the development of D.

In particular, if λ = 1, then the difference set gives rise to a projective plane. An example of a (7,3,1) difference set in the group (an abelian group written additively) is the subset {1,2,4}. The development of this difference set gives the Fano plane. Since every difference set gives an SBIBD, the parameter set must satisfy the Bruck–Ryser–Chowla theorem, but not every SBIBD gives a difference set. An Hadamard matrix of order m is an m × m matrix H whose entries are ±1 such that HH⊤ = mIm, where H⊤ is the transpose of H and Im is the m × m identity matrix. An Hadamard matrix can be put into standardized form (that is, converted to an equivalent Hadamard matrix) where the first row and first column entries are all +1. If the order m > 2 then m must be a multiple of 4. Given an Hadamard matrix of order 4a in standardized form, remove the first row and first column and convert every −1 to a 0. The resulting 0–1 matrix M is the incidence matrix of a symmetric 2 − (4a − 1, 2a − 1, a − 1) design called an Hadamard 2 design. This construction is reversible, and the incidence matrix of a symmetric 2 design with these parameters can be used to form an Hadamard matrix of order 4a. When a = 2 we obtain the, by now familiar, Fano plane as an Hadamard 2 design. A pairwise balanced design (or PBD) is a set X together with a family of subsets of X (which need not have the same size and may contain repeats) such that every pair of distinct elements of X is contained in exactly λ (a positive integer) subsets. The set X is allowed to be one of the subsets, and if all the subsets are copies of X, the PBD is called trivial. The size of X is v and the number of subsets in the family (counted with multiplicity) is b.

Fisher's inequality holds for PBDs: For any non trivial PBD, v ≤ b. This result also generalizes the famous Erdős–De Bruijn theorem: For a PBD with λ = 1 having no blocks of size 1 or size v, v ≤ b, with equality if and only if the PBD is a projective plane or a near pencil.