In
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, a block design is an
incidence structure
In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the Point (geometry), points and Line (geometry), lines of the Euclidean plane as t ...
consisting of a set together with a
family of subsets known as ''blocks'', chosen such that number of occurrences of each element satisfies certain conditions making the collection of blocks exhibit
symmetry
Symmetry () in everyday life refers to a sense of harmonious and beautiful proportion and balance. In mathematics, the term has a more precise definition and is usually used to refer to an object that is Invariant (mathematics), invariant und ...
(balance). Block designs have applications in many areas, including
experimental design
The design of experiments (DOE), also known as experiment design or experimental design, is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. ...
,
finite geometry
A finite geometry is any geometry, geometric system that has only a finite set, finite number of point (geometry), points.
The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based ...
,
physical chemistry
Physical chemistry is the study of macroscopic and microscopic phenomena in chemical systems in terms of the principles, practices, and concepts of physics such as motion, energy, force, time, thermodynamics, quantum chemistry, statistical mech ...
,
software testing
Software testing is the act of checking whether software satisfies expectations.
Software testing can provide objective, independent information about the Quality (business), quality of software and the risk of its failure to a User (computin ...
,
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, and
algebraic geometry
Algebraic geometry is a branch of mathematics which uses abstract algebraic techniques, mainly from commutative algebra, to solve geometry, geometrical problems. Classically, it studies zero of a function, zeros of multivariate polynomials; th ...
.
Without further specifications the term ''block design'' usually refers to a balanced incomplete block design (BIBD), specifically (and also synonymously) a 2-design, which has been the most intensely studied type historically due to its application in the
design of experiments
The design of experiments (DOE), also known as experiment design or experimental design, is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. ...
. Its generalization is known as a t-design.
Overview
A design is said to be ''balanced'' (up to ''t'') if all ''t''-subsets of the original set occur in equally many (i.e., ''λ'') blocks. When ''t'' is unspecified, it can usually be assumed to be 2, which means that each ''pair'' of elements is found in the same number of blocks and the design is ''pairwise balanced''. For ''t'' = 1, each element occurs in the same number of blocks (the ''replication number'', denoted ''r'') and the design is said to be ''regular''. A block design in which all the blocks have the same size (usually denoted ''k'') is called ''uniform'' or ''proper''. The designs discussed in this article are all uniform. Block designs that are not necessarily uniform have also been studied; for ''t'' = 2 they are known in the literature under the general name
pairwise balanced designs (PBDs). Any uniform design balanced up to ''t'' is also balanced in all lower values of ''t'' (though with different ''λ''-values), so for example a pairwise balanced (''t'' = 2) design is also regular (''t'' = 1). When the balancing requirement fails, a design may still be ''partially balanced'' if the ''t''-subsets can be divided into ''n'' classes, each with its own (different) ''λ''-value. For ''t'' = 2 these are known as PBIBD(''n'') designs, whose classes form an
association scheme
The theory of association schemes arose in statistics, in the theory of design of experiments, experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. In algebraic combinatori ...
.
Designs are usually said (or assumed) to be ''incomplete'', meaning that the collection of blocks is not all possible ''k''-subsets, thus ruling out a trivial design.
Block designs may or may not have repeated blocks. Designs without repeated blocks are called ''simple'', in which case the "family" of blocks is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
rather than a
multiset
In mathematics, a multiset (or bag, or mset) is a modification of the concept of a set that, unlike a set, allows for multiple instances for each of its elements. The number of instances given for each element is called the ''multiplicity'' of ...
.
In
statistics
Statistics (from German language, German: ', "description of a State (polity), state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a s ...
, the concept of a block design may be extended to ''non-binary'' block designs, in which blocks may contain multiple copies of an element (see
blocking (statistics)
In the statistical theory of the design of experiments, blocking is the arranging of experimental units that are similar to one another in groups (blocks) based on one or more variables. These variables are chosen carefully to minimize the effect ...
). There, a design in which each element occurs the same total number of times is called ''equireplicate,'' which implies a ''regular'' design only when the design is also binary. The incidence matrix of a non-binary design lists the number of times each element is repeated in each block.
Regular uniform designs (configurations)
The simplest type of "balanced" design (''t'' = 1) is known as a tactical configuration or 1-design. The corresponding
incidence structure
In mathematics, an incidence structure is an abstract system consisting of two types of objects and a single relationship between these types of objects. Consider the Point (geometry), points and Line (geometry), lines of the Euclidean plane as t ...
in
geometry
Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
is known simply as a configuration, see
Configuration (geometry)
In mathematics, specifically projective geometry, a configuration in the plane consists of a finite set of points, and a finite arrangement of lines, such that each point is incident to the same number of lines and each line is incident to the ...
. Such a design is uniform and regular: each block contains ''k'' elements and each element is contained in ''r'' blocks. The number of set elements ''v'' and the number of blocks ''b'' are related by
, which is the total number of element occurrences.
Every
binary matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in ...
with constant row and column sums is the
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
of a regular uniform block design. Also, each configuration has a corresponding
biregular bipartite graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
known as its incidence or
Levi graph
In combinatorial mathematics, a Levi graph or incidence graph is a bipartite graph associated with an incidence structure.. See in particulap. 181 From a collection of points and lines in an incidence geometry or a projective configuration, we ...
.
Pairwise balanced uniform designs (2-designs or BIBDs)
Given a finite set ''X'' (of elements called ''points'') and integers ''k'', ''r'', ''λ'' ≥ 1, we define a ''2-design'' (or ''BIBD'', standing for balanced incomplete block design) ''B'' to be a family of ''k''-element subsets of ''X'', called ''blocks'', such that any ''x'' in ''X'' is contained in ''r'' blocks, and any pair of distinct points ''x'' and ''y'' in ''X'' is contained in ''λ'' blocks. Here, the condition that any ''x'' in ''X'' is contained in ''r'' blocks is redundant, as shown below.
Here ''v'' (the number of elements of ''X'', called points), ''b'' (the number of blocks), ''k'', ''r'', and λ are the ''parameters'' of the design. (To avoid degenerate examples, it is also assumed that ''v'' > ''k'', so that no block contains all the elements of the set. This is the meaning of "incomplete" in the name of these designs.) In a table:
:
The design is called a (''v'', ''k'', ''λ'')-design or a (''v'', ''b'', ''r'', ''k'', ''λ'')-design. The parameters are not all independent; ''v'', ''k'', and λ determine ''b'' and ''r'', and not all combinations of ''v'', ''k'', and ''λ'' are possible. The two basic equations connecting these parameters are
:
obtained by counting the number of pairs (''B'', ''p'') where ''B'' is a block and ''p'' is a point in that block, and
:
obtained from counting for a fixed ''x'' the triples (''x'', ''y'', ''B'') where ''x'' and ''y'' are distinct points and ''B'' is a block that contains them both. This equation for every ''x'' also proves that ''r'' is constant (independent of ''x'') even without assuming it explicitly, thus proving that the condition that any ''x'' in ''X'' is contained in ''r'' blocks is redundant and ''r'' can be computed from the other parameters.
The resulting ''b'' and ''r'' must be integers, which imposes conditions on ''v'', ''k'', and ''λ''. These conditions are not sufficient as, for example, a (43,7,1)-design does not exist.
The ''order'' of a 2-design is defined to be ''n'' = ''r'' − ''λ''. The complement of a 2-design is obtained by replacing each block with its complement in the point set ''X''. It is also a 2-design and has parameters ''v''′ = ''v'', ''b''′ = ''b'', ''r''′ = ''b'' − ''r'', ''k''′ = ''v'' − ''k'', ''λ''′ = ''λ'' + ''b'' − 2''r''. A 2-design and its complement have the same order.
A fundamental theorem,
Fisher's inequality Fisher's inequality is a necessary condition for the existence of a balanced incomplete block design, that is, a system of subsets that satisfy certain prescribed conditions in combinatorial mathematics. Outlined by Ronald Fisher, a population gene ...
, named after the statistician
Ronald Fisher
Sir Ronald Aylmer Fisher (17 February 1890 – 29 July 1962) was a British polymath who was active as a mathematician, statistician, biologist, geneticist, and academic. For his work in statistics, he has been described as "a genius who a ...
, is that ''b'' ≥ ''v'' in any 2-design.
A rather surprising and not very obvious (but very general) combinatorial result for these designs is that if points are denoted by any arbitrarily chosen set of equally or unequally spaced numerics, there is no choice of such a set which can make all block-sums (that is, sum of all points in a given block) constant. For other designs such as partially balanced incomplete block designs this may however be possible. Many such cases are discussed in. However, it can also be observed trivially for the magic squares or magic rectangles which can be viewed as the partially balanced incomplete block designs.
Examples
The unique (6,3,2)-design (''v'' = 6, ''k'' = 3, ''λ'' = 2) has 10 blocks (''b'' = 10) and each element is repeated 5 times (''r'' = 5).
Using the symbols 0 − 5, the blocks are the following triples:
: 012 013 024 035 045 125 134 145 234 235.
and the corresponding
incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
(a ''v''×''b''
binary matrix
A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in ...
with constant row sum ''r'' and constant column sum ''k'') is:
:
One of four nonisomorphic (8,4,3)-designs has 14 blocks with each element repeated 7 times. Using the symbols 0 − 7 the blocks are the following 4-tuples:
[
: 0123 0124 0156 0257 0345 0367 0467 1267 1346 1357 1457 2347 2356 2456.
The unique (7,3,1)-design is symmetric and has 7 blocks with each element repeated 3 times. Using the symbols 0 − 6, the blocks are the following triples:][
: 013 026 045 124 156 235 346.
This design is associated with the ]Fano plane
In finite geometry, the Fano plane (named after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and ...
, with the elements and blocks of the design corresponding
Correspondence may refer to:
*In general usage, non-concurrent, remote communication between people, including letters, email, newsgroups, Internet forums, blogs.
Science
*Correspondence principle (physics): quantum physics theories must agree ...
to the points and lines of the plane. Its corresponding incidence matrix can also be symmetric, if the labels or blocks are sorted the right way:
:
Symmetric 2-designs (SBIBDs)
The case of equality in Fisher's inequality, that is, a 2-design with an equal number of points and blocks, is called a symmetric design. Symmetric designs have the smallest number of blocks among all the 2-designs with the same number of points.
In a symmetric design ''r'' = ''k'' holds as well as ''b'' = ''v'', and, while it is generally not true in arbitrary 2-designs, in a symmetric design every two distinct blocks meet in ''λ'' points. A theorem of Ryser provides the converse. If ''X'' is a ''v''-element set, and ''B'' is a ''v''-element set of ''k''-element subsets (the "blocks"), such that any two distinct blocks have exactly λ points in common, then (''X, B'') is a symmetric block design.
The parameters of a symmetric design satisfy
::
This imposes strong restrictions on ''v'', so the number of points is far from arbitrary. The Bruck–Ryser–Chowla theorem
The Bruck– Ryser– Chowla theorem is a result on the combinatorics of symmetric block designs that implies nonexistence of certain kinds of design. It states that if a -design exists with (implying and ), then:
* if is even, then is a squa ...
gives necessary, but not sufficient, conditions for the existence of a symmetric design in terms of these parameters.
The following are important examples of symmetric 2-designs:
Projective planes
Finite projective planes
Finite may refer to:
* Finite set, a set whose cardinality (number of elements) is some natural number
* Finite verb, a verb form that has a subject, usually being inflected or marked for person and/or tense or aspect
* "Finite", a song by Sara Gr ...
are symmetric 2-designs with ''λ'' = 1 and order ''n'' > 1. For these designs the symmetric design equation becomes:
::
Since ''k'' = ''r'' we can write the ''order of a projective plane'' as ''n'' = ''k'' − 1 and, from the displayed equation above, we obtain ''v'' = (''n'' + 1)''n'' + 1 = ''n''2 + ''n'' + 1 points in a projective plane of order ''n''.
As a projective plane is a symmetric design, we have ''b'' = ''v'', meaning that ''b'' = ''n''2 + ''n'' + 1 also. The number ''b'' is the number of ''lines'' of the projective plane. There can be no repeated lines since λ = 1, so a projective plane is a simple 2-design in which the number of lines and the number of points are always the same. For a projective plane, ''k'' is the number of points on each line and it is equal to ''n'' + 1. Similarly, ''r'' = ''n'' + 1 is the number of lines with which a given point is incident.
For ''n'' = 2 we get a projective plane of order 2, also called the Fano plane
In finite geometry, the Fano plane (named after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and ...
, with ''v'' = 4 + 2 + 1 = 7 points and 7 lines. In the Fano plane, each line has ''n'' + 1 = 3 points and each point belongs to ''n'' + 1 = 3 lines.
Projective planes are known to exist for all orders which are prime numbers or powers of primes. They form the only known infinite family (with respect to having a constant λ value) of symmetric block designs.
Biplanes
A biplane or biplane geometry is a symmetric 2-design with ''λ'' = 2; that is, every set of two points is contained in two blocks ("lines"), while any two lines intersect in two points. They are similar to finite projective planes, except that rather than two points determining one line (and two lines determining one point), two points determine two lines (respectively, points). A biplane of order ''n'' is one whose blocks have ''k'' = ''n'' + 2 points; it has ''v'' = 1 + (''n'' + 2)(''n'' + 1)/2 points (since ''r'' = ''k'').
The 18 known examples are listed below.
* (Trivial) The order 0 biplane has 2 points (and lines of size 2; a 2-(2,2,2) design); it is two points, with two blocks, each consisting of both points. Geometrically, it is the digon
In geometry, a bigon, digon, or a ''2''-gon, is a polygon with two sides (edge (geometry), edges) and two Vertex (geometry), vertices. Its construction is Degeneracy (mathematics), degenerate in a Euclidean plane because either the two sides wou ...
.
* The order 1 biplane has 4 points (and lines of size 3; a 2-(4,3,2) design); it is the complete design with ''v'' = 4 and ''k'' = 3. Geometrically, the points are the vertices of a tetrahedron and the blocks are its faces.
* The order 2 biplane is the complement of the Fano plane
In finite geometry, the Fano plane (named after Gino Fano) is a finite projective plane with the smallest possible number of points and lines: 7 points and 7 lines, with 3 points on every line and 3 lines through every point. These points and ...
: it has 7 points (and lines of size 4; a 2-(7,4,2)), where the lines are given as the ''complements'' of the (3-point) lines in the Fano plane.
* The order 3 biplane has 11 points (and lines of size 5; a 2-(11,5,2)), and is also known as the after Raymond Paley
Raymond Edward Alan Christopher Paley (7 January 1907 – 7 April 1933) was an England, English mathematician who made significant contributions to mathematical analysis before dying young in a skiing accident.
Life
Paley was born in Bournemou ...
; it is associated to the Paley digraph of order 11, which is constructed using the field with 11 elements, and is the Hadamard 2-design associated to the size 12 Hadamard matrix; see Paley construction I.
:Algebraically this corresponds to the exceptional embedding of the projective special linear group
In mathematics, especially in the group theoretic area of algebra, the projective linear group (also known as the projective general linear group or PGL) is the induced action of the general linear group of a vector space ''V'' on the associa ...
''PSL''(2,5) in ''PSL''(2,11) – see projective linear group: action on ''p'' points for details.
* There are three biplanes of order 4 (and 16 points, lines of size 6; a 2-(16,6,2)). One is the Kummer configuration In geometry, the Kummer configuration, named for Ernst Kummer, is a geometric configuration of 16 points and 16 planes such that each point lies on 6 of the planes and each plane contains 6 of the points. Further, every pair of points is incident ...
. These three designs are also Menon designs.
* There are four biplanes of order 7 (and 37 points, lines of size 9; a 2-(37,9,2)).
* There are five biplanes of order 9 (and 56 points, lines of size 11; a 2-(56,11,2)).
* Two biplanes are known of order 11 (and 79 points, lines of size 13; a 2-(79,13,2)).
Biplanes of orders 5, 6, 8 and 10 do not exist, as shown by the Bruck-Ryser-Chowla theorem.
Hadamard 2-designs
An Hadamard matrix
In mathematics, an Hadamard matrix, named after the French mathematician Jacques Hadamard, is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. In geometry, geometric terms, this means that each pair of r ...
of size ''m'' is an ''m'' × ''m'' matrix H whose entries are ±1 such that HH⊤ = mIm, where H⊤ is the transpose of H and I''m'' 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 size ''m'' > 2 then ''m'' must be a multiple of 4.
Given an Hadamard matrix of size 4''a'' 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
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
of a symmetric 2-(4''a'' − 1, 2''a'' − 1, ''a'' − 1) design called an Hadamard 2-design.
It contains blocks/points; each contains/is contained in points/blocks. Each pair of points is contained in exactly blocks.
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 size 4''a''.
Resolvable 2-designs
A resolvable 2-design 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.
If a 2-(''v'',''k'',λ) resolvable design has ''c'' parallel classes, then ''b'' ≥ ''v'' + ''c'' − 1.
Consequently, a symmetric design can not have a non-trivial (more than one parallel class) resolution.
Archetypical resolvable 2-designs are the finite affine planes. A solution of the famous 15 schoolgirl problem is a resolution of a 2-(15,3,1) design.
General balanced designs (''t''-designs)
Given any positive integer ''t'', a ''t''-design ''B'' is a class of ''k''-element subsets of ''X'', called ''blocks'', such that every point ''x'' in ''X'' appears in exactly ''r'' blocks, and every ''t''-element subset ''T'' appears in exactly λ blocks. The numbers ''v'' (the number of elements of ''X''), ''b'' (the number of blocks), ''k'', ''r'', λ, and ''t'' are the ''parameters'' of the design. The design may be called a ''t''-(''v'',''k'',λ)-design. Again, these four numbers determine ''b'' and ''r'' and the four numbers themselves cannot be chosen arbitrarily. The equations are
:
where ''λi'' is the number of blocks that contain any ''i''-element set of points and ''λt'' = λ.
Note that and .
Theorem: Any ''t''-(''v'',''k'',λ)-design is also an ''s''-(''v'',''k'',λs)-design for any ''s'' with 1 ≤ ''s'' ≤ ''t''. (Note that the "lambda value" changes as above and depends on ''s''.)
A consequence of this theorem is that every ''t''-design with ''t'' ≥ 2 is also a 2-design.
A ''t''-(''v'',''k'',1)-design is called a Steiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner ...
.
The term ''block design'' by itself usually means a 2-design.
Derived and extendable t-designs
Let D = (''X'', ''B'') be a t-(''v'',''k'',''λ'') design and ''p'' a point of ''X''. The ''derived design'' ''D''''p'' has point set ''X'' − and as block set all the blocks of D which contain p with p removed. It is a (''t'' − 1)-(''v'' − 1, ''k'' − 1, ''λ'') design. Note that derived designs with respect to different points may not be isomorphic. A design E is called an ''extension'' of D if E has a point p such that Ep is isomorphic to D; we call D ''extendable'' if it has an extension.
Theorem: If a ''t''-(''v'',''k'',''λ'') design has an extension, then ''k'' + 1 divides ''b''(''v'' + 1).
The only extendable projective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane (geometry), plane. In the ordinary Euclidean plane, two lines typically intersect at a single point, but there are some pairs of lines (namely, paral ...
s (symmetric 2-(''n''2 + ''n'' + 1, ''n'' + 1, 1) designs) are those of orders 2 and 4.
Every Hadamard 2-design is extendable (to an Hadamard 3-design).
Theorem:.
If D, a symmetric 2-(''v'',''k'',λ) design, is extendable, then one of the following holds:
# D is an Hadamard 2-design,
# ''v'' = (λ + 2)(λ2 + 4λ + 2), ''k'' = λ2 + 3λ + 1,
# ''v'' = 495, ''k'' = 39, λ = 3.
Note that the projective plane of order two is an Hadamard 2-design; the projective plane of order four has parameters which fall in case 2; the only other known symmetric 2-designs with parameters in case 2 are the order 9 biplanes, but none of them are extendable; and there is no known symmetric 2-design with the parameters of case 3.
Inversive planes
A design with the parameters of the extension of an affine plane
In geometry, an affine plane is a two-dimensional affine space.
Definitions
There are two ways to formally define affine planes, which are equivalent for affine planes over a field.
The first way consists in defining an affine plane as a set on ...
, i.e., a 3-(''n''2 + 1, ''n'' + 1, 1) design, is called a finite inversive plane, or Möbius plane In mathematics, the classical Möbius plane (named after August Ferdinand Möbius) is the Euclidean plane supplemented by a single point at infinity. It is also called the inversive plane because it is closed under inversion with respect to any gene ...
, of order ''n''.
It is possible to give a geometric description of some inversive planes, indeed, of all known inversive planes. An ''ovoid
An oval () is a closed curve in a plane which resembles the outline of an egg. The term is not very specific, but in some areas of mathematics (projective geometry, technical drawing, etc.), it is given a more precise definition, which may inc ...
'' in PG(3,''q'') is a set of ''q''2 + 1 points, no three collinear. It can be shown that every plane (which is a hyperplane since the geometric dimension is 3) of PG(3,''q'') meets an ovoid ''O'' in either 1 or ''q'' + 1 points. The plane sections of size ''q'' + 1 of ''O'' are the blocks of an inversive plane of order ''q''. Any inversive plane arising this way is called ''egglike''. All known inversive planes are egglike.
An example of an ovoid is the elliptic quadric, the set of zeros of the quadratic form
::: ''x''1''x''2 + ''f''(''x''3, ''x''4),
where f is an irreducible quadratic form
In mathematics, a quadratic form is a polynomial with terms all of degree two (" form" is another name for a homogeneous polynomial). For example,
4x^2 + 2xy - 3y^2
is a quadratic form in the variables and . The coefficients usually belong t ...
in two variables over GF(''q''). 2 + ''xy'' + ''y''2 for example">'f''(''x'',''y'') = ''x''2 + ''xy'' + ''y''2 for example
If ''q'' is an odd power of 2, another type of ovoid is known – the Suzuki–Tits ovoid.
Theorem. Let ''q'' be a positive integer, at least 2. (a) If ''q'' is odd, then any ovoid is projectively equivalent to the elliptic quadric in a projective geometry PG(3,''q''); so ''q'' is a prime power and there is a unique egglike inversive plane of order ''q''. (But it is unknown if non-egglike ones exist.) (b) if ''q'' is even, then ''q'' is a power of 2 and any inversive plane of order ''q'' is egglike (but there may be some unknown ovoids).
Partially balanced designs (PBIBDs)
An ''n''-class association scheme
The theory of association schemes arose in statistics, in the theory of design of experiments, experimental design for the analysis of variance. In mathematics, association schemes belong to both algebra and combinatorics. In algebraic combinatori ...
consists of a set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''X'' of size ''v'' together with a partition ''S'' of ''X'' × ''X'' into ''n'' + 1 binary relation
In mathematics, a binary relation associates some elements of one Set (mathematics), set called the ''domain'' with some elements of another set called the ''codomain''. Precisely, a binary relation over sets X and Y is a set of ordered pairs ...
s, ''R''0, ''R''1, ..., ''R''''n''. A pair of elements in relation Ri are said to be ''i''th–''associates''. Each element of ''X'' has ''n''i ''i''th associates. Furthermore:
* and is called the Identity relation
In mathematics, a homogeneous relation (also called endorelation) on a set ''X'' is a binary relation between ''X'' and itself, i.e. it is a subset of the Cartesian product . This is commonly phrased as "a relation on ''X''" or "a (binary) relation ...
.
*Defining , if ''R'' in ''S'', then ''R*'' in ''S''
*If , the number of such that and is a constant depending on ''i'', ''j'', ''k'' but not on the particular choice of ''x'' and ''y''.
An association scheme is ''commutative'' if for all ''i'', ''j'' and ''k''. Most authors assume this property.
A partially balanced incomplete block design with ''n'' associate classes (PBIBD(''n'')) is a block design based on a ''v''-set X with ''b'' blocks each of size ''k'' and with each element appearing in ''r'' blocks, such that there is an association scheme with ''n'' classes defined on ''X'' where, if elements ''x'' and ''y'' are ''i''th associates, 1 ≤ ''i'' ≤ ''n'', then they are together in precisely ''λ''''i'' blocks.
A PBIBD(''n'') determines an association scheme but the converse is false.
Example
Let ''A''(3) be the following association scheme with three associate classes on the set ''X'' = . The (''i'',''j'') entry is ''s'' if elements ''i'' and ''j'' are in relation Rs.
The blocks of a PBIBD(3) based on ''A''(3) are:
The parameters of this PBIBD(3) are: ''v'' = 6, ''b'' = 8, ''k'' = 3, ''r'' = 4 and λ1 = λ2 = 2 and λ3 = 1. Also, for the association scheme we have ''n''0 = ''n''2 = 1 and ''n''1 = ''n''3 = 2. The incidence matrix M is
and the concurrence matrix ''MM''T is
from which we can recover the ''λ'' and ''r'' values.
Properties
The parameters of a PBIBD(''m'') satisfy:
#
#
#
#
#
A PBIBD(1) is a BIBD and a PBIBD(2) in which ''λ''1 = ''λ''2 is a BIBD.
Two associate class PBIBDs
PBIBD(2)s have been studied the most since they are the simplest and most useful of the PBIBDs. They fall into six types based on a classification of the ''then known'' PBIBD(2)s by :
# group divisible;
# triangular;
# Latin square type;
# cyclic;
# partial geometry type;
# miscellaneous.
Applications
The mathematical subject of block designs originated in the statistical framework of design of experiments
The design of experiments (DOE), also known as experiment design or experimental design, is the design of any task that aims to describe and explain the variation of information under conditions that are hypothesized to reflect the variation. ...
. These designs were especially useful in applications of the technique of analysis of variance (ANOVA). This remains a significant area for the use of block designs.
While the origins of the subject are grounded in biological applications (as is some of the existing terminology), the designs are used in many applications where systematic comparisons are being made, such as in software testing
Software testing is the act of checking whether software satisfies expectations.
Software testing can provide objective, independent information about the Quality (business), quality of software and the risk of its failure to a User (computin ...
.
The incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
of block designs provide a natural source of interesting block code
In coding theory, block codes are a large and important family of Channel coding, error-correcting codes that encode data in blocks.
There is a vast number of examples for block codes, many of which have a wide range of practical applications. Th ...
s that are used as error correcting code
In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.
The centra ...
s. The rows of their incidence matrices are also used as the symbols in a form of pulse-position modulation
Pulse-position modulation (PPM) is a form of signal modulation in which ''M'' message bits are encoded by transmitting a single pulse in one of 2^M possible required time shifts. This is repeated every ''T'' seconds, such that the transmitted b ...
.
Statistical application
Suppose that skin cancer researchers want to test three different sunscreens. They coat two different sunscreens on the upper sides of the hands of a test person. After a UV radiation they record the skin irritation in terms of sunburn. The number of treatments is 3 (sunscreens) and the block size is 2 (hands per person).
A corresponding BIBD can be generated by the R-function ''design.bib'' of th
R-package agricolae
and is specified in the following table:
The investigator chooses the parameters , and for the block design which are then inserted into the R-function. Subsequently, the remaining parameters and are determined automatically.
Using the basic relations we calculate that we need blocks, that is, 3 test people in order to obtain a balanced incomplete block design. Labeling the blocks and , to avoid confusion, we have the block design,
: , and .
A corresponding incidence matrix
In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is ''X'' and the second is ''Y'', the matrix has one row for each element o ...
is specified in the following table:
Each treatment occurs in 2 blocks, so .
Just one block () contains the treatments 1 and 2 simultaneously and the same applies to the pairs of treatments (1,3) and (2,3). Therefore, .
It is impossible to use a complete design (all treatments in each block) in this example because there are 3 sunscreens to test, but only 2 hands on each person.
See also
* Incidence geometry
In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An ''incide ...
* Steiner system
250px, thumbnail, The Fano plane is a Steiner triple system S(2,3,7). The blocks are the 7 lines, each containing 3 points. Every pair of points belongs to a unique line.
In combinatorial mathematics, a Steiner system (named after Jakob Steiner ...
* Fractional factorial design
In statistics, a fractional factorial design is a way to conduct experiments with fewer experimental runs than a full factorial design. Instead of testing every single combination of factors, it tests only a carefully selected portion. This " ...
Notes
References
*
*
*. 2nd ed. (1999) .
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
External links
DesignTheory.Org
Databases of combinatorial, statistical, and experimental block designs. Software and other resources hosted by the School of Mathematical Sciences at Queen Mary College, University of London.
Peter Cameron Peter Cameron may refer to:
* Peter Cameron (entomologist) (1847–1912), English entomologist who specialised in Hymenoptera
* Peter Cameron (mathematician) (born 1947), Australian mathematician, joint winner of the 2003 Euler Medal
* Peter Camero ...
's page of web based design theory resources.
*
{{Incidence structures
Combinatorics
Combinatorial design
Families of sets
Design of experiments