Combinatorial design theory is the part of
combinatorialCombinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
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.
Combinatorial design theory is the part of
combinatorialCombinatorics is a branch of pure mathematics concerning the study of discrete objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics...
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
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, we have a
projective planeIn mathematics, a projective plane has two possible definitions, one of them coming from linear algebra, and another coming from axiomatic and finite geometry. The first definition quickly produces planes that are homogeneous spaces for some of the classical groups, including the real projective...
:
X is the point set of the plane and the blocks are the lines.
A
spherical designA 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 A spherical...
is a finite set
X of points in a (
d − 1)-dimensional
sphereA 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
- f(x1, ..., xd)
of total degree at most
t is equal to the average value of
f on the whole sphere, i.e., the
integralIntegration is an important concept in mathematics which, together with differentiation, forms one of the main operations in calculus. Given a function ƒ of a real variable x and an interval [a, b] of the real line, the definite integralis defined informally...
of
f divided by the area of the sphere.
Combinatorial design theory is applied to the
design of experimentsDesign of experiments, or experimental design, is the design of all information-gathering exercises where variation is present, whether under the full control of the experimenter or not...
. Some of the basic theory of combinatorial designs originated in
Ronald FisherSir Ronald Aylmer Fisher, FRS was an English statistician, evolutionary biologist, eugenicist and geneticist. He was described by Anders Hald as "a genius who almost single-handedly created the foundations for modern statistical science," and Richard Dawkins described him as "the greatest of...
'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 powerIn 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, 15 and 36 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 fieldIn abstract algebra, a finite field or Galois field is a field that contains only finitely many elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...
s and an application of
quadratic formIn mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. For example,is a quadratic form in the variables x and y....
s.
When such a structure does exist, it is called a finite
projective planeIn mathematics, a projective plane has two possible definitions, one of them coming from linear algebra, and another coming from axiomatic and finite geometry. The first definition quickly produces planes that are homogeneous spaces for some of the classical groups, including the real projective...
; thus showing how
finite geometryA 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 precisely the same number of 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, 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.
External links
- Design DB: A comprehensive database of combinatorial, statistical, experimental block designs
See also
- Algebraic statistics
Algebraic statistics is the use of algebra to advance statistics. Algebra has been useful for experimental design, parameter estimation, and hypothesis testing....
- Association scheme
In mathematics, association schemes are structures that appear in many different forms in the fields of combinatorics and statistics. Their theory is one of the branches of algebraic combinatorics.-Definition:...
- Fisher's inequality
In 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 problem
Kirkman'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...
- Room square
A 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...
- 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 A spherical...