Combinatorial design
Encyclopedia
Combinatorial design theory is the part of combinatorial
mathematics
that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties.
For instance, a balanced incomplete block design (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 any two blocks have the same number λ of common elements. For example, if λ = 1 and b = v, we have a projective plane
: X is the point set of the plane and the blocks are the lines.
A spherical design
is a finite set X of points in a (d − 1)-dimensional sphere
such that, for some integer t, the average value on X of every polynomial
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.
Combinatorial design theory is applied to the design of experiments
. Some of the basic theory of combinatorial designs originated in Ronald Fisher
's work on design of experiments.
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 field
s and an application of quadratic form
s.
When such a structure does exist, it is called a finite projective plane
; thus showing how finite geometry
and combinatorics intersect.
Often associated with Paul Erdős
, who did the pioneer work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms
in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics.
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties.
For instance, a balanced incomplete block design (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 any two blocks have the same number λ of common elements. For example, if λ = 1 and b = v, we have a projective plane
Projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
: X is the point set of the plane and the blocks are the lines.
A spherical design
Spherical design
A spherical design, part of combinatorial design theory in mathematics, is a finite set of N points on the d-dimensional unit hypersphere Sd such that the average value of any polynomial f of degree t or less on the set equals the average value of f on the whole sphere...
is a finite set X of points in a (d − 1)-dimensional sphere
Sphere
A sphere is a perfectly round geometrical object in three-dimensional space, such as the shape of a round ball. Like a circle in two dimensions, a perfect sphere is completely symmetrical around its center, with all points on the surface lying the same distance r from the center point...
such that, for some integer t, the average value on X of every polynomial
of total degree at most t is equal to the average value of f on the whole sphere, i.e., the integral
Integral
Integration is an important concept in mathematics and, together with its inverse, differentiation, is one of the two main operations in calculus...
of f divided by the area of the sphere.
Combinatorial design theory is applied to the design of experiments
Design of experiments
In general usage, design of experiments or experimental design is the design of any information-gathering exercises where variation is present, whether under the full control of the experimenter or not. However, in statistics, these terms are usually used for controlled experiments...
. Some of the basic theory of combinatorial designs originated in Ronald Fisher
Ronald Fisher
Sir Ronald Aylmer Fisher FRS was an English statistician, evolutionary biologist, eugenicist and geneticist. Among other things, Fisher is well known for his contributions to statistics by creating Fisher's exact test and Fisher's equation...
's work on design of experiments.
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
Prime power
In mathematics, a prime power is a positive integer power of a prime number.For example: 5=51, 9=32 and 16=24 are prime powers, while6=2×3, 15=3×5 and 36=62=22×32 are not...
. 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 field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s and an application of quadratic form
Quadratic form
In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. For example,4x^2 + 2xy - 3y^2\,\!is a quadratic form in the variables x and y....
s.
When such a structure does exist, it is called a finite projective plane
Projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
; thus showing how finite geometry
Finite geometry
A finite geometry is any geometric system that has only a finite number of points.Euclidean geometry, for example, is not finite, because a Euclidean line contains infinitely many points, in fact as many points as there are real numbers...
and combinatorics intersect.
Probabilistic combinatorics
In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph. For instance, what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0. This approach proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.Often associated with Paul Erdős
Paul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
, who did the pioneer work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms
Analysis of algorithms
To analyze an algorithm is to determine the amount of resources necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length...
in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics.
See also
- Algebraic statisticsAlgebraic statisticsAlgebraic statistics is the use of algebra to advance statistics. Algebra has been useful for experimental design, parameter estimation, and hypothesis testing....
- Association schemeAssociation schemeThe theory of association schemes arose in statistics, in the theory of experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. Indeed, in algebraic combinatorics, association schemes provide a unified approach to many topics,...
- Fisher's inequalityFisher's inequalityIn combinatorial mathematics, Fisher's inequality, named after Ronald Fisher, is a necessary condition for the existence of a balanced incomplete block design satisfying certain prescribed conditions....
- Kirkman's schoolgirl problemKirkman's schoolgirl problemKirkman's schoolgirl problem is a problem in combinatorics proposed by Thomas Kirkman in 1850 as Query VI in The Lady's and Gentleman's Diary...
- Latin squareLatin squareIn combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column...
- Latin rectangleLatin rectangleIn combinatorial mathematics, a Latin rectangle is an r × n matrix that has the numbers 1, 2, 3, ..., n as its entries with no number occurring more than once in any row or column where r ≤ n. An n × n Latin rectangle is called a...
- Room squareRoom squareA Room square, named after Thomas Gerald Room, is an n × n array filled with n + 1 different symbols in such a way that:# Each cell of the array is either empty or contains an unordered pair from the set of symbols...
External links
- Design DB: A comprehensive database of combinatorial, statistical, experimental block designs