Combinatorial design


Combinatorial design

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

f(x_1, \ldots, x_d)\

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.

Contents

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.

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.

See also

Bibliography

  • Caliński, Tadeusz and 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. 
  • 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. 
  • Street, Anne Penfold and Street, Deborah J. (1987). Combinatorics of Experimental Design. Oxford U. P. [Clarendon]. pp. 400+xiv. ISBN 0198532563. 
  • Stinson, Douglas R. (2003). Combinatorial Designs - Constructions and Analysis. Springer Verlag. ISBN 0387954872. 

External links

  • Design DB: A comprehensive database of combinatorial, statistical, experimental block designs

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Design theory — can refer to any theory relating to design in general. Design theory may also refer to: Engineering and industrial design C K theory Design science C K theory Mathematics Combinatorial design Block design Symmetric design Design of experiments… …   Wikipedia

  • Combinatorial chemistry — involves the rapid synthesis or the computer simulation of a large number of different but structurally related molecules or materials. It is especially common in CADD (Computer aided drug design) and can be done online with web based software,… …   Wikipedia

  • Design of experiments — In general usage, design of experiments (DOE) 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… …   Wikipedia

  • Combinatorial map — A combinatorial map is a combinatorial object modelling topological structures with subdivided objects. Historically, the concept was introduced informally by J. Edmonds for polyhedral surfaces [1] which are planar graphs. It was given its first… …   Wikipedia

  • Randomized block design — In the statistical theory of the design of experiments, blocking is the arranging of experimental units in groups (blocks) that are similar to one another. Typically, a blocking factor is a source of variability that is not of primary interest to …   Wikipedia

  • Spherical design — A spherical design, part of combinatorial design theory in mathematics, is a finite set of 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… …   Wikipedia

  • Block design — In combinatorial mathematics, a block design (more fully, a balanced incomplete block design) is a particular kind of set system, which has long standing applications to experimental design (an area of statistics) as well as purely combinatorial… …   Wikipedia

  • Journal of Combinatorial Theory — Le Journal of Combinatorial Theory, Series A[1] et Series B[2] est une revue mathématique se spécialisant en analyse combinatoire et autres questions associées ; elle est publiée par Elsevier Science. Series A est principalement consacrée… …   Wikipédia en Français

  • Symmetric design — In combinatorial mathematics, a symmetric design is a block design with equal numbers of points and blocks. Thus, it has the fewest possible blocks given the number of points (by Fisher s inequality).That is, a symmetric design is a ( v , b , r …   Wikipedia

  • Electronic design automation — (EDA) is the category of tools for designing and producing electronic systems ranging from printed circuit boards (PCBs) to integrated circuits. This is sometimes referred to as ECAD (electronic computer aided design) or just CAD. (Printed… …   Wikipedia