Combinatorial design

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.[1]

Example

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 q2 + 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.

When such a structure does exist, it is called a finite projective plane; thus showing how finite geometry and combinatorics intersect. When q = 2, the projective plane is called the Fano plane.

History

Combinatorial designs date to antiquity, with the Lo Shu Square being an early magic square. They 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).[2] Other combinatorial designs are related to or have been developed from the study of these fundamental ones.

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).
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 block design. 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.[6]
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.
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.[7] 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.
Fisher's inequality holds for PBDs:[8] For any non-trivial PBD, vb.
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, vb, with equality if and only if the PBD is a projective plane or a near-pencil.[9]

A wide assortment of 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:

  1. Each element appears R = ρ1 + 2ρ2 times altogether, with multiplicity one in exactly ρ1 blocks and multiplicity two in exactly ρ2 blocks.
  2. Every pair of distinct elements appears Λ times (counted with multiplicity); that is, if mvb is the multiplicity of the element v in block b, then for every pair of distinct elements v and w, .
For example, one of the only two nonisomorphic BTD(4,8;2,3,8;4,6)s (blocks are columns) is:[10]
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
The incidence matrix of a BTD (where the entries are the multiplicities of the elements in the blocks) can be used to form a ternary error-correcting code analogous to the way binary codes are formed from the incidence matrices of BIBDs.[11]
  1. every element of V appears precisely once in each column, and
  2. every element of V appears at most twice in each row.
An example of a BTD(3) is given by
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
The columns of a BTD(n) provide a 1-factorization of the complete graph on 2n vertices, K2n.[12]
BTD(n)s can be used to schedule round-robin tournaments: the rows represent the locations, the columns the rounds of play and the entries are the competing players or teams.
A frequency square F1 of order n based on the set {s1,s2, ..., sm} with frequency vector (λ1, λ2, ...,λm) and a frequency square F2, also of order n, based on the set {t1,t2, ..., tk} with frequency vector (μ1, μ2, ...,μk) are orthogonal if every ordered pair (si, tj) appears precisely λiμj times when F1 and F2 are superimposed.
Any affine space AG(n,3) gives an example of an HTS. Such an HTS is an affine HTS. Nonaffine HTSs also exist.
The number of points of an HTS is 3m for some integer m  2. Nonaffine HTSs exist for any m  4 and do not exist for m = 2 or 3.[13]
Every Steiner triple system is equivalent to a Steiner quasigroup (idempotent, commutative and satisfying (xy)y = x for all x and y). A Hall triple system is equivalent to a Steiner quasigroup which is distributive, that is, satisfies a(xy) = (ax)(ay) for all a,x,y in the quasigroup.[14]
  1. Each cell of the array is either empty or contains an unordered pair from S,
  2. Each symbol occurs exactly once in each row and column of the array, and
  3. Every unordered pair of symbols occurs in at most one cell of the array.
An example of an H(4,6) is
0 4   1 3 2 5
2 3 1 4 0 5  
  3 5 2 4 0 1
1 5 0 2   3 4
An H(2n  1, 2n) is a Room square of side 2n  1, and thus the Howell designs generalize the concept of Room squares.
The pairs of symbols in the cells of a Howell design can be thought of as the edges of an s regular graph on 2n vertices, called the underlying graph of the Howell design.
Cyclic Howell designs are used as Howell movements in duplicate bridge tournaments. The rows of the design represent the rounds, the columns represent the boards, and the diagonals represent the tables.[15]
{1,2,3,4,7}       {1,2,5,6,7}       {3,4,5,6,7}.
Lotto designs model any lottery that is run in the following way: Individuals purchase tickets consisting of k numbers chosen from a set of n numbers. At a certain point the sale of tickets is stopped and a set of p numbers is randomly selected from the n numbers. These are the winning numbers. If any sold ticket contains t or more of the winning numbers, a prize is given to the ticket holder. Larger prizes go to tickets with more matches. The value of L(n,k,p,t) is of interest to both gamblers and researchers, as this is the smallest number of tickets that are needed to be purchased in order to guarantee a prize.
The Hungarian Lottery is a (90,5,5,t)-lotto design and it is known that L(90,5,5,2) = 100. Lotteries with parameters (49,6,6,t) are also popular worldwide and it is known that L(49,6,6,2) = 19. In general though, these numbers are hard to calculate and remain unknown.[17]
A geometric construction of one such design is given in Transylvanian lottery.
(0,1,2)     (1,0,3)     (2,1,3)     (0,2,3)
Any triple system can be made into a Mendelson triple system by replacing the unordered triple {a,b,c} with the pair of ordered triples (a,b,c) and (a,c,b), but as the example shows, the converse of this statement is not true.
If (Q,∗) is an idempotent semisymmetric quasigroup, that is, xx = x (idempotent) and x ∗ (yx) = y (semisymmetric) for all x, y in Q, let β = {(x,y,xy): x, y in Q}. Then (Q, β) is a Mendelsohn triple system MTS(|Q|,1). This construction is reversible.[18]
Every quasisymmetric block design gives rise to a strongly regular graph (as its block graph), but not all SRGs arise in this way.[21]
The incidence matrix of a quasisymmetric 2-(v,k,λ) design with kxy (mod 2) generates a binary self-orthogonal code (when bordered if k is odd).[22]
of total degree at most t is equal to the average value of f on the whole sphere, i.e., the integral of f divided by the area of the sphere.
  1. each row is a permutation of the n symbols and
  2. 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.
If r = n and k = 1 these are referred to as Tuscan squares, while if r = n and k = n - 1 they are Florentine squares. A Roman square is a tuscan square which is also a latin square (these are also known as row complete latin squares). A Vatican square is a florentine square which is also a latin square.
The following example is a tuscan-1 square on 7 symbols which is not tuscan-2:[23]
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
A tuscan square on n symbols is equivalent to a decomposition of the complete graph with n vertices into n hamiltonian directed paths.[24]
In a sequence of visual impressions, one flash card may have some effect on the impression given by the next. This bias can be cancelled by using n sequences corresponding to the rows of an n × n tuscan-1 square.[25]
Notice that in the following example of a 3-{12,{4,6},1) design based on the set X = {1,2,...,12}, some pairs appear four times (such as 1,2) while others appear five times (6,12 for instance).[27]
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
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
The seven blocks (columns) form the order 2 biplane (a symmetric (7,4,2)-design).

See also

Notes

  1. Stinson 2003, pg.1
  2. Stinson 2003, pg. IX
  3. Beth, Jungnickel & Lenz 1986, pg. 40 Example 5.8
  4. Ryser 1963, pg. 52, Theorem 3.1
  5. When the group G is an abelian group (or written additively) the defining property looks like d1 –d2 from which the term difference set comes from.
  6. Beth, Jungnickel & Lenz 1986, pg. 262, Theorem 1.6
  7. Stinson 2003, pg. 74, Theorem 4.5
  8. Stinson 2003, pg. 193, Theorem 8.20
  9. Stinson 2003, pg. 183, Theorem 8.5
  10. Colbourn & Dinitz 2007, pg. 331, Example 2.2
  11. Colbourn & Dinitz 2007, pg. 331, Remark 2.8
  12. Colbourn & Dinitz 2007, pg. 333, Remark 3.3
  13. Colbourn & Dinitz 2007, pg. 496, Theorem 28.5
  14. Colbourn & Dinitz 2007, pg. 497, Theorem 28.15
  15. Colbourn & Dinitz 2007, pg. 503, Remark 29.38
  16. Colbourn & Dinitz 2007, pg. 512, Example 32.4
  17. Colbourn & Dinitz 2007, pg. 512, Remark 32.3
  18. Colbourn & Dinitz 2007, pg. 530, Theorem 35.15
  19. Colbourn & Dinitz 2007, pg. 577, Theorem 47.15
  20. Colbourn & Dinitz 2007, pp. 578-579
  21. Colbourn & Dinitz 2007, pg. 579, Theorem 48.10
  22. Colbourn & Dinitz 2007, pg. 580, Lemma 48.22
  23. Colbourn & Dinitz 2007, pg. 652, Examples 62.4
  24. Colbourn & Dinitz 2007, pg. 655, Theorem 62.24
  25. Colbourn & Dinitz 2007, pg. 657, Remark 62.29
  26. Colbourn & Dinitz 2007, pg. 657
  27. Colbourn & Dinitz 2007, pg. 658, Example 63.5
  28. Colbourn & Dinitz 2007, pg. 669, Remark 65.3

References

  • 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. 
  • 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.

External links

This article is issued from Wikipedia - version of the 5/29/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.