Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in block designs, while at other times it could involve the spatial arrangement of entries in an array as in sudoku grids.
Combinatorial design theory can be applied to the area of design of experiments. Some of the basic theory of combinatorial designs originated in the statistician Ronald Fisher's work on the design of biological experiments. Modern applications are also found in a wide gamut of areas including; Finite geometry, tournament scheduling, lotteries, mathematical biology, algorithm design and analysis, networking, group testing and cryptography.
Given a certain number n of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people is in exactly one set together, every two sets have exactly one person in common, and no set contains everyone, all but one person, or exactly one person? The answer depends on n.
This has a solution only if n has the form q + q + 1. It is less simple to prove that a solution exists if q is a prime power. It is conjectured that these are the only solutions. It has been further shown that if a solution exists for q congruent to 1 or 2 mod 4, then q is a sum of two square numbers. This last result, the Bruck–Ryser theorem, is proved by a combination of constructive methods based on finite fields and an application of quadratic forms.
Combinatorial designs date to antiquity, with the Lo Shu Square being an early magic square. One of the earliest datable application of combinatorial design is found in India in the book Brhat Samhita by Varahamihira, written around 587 AD, for the purpose of making perfumes using 4 substances selected from 16 different substances using a magic square. Combinatorial designs developed along with the general growth of combinatorics from the 18th century, for example with Latin squares in the 18th century and Steiner systems in the 19th century. Designs have also been popular in recreational mathematics, such as Kirkman's schoolgirl problem (1850), and in practical problems, such as the scheduling of round-robin tournaments (solution published 1880s). In the 20th century designs were applied to the design of experiments, notably Latin squares, finite geometry, and association schemes, yielding the field of algebraic statistics.
Fundamental combinatorial designs
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.
- 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 dd of elements of D in exactly λ ways (when G is written with a multiplicative operation).
- An Hadamard matrix of order m is an m × m matrix H whose entries are ±1 such that HH = mI, where H is the transpose of H and I 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.
- 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.
Other combinatorial designs
The Handbook of Combinatorial Designs (Colbourn & Dinitz 2007) has, amongst others, 65 chapters, each devoted to a combinatorial design other than those given above. A partial listing is given below:
- Each element appears R = ρ + 2ρ times altogether, with multiplicity one in exactly ρ blocks and multiplicity two in exactly ρ blocks.
- Every pair of distinct elements appears Λ times (counted with multiplicity); that is, if m is the multiplicity of the element v in block b, then for every pair of distinct elements v and w, .
- A balanced tournament design of order n (a BTD(n)) is an arrangement of all the distinct unordered pairs of a 2n-set V into an n × (2n − 1) array such that
- every element of V appears precisely once in each column, and
- every element of V appears at most twice in each row.
- Hall triple systems (HTSs) are Steiner triple systems (STSs) (but the blocks are called lines) with the property that the substructure generated by two intersecting lines is isomorphic to the finite affine plane AG(2,3).
- Let S be a set of 2n elements. A Howell design, H(s,2n) (on symbol set S) is an s × s array such that:
- Each cell of the array is either empty or contains an unordered pair from S,
- Each symbol occurs exactly once in each row and column of the array, and
- Every unordered pair of symbols occurs in at most one cell of the array.
- each row is a permutation of the n symbols and
- for any two distinct symbols a and b and for each m from 1 to k, there is at most one row in which b is m steps to the right of a.
- A t-wise balanced design (or t BD) of type t − (v,K,λ) is a v-set X together with a family of subsets of X (called blocks) whose sizes are in the set K, such that every t-subset of distinct elements of X is contained in exactly λ blocks. If K is a set of positive integers strictly between t and v, then the t BD is proper. If all the k-subsets of X for some k are blocks, the t BD is a trivial design.
- A Youden square is a k × v rectangular array (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:
- ^ Stinson 2003, pg.1
- ^ Hayashi, Takao (2008). Magic Squares in Indian Mathematics. Encyopaedia of the History of Science, Technology, and Medicine in Non-Western Cultures (2 ed.). Springer. pp. 1252–1259.
- ^ Stinson 2003, pg. IX
- ^ Beth, Jungnickel & Lenz 1986, pg. 40 Example 5.8
- ^ Ryser 1963, pg. 52, Theorem 3.1
- ^ When the group G is an abelian group (or written additively) the defining property looks like d –d from which the term difference set comes from.
- ^ Beth, Jungnickel & Lenz 1986, pg. 262, Theorem 1.6
- ^ Stinson 2003, pg. 74, Theorem 4.5
- ^ Stinson 2003, pg. 193, Theorem 8.20
- ^ Stinson 2003, pg. 183, Theorem 8.5
- ^ Colbourn & Dinitz 2007, pg. 331, Example 2.2
- ^ Colbourn & Dinitz 2007, pg. 331, Remark 2.8
- ^ Colbourn & Dinitz 2007, pg. 333, Remark 3.3
- ^ Colbourn & Dinitz 2007, pg. 496, Theorem 28.5
- ^ Colbourn & Dinitz 2007, pg. 497, Theorem 28.15
- ^ Colbourn & Dinitz 2007, pg. 503, Remark 29.38
- ^ Colbourn & Dinitz 2007, pg. 512, Example 32.4
- ^ Colbourn & Dinitz 2007, pg. 512, Remark 32.3
- ^ Colbourn & Dinitz 2007, pg. 530, Theorem 35.15
- ^ Colbourn & Dinitz 2007, pg. 577, Theorem 47.15
- ^ Colbourn & Dinitz 2007, pp. 578-579
- ^ Colbourn & Dinitz 2007, pg. 579, Theorem 48.10
- ^ Colbourn & Dinitz 2007, pg. 580, Lemma 48.22
- ^ Colbourn & Dinitz 2007, pg. 652, Examples 62.4
- ^ Colbourn & Dinitz 2007, pg. 655, Theorem 62.24
- ^ Colbourn & Dinitz 2007, pg. 657, Remark 62.29
- ^ Colbourn & Dinitz 2007, pg. 657
- ^ Colbourn & Dinitz 2007, pg. 658, Example 63.5
- ^ Colbourn & Dinitz 2007, pg. 669, Remark 65.3
- Assmus, E.F.; Key, J.D. (1992), Designs and Their Codes, Cambridge: Cambridge University Press, ISBN 0-521-41361-3
- Beth, Thomas; Jungnickel, Dieter; Lenz, Hanfried (1986), Design Theory, Cambridge: Cambridge University Press. 2nd ed. (1999) ISBN 978-0-521-44432-3.
- R. C. Bose, "A Note on Fisher's Inequality for Balanced Incomplete Block Designs", Annals of Mathematical Statistics, 1949, pages 619–620.
- Caliński, Tadeusz; Kageyama, Sanpei (2003). Block designs: A Randomization approach, Volume II: Design. Lecture Notes in Statistics. 170. New York: Springer-Verlag. ISBN 0-387-95470-8.
- Colbourn, Charles J.; Dinitz, Jeffrey H. (2007), Handbook of Combinatorial Designs (2nd ed.), Boca Raton: Chapman & Hall/ CRC, ISBN 1-58488-506-8
- R. A. Fisher, "An examination of the different possible solutions of a problem in incomplete blocks", Annals of Eugenics, volume 10, 1940, pages 52–75.
- Hall, Jr., Marshall (1986), Combinatorial Theory (2nd ed.), New York: Wiley-Interscience, ISBN 0-471-09138-3
- Hughes, D.R.; Piper, E.C. (1985), Design theory, Cambridge: Cambridge University Press, ISBN 0-521-25754-9
- Lander, E. S. (1983), Symmetric Designs: An Algebraic Approach, Cambridge: Cambridge University Press
- Lindner, C.C.; Rodger, C.A. (1997), Design Theory, Boca Raton: CRC Press, ISBN 0-8493-3986-3
- Raghavarao, Damaraju (1988). Constructions and Combinatorial Problems in Design of Experiments (corrected reprint of the 1971 Wiley ed.). New York: Dover.
- Raghavarao, Damaraju and Padgett, L.V. (2005). Block Designs: Analysis, Combinatorics and Applications. World Scientific.CS1 maint: Multiple names: authors list (link)
- Ryser, Herbert John (1963), "Chapter 8: Combinatorial Designs", Combinatorial Mathematics (Carus Monograph #14), Mathematical Association of America
- S. S. Shrikhande, and Vasanti N. Bhat-Nayak, Non-isomorphic solutions of some balanced incomplete block designs I – Journal of Combinatorial Theory, 1970
- Stinson, Douglas R. (2003), Combinatorial Designs: Constructions and Analysis, New York: Springer, ISBN 0-387-95487-2
- Street, Anne Penfold; Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0-19-853256-3.
- van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.