|
Encyclopaedia of DesignTheory: Glossary |
The label "Topics" or "Encyc" against a glossary entry is a link to either a topic essay or an encyclopaedia entry for this subject; the label "Example" points you to an example, and "External" to a page on the Web with more information.
| This Warning sign is used for terms where there are conflicting meanings in the literature, or other problems of terminology. This is not infrequent in design theory, partly because the combinatorial and statistical aspects of the subject have developed with relatively little interaction. |
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
Many variations are possible. For example, in a multigraph we can take the (v,w) entry to be the number of edges incident with v and w. In a digraph we can take it to be the number of edges with initial vertex v and terminal vertex w.
| Some authors use the term "association scheme" for any coherent configuration. Others don't require the matrices to be symmetric but do require that they commute. |
| Another of those words used differently in combinatorics and statistics. See D. A. Preece, Balance and designs: Another terminological tangle, Utilitas Math. 21C (1982), 85-186. |
In combinatorics, pairwise balance means that two points are contained in a constant number of blocks. This obviously generalises to t-wise balance.
In statistics, there are various different kinds of balance (variance balance, efficiency balance, etc.), none of which are equivalent to the combinatorialist's pairwise balance, but become equivalent to it if some extra conditions are satisfied (e.g. in binary equireplicate uniform block designs, aka 1-designs). To add to the complication, the combinatorialist's 3-design is called "doubly balanced"(!)
"Balance" also arises in other types of designs such as weighing matrices.
In coding theory, a code is binary if the alphabet of the code is the set {0,1} (or the Galois field GF(2) of integers modulo 2.)
In incidence structures, "point" and "block" are the usual terms for the two types of element. Often a block is identified with a subset of the set of points, namely, those points incident with it. If the same set of points arises from more than one block, we say that the structure has repeated blocks.
| Be warned that some combinatorialists use the term as a synonym for "2-design" (see t-design). |
For some structures (groups, or more generally loops or quasigroups), the Cayley table is a Latin square.
For an arbitrary group, a representation is a homomorphism to the group of n×n complex matrices, and the corresponding character is the function which takes any element to the trace of the representing matrix. A character is called irreducible if the representing matrices have no proper invariant subspace. A character is constant on the conjugacy classes of the group, and the numbers of irreducible characters and conjugacy classes are equal; the character table is the square table which gives the values of characters on conjugacy classes.
| A circulant graph is a graph which is also a cyclic design. The cyclic graph is a circulant graph, but not every circulant graph is cyclic! |
An association scheme is a symmetric coherent configuration.
A block design is connected if its incidence graph is.
If the group happens to be Abelian, or if H is a normal subgroup of G, then the left and right cosets coincide and we simply speak of "cosets". In any case, the numbers of left and right cosets are equal; this number is the index of H in G.
Distinct left cosets are disjoint, and each has the same cardinality as the subgroup H; so they form a partition of the group. The same applies to right cosets. This is the basis of Lagrange's Theorem.
If D is a difference set in G with |G|=v and |D|=k, then the translates of D (the sets D+x, for x in G) are the blocks of a square 2-(v,k,lambda) design.
| Some people write this group as D2n, others as Dn. |
A distance-regular graph of diameter 2 is strongly regular, and any connected strongly regular graph is distance-regular with diameter 2.
Any distance-transitive graph is distance-regular.
The rows of a Hadamard matrix form an equidistant code, since any two agree in exactly half of their entries and disagree in the remainder.
If the block design is binary, then this condition is equivalent to regularity of the corresponding hypergraph.
If this holds, then the relation on lines of being equal or disjoint is an equivalence relation called parallelism, and each parallel class of lines covers the point set exactly (that is, each point is incident with just one line of each parallel class).
So an incidence structure satisfying Euclid's parallel postulate is resolvable.
The Galois field of prime order p consists of the integers modulo p.
A more restricted concept, sometimes called a simple graph, has no loops and no multiple edges. In this case, an edge can be identified with an unordered pair of vertices. Two vertices are called adjacent if there is an edge incident with that pair of vertices.
In a directed graph or digraph, edges are ordered (rather than unordered) pairs.
| This is a term which has different meanings to different people! |
Originally, a group divisible design was one in which we are given a partition of the set of points into "groups", all of the same size (the term here has no connection with the algebraic sense) so that two points in the same group lie in lambda1 blocks, while any two points in different groups lie in lambda2 blocks. Such a design (assuming constant block size) is partially balanced (that is, a PBIBD), with respect to the association scheme whose classes are "equal", "in same group but not equal", and "in different groups".
In combinatorial design theory, the conditions of constant group size and constant block size are very often relaxed, but it is often assumed that lambda1=0, that is, a block and a group share at most one common point.
If there are just two types (traditionally called "points" and "blocks"), we usually speak of an incidence structure.
The incidence graph of an incidence geometry has all the varieties as vertices, two distinct varieties being joined if they are incident. It is a multipartite graph; the parts of the multipartition are the types of varieties.
|
Sometimes the transpose of this matrix is used (especially in coding
theory).
|
u·v = u1v1 + ... + unvn.In coding theory we speak of the standard inner product on a vector space over a finite field; it is given by the above formula and satisfies the first two conditions (but not of course the third).
| Sometimes it is not clear exactly what structure is being preserved. For example, for Latin squares, are the roles of rows, columns and symbols interchangeable? |
It follows from Hall's marriage theorem that any Latin rectangle can be extended (by the addition of n-m extra rows) to a Latin square.
| Sometimes it is permitted that the size of the alphabet is greater than the number of columns, and required that each symbol occurs at most once in each row or column. Such an object is a special type of partial Latin square. |
f(x,y) = Sum g(x,z),then
g(x,y) = Sum f(x,z)µ(z,y),where both summations run over all elements z with x<=z<=y.
For example, Rees defined a neighbour design to be a 1-design with a circular structure on each block satisfying this condition; these have subsequently been called "Rees neighbour designs" or "balanced Ouchterlony neighbour designs".
A necessary condition for a graph to have a 1-factorisation is that it is regular. It follows from Hall's marriage theorem that, for bipartite graphs, this condition is also sufficient.
|
One of those words with many different meanings. Be especially careful of
the first two. To make things worse, the word "order" is also used as a synonym for (partially) ordered set! |
The order of a finite group or field is the number of elements it contains.
The order of an element g of a finite group is the smallest positive number m such that gm=1. It follows from Lagrange's Theorem that the order of any element of a group divides the order of the group.
The order of a Latin square is the number of its rows (or columns or symbols).
The order of a projective (resp. affine) plane is the number n such that the plane has n2+n+1 (resp. n2) points.
Sometimes, the order of another type of design (such as a Steiner triple system) is used to mean the number of points of the design.
| The word "orthogonal" has many different meanings. See, for example, D. A. Preece, "Orthogonality and designs: a terminological muddle", Utilitas Math 12 (1977), 201-223. |
Two vectors v and w are orthogonal if v·w=0, where v·w denotes the inner product. Two subspaces V and W are orthogonal if every vector in V is orthogonal to every vector in W.
Two partitions P1 and P2 of a set X are said to be orthogonal if, for any parts Y1 and Y2 of P1 and P2, the size of their intersection is equal to |Y1|.|Y2|/|X|. In other words, the proportion of elements of each part of P1 which belong to a given part Y2 of P2 is constant.
Two Latin squares L1 and L2 are orthogonal if, for each pair (k,l) of symbols, there is a unique cell (i,j) in which L1 has symbol k and L2 has symbol l.
The term orthogonal design has two entirely different meanings.
An orthogonal array is different again - see below.
There is a more general definition which permits using alphabets of different cardinalities in the different coordinate positions.
A theorem of Ryser asserts that if all the symbols in a partial Latin square are confined to i rows and j columns, where i+j <= n, then the array can be completed to a Latin square (by putting symbols in the blank cells).
Permutations in active form are functions and can be composed. This composition is the group operation in the symmetric group.
In other words, it is a subgroup of the symmetric group on X.
If we order the points as p1,...,pn, and the blocks as p1t,...,pnt, then the incidence matrix of the incidence structure is symmetric.
The corresponding term for hypergraphs is uniform.
In other words, left and right division by any element are possible and give a unique result). This means that the equation ax=b has a unique solution x, given a and b; and similarly the equation ya=b has a unique solution y.
The analogous term for block designs is equireplicate.
More generally, an incidence structure is r-resolvable if its blocks can be partitioned into sets such that each point lies in r blocks of each set.
The finite simple groups have been classified.
A code meeting this bound is called maximum-distance separable.
In coding theory, a code which attains this bound is called a perfect code.
| Square 2-designs (BIBDs) are often called "symmetric" in the literature, though there is no requirement that the incidence matrix should be symmetric. (The latter condition is equivalent to the existence of a polarity of the design.) |
Hall's marriage theorem gives a necessary and sufficient condition for a family of sets to have a SDR.
The corresponding term for binary block designs is proper.
For a connected, proper, equireplicate block design, variance balance coincides with the combinatorial condition of pairwise balance. See also balance.
Another representation is as a k×v Latin rectangle with v different symbols, having the properties that the sets of symbols used in the columns of the rectangle are the blocks of a square 2-(v,k,lambda) design.
A Youden "square" is equivalent to a 1-factorisation of the incidence graph of a square 2-design. Hall's marriage theorem implies that any square 2-design can be represented as a Youden "square".
Table of contents | Glossary | Topics | Bibliography | History
Peter J. Cameron
26 October 2002