E D T

# 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

A
Abelian group (Topics)
A group satisfying the commutative law ab = ba.

absolute point of a polarity
An absolute point of a polarity is a point which is incident with its image.

additive group of field or vector space
The group consisting of the elements of the field or vector space, with the operation of addition.

adjacency matrix of graph
The usual adjacency matrix of a simple graph has rows and columns indexed by the vertices of the graph, with (v,w) entry equal to 1 if the vertices v and w are adjacent in the graph and 0 otherwise.

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.

affine
A resolvable design is affine (or affine resolvable) if the number of points common to two blocks in different classes of the resolution is constant. The points and hyperplanes of an affine space form an example.

affine plane (Topics)
A 2-(n2,n,1) design (necessarily affine). The points and lines of an affine space of dimension 2 form an example. An affine plane is a special kind of net.

affine resolvable
A synonym for "affine".

affine space
An affine space of dimension n over a field F is constructed from the vector space of dimension n over F as follows: the objects are all the cosets of the subspaces of the vector space, two objects being incident if one contains the other. Cosets of subspaces with dimension 0, 1, n-1 (as vector spaces) are called points, lines, and hyperplanes respectively.

alphabet
The alphabet of a code or an orthogonal array is the set of symbols used in the codewords or the array entries.

alternating group
The alternating group An is the group consisting of all even permutations of the set {1,...,n} (those which are the product of an even number of transpositions). The group operation is composition of permutations. The order of An is n!/2 . The alternating group is simple for n>4.

association scheme (Example, Topics, External)
A set of symmetric zero-one matrices, containing the identity, having sum equal to the all-one matrix, and having the property that the product of any two matrices is a linear combination of the matrices in the set. It can also be regarded as a partition of X² such that the matrices describing the sets in the partition have the above properties. In other words, it is a symmetric coherent configuration.

 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.

associative law
The law a(bc) = (ab)c. In additive notation, this is written as a+(b+c) = (a+b)+c.

automorphism
An automorphism of a mathematical object is a one-to-one mapping from the object to itself which preserves all the relevant structure. Sometimes, different choices of what the "relevant structure" is lead to different concepts of automorphism (which may be distinguished as strong automorphism, weak automorphism, etc.)

Top

balance for designs
 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.

basis
A basis (for example, in a vector space) is a set of elements with the property that any element of the space can be written uniquely as a linear combination of elements of the basis.

binary
In statistical design theory, a block design is binary if no treatment occurs more than once in a block (that is, a part of the treatment partition and a part of the block partition meet in at most one plot). If this holds, then a block can be thought of as a set (rather than a multiset) of treatments, and the block design can be represented as an incidence structure.

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.)

bipartite graph
A graph is bipartite if the vertices are partitioned into two subsets (the bipartite blocks) so that any edge joins vertices in different parts. Thus, a synonym for 2-partite graph.

block
In experimental design, a block is a subset of the set of plots or experimental units such that, typically, the units of the block are more alike than they are like units outside.

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.

block design (Topics)
In statistics, a block design is a set (of "plots") carrying two partitions, a partition into "treatments" and a partition into "blocks". If it is binary, it can be represented as an incidence structure; if it also has no repeated blocks, it can be represented as a hypergraph.

 Be warned that some combinatorialists use the term as a synonym for "2-design" (see t-design).

Bose-Mesner algebra
The Bose-Mesner algebra of an association scheme is the span (over the real numbers) of the matrices of the scheme. It follows from the definition of an association scheme that this set is closed under multiplication, and is a commutative and associative algebra.

building
A special type of chamber system. Most buildings are associated with algebraic groups. Projective spaces are examples of buildings.

Top

Cayley table
Given a set of n elements x1, ..., xn, with a binary operation ("composition", "multiplication", etc.), we can represent the operation by a Cayley table. This is an n x n array with (i,j) entry xi o xj, where o denotes the binary operation. Sometimes we take the entry to be the index k for which xi o xj = xk.

For some structures (groups, or more generally loops or quasigroups), the Cayley table is a Latin square.

Cayley's Theorem
Cayley's Theorem states that every group is isomorphic to a permutation group. The permutations are the rows of the Cayley table of the group.

chamber system (Topics)
A chamber system is a set carrying a collection of partitions. The standard method of constructing a chamber system from an incidence geometry works as follows. Let {1,2,...,r} be the types. Then the chambers are the maximal flags containing one variety of each type; two chambers are i-adjacent (that is, equivalent in the ith relation) if they have the same varieties of all types except possibly i.

character table (Example)
A character of an Abelian group A is a homomorphism from A to the multiplicative complex numbers, that is, a function X satisfying X(gh)=X(g)X(h). There are equally many characters as group elements. The characters themselves form a group under the operation of multiplication, which is isomorphic to the original group A. The character table is a square table giving the values of the characters on the group elements.

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.

circulant graph
A graph is circulant if its vertices can be labelled with the integers 1,...,v-1 (mod v) in such a way that the cyclic shift x->x+1 (mod v) is an automorphism. A circulant graph is a Cayley graph for the cyclic group.

 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!

class-uniform resolvable design
A resolvable design in which the multiset of block sizes in each parallel class of the resolution is the same.

Classification of the Finite Simple Groups
The finite simple groups have all been classified. The theorem (referred to as CFSG for short) asserts that a finite simple group is of one of the following types:

code (Example)
A code of length n is a set of codewords, each codeword being an n-tuple of symbols taken from some fixed set A called the alphabet of the code.

coherent configuration
A set of zero-one matrices having sum equal to the all-one matrix, having the identity matrix as tthe sum of a subset of its elements, closed under transposition, and having the property that the product of any two matrices is a linear combination of the matrices in the set. It can also be regarded as a partition of X² such that the matrices describing the sets in the partition have the above properties.

An association scheme is a symmetric coherent configuration.

column-complete Latin square
A Latin square is column-complete if each ordered pair of distinct symbols occurs precisely once in consecutive positions in a column of the square.

column-quasi-complete Latin square
A Latin square is column-quasi-complete if each unordered pair of distinct symbols occurs precisely twice in consecutive positions in a column of the square.

commutative law
The law ab = ba. In additive notation, this is written as a+b = b+a.

complete bipartite graph
A bipartite graph in which any two vertices in different bipartite blocks are joined by an edge. Thus, a special case of a complete multipartite graph.

complete-block design
A block design in which every treatment occurs in every block.

complete graph
The simple graph in which every pair of vertices is joined by an edge. The complete graph on n vertices is denoted by Kn.

complete Latin square (Example)
A Latin square is complete if it is both row-complete and column-complete.

complete multipartite graph
A multipartite graph in which every pair of vertices lying in different multipartite blocks is joined by an edge.

connected
A graph is connected if there is a path joining any two of its vertices.

A block design is connected if its incidence graph is.

conjugacy class
Two elements g and h of a group G are conjugate if h=x-1gx for some element x of G. Conjugacy is an equivalence relation whose equivalence classes are called conjugacy classes.

coset
A left coset of a subgroup H of a group G is a set of the form gH for some element g of G; a right coset is of the form Hg.

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.

covering radius
The covering radius of a code C is the smallest integer r such that every n-tuple over the alphabet of C lies at Hamming distance r or less from some codeword of C.

cyclic design
A design is cyclic if we can label its points with 0,...,v-1 (the integers mod v) in such a way that the cyclic shift x->x+1 (mod v) is an automorphism.

cyclic graph
The graph whose vertices are the integers mod v, two vertices being adjacent if their difference is 1 (mod v). It is distance-regular.

cyclic group
A group which is generated by a single element - thus, it consists of all powers of this element (if it is written multiplicatively), or all multiples (if written additively). Any cyclic group is Abelian.

cyclic scheme
The association scheme derived from the distance-regular cyclic graph.

Top

degree of a (hyper)graph
A synonym for valency.

Desargues' Theorem
A configuration theorem for projective planes, which holds in a plane if and only if it can be coordinatised by a field (possibly with non-commutative multiplication).

diameter of a connected graph
The maximum distance between two vertices of the graph.

difference set
Let G be a group, with the operation + (so that -x is the inverse of x). A difference set in G is a subset D of G with the property that each non-identity element g of G can be written in precisely lambda different ways in the form x-y for x,y in D, where x-y is short for x+(-y), and lambda is some constant.

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.

digraph
Short for directed graph.

dihedral group
A dihedral group is a group of order 2n generated by two elements a and b satisfying the relations an=b2=(ab)2=1. The group of symmetries of a regular n-gon is a dihedral group of order 2n.

 Some people write this group as D2n, others as Dn.

dimension
The dimension of a vector space is the number of vectors in a basis of the space.

direct sum or direct product
An algebraic object built from two (or more) objects: its element set is the cartesian product of the element sets of the factors, and operations are defined componentwise. We usually use direct sum for additive structures such as Abelian groups, and direct product for multiplicative structures.

directed graph
A variant of a graph in which an edge is an ordered pair of vertices. Thus, each edge has an initial vertex and a terminal vertex (which may be equal, if the edge is a loop).

directed terrace in a group (Example)
A directed terrace in a finite group G of order n is an ordering (h1,h2,,...,hn) of the elements of G such that the elements hi-1hi+1, for i=1,...,n-1, are all distinct and different from the identity. Directed terraces arise from sequencings, and are used to construct complete Latin squares.

distance in a graph
The distance between two vertices of a connected graph is the smallest number of edges in a path joining the two vertices.

distance-regular graph
A connected simple graph of diameter d is distance-regular if, when we define two vertices to be ith associates if their distance is i, for i=0,...,d, we obtain an association scheme.

A distance-regular graph of diameter 2 is strongly regular, and any connected strongly regular graph is distance-regular with diameter 2.

distance-transitive graph
A connected simple graph is distance-transitive if, whenever two pairs of vertices have the same distance, there is an automorphism of the graph which carries the first pair to the second.

Any distance-transitive graph is distance-regular.

dual of an incidence structure
An incidence structure consists of a set of points and a set of blocks, with a relation of incidence between points and blocks. To form the dual, we re-label the points as blocks and the blocks as points, and reverse the direction of the incidence relation.

duality of an incidence structure
A duality is an isomorphism from an incidence structure to its dual.

dual code of a linear code
The set of all vectors orthogonal to all codewords in the code (with respect to the standard inner product).

dual group of an Abelian group
The group of characters of the given Abelian group, with the operation of multiplication. It is isomorphic to the original group.

Top

equidistant code
A code with the property that the Hamming distance between any two codewords is constant.

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.

equidistant permutation array
A set of permutations of the set {1,...,n} with the property that the Hamming distance between any two is constant. (We regard a permutation in passive form, as a word over the alphabet {1,...,n}.)

equireplicate block design
A block design is called equireplicate if each treatment occurs in the same number of blocks.

If the block design is binary, then this condition is equivalent to regularity of the corresponding hypergraph.

estimation (Topics)
An experimenter measures the response of each of a set of plots assigned various treatments. A statistical model assumes a certain form for this response, depending on the treatment and nuisance factors. The purpose of the experiment is to estimate the parameters associated with the treatment factors. It is important that estimators should be functions of the data only!

Euclid's parallel postulate
In an incidence structure of points and lines, Euclid's parallel postulate is the assertion that, given a line l and a point p not incident with it, there is a unique line l' which is incident with p and disjoint from l.

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.

Top

field
A field is a structure in which the arithmetic operations (addition, subtraction, multiplication, and division except by zero) are defined and satisfy the usual laws (commutative, associative, distributive, etc.)

finite field
See Galois field.

Fisher's inequality
Fisher's inequality asserts that a non-trivial 2-design (or BIBD) has at least as many blocks as points. A design meeting the bound is called square (or sometimes "symmetric").

flag
A flag in an incidence geometry is a set of mutually incident objects or varieties. In an incidence structure with just two types (points and blocks), a flag is usually an incident point-block pair.

Frobenius automorphism
In the Galois field of order pn, the Frobenius automorphism is the function which maps each element to its pth power. It generates the automorphism group of the field (which is thus a cyclic group).

Top

Galois field (Example, Topics)
Galois showed that the number of elements in any finite field must be a power of a prime number; and moreover, for every number which is a prime power, there is a finite field of that order, and it is unique up to isomorphism. These fields are called Galois fields in his honour, and the Galois field with q elements is denoted by GF(q).

The Galois field of prime order p consists of the integers modulo p.

generator matrix
A generator matrix of a linear code is a matrix (with linearly independent rows) whose row space is the given code.

Golay codes
Two remarkable perfect codes (a binary code of length 23 and a ternary code of length 11) associated with the Mathieu groups and the Witt designs.

graph
The term "graph" has several meanings. In the most general form, it is an incidence structure consisting of a set of vertices and a set of edges, each edge incident with one or two vertices. An edge incident with one vertex is called a loop, and an edge incident with two vertices is called a link. Multiple edges (incident with the same set of vertices) are allowed.

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.

greatest lower bound
The greatest lower bound of two elements x and y in a poset is an element z with the properties
• z<=x and z<=y;
• if w is any element satisfying w<=x and w<=y, then w<=z.
The definition extends to more than two elements.

group
A set with an associative operation having an identity element and inverses of each of its elements. The set of automorphisms of any mathematical structure is a group (the operation is composition of mappings).

group action
An action of a group G on a set X is a function from X×G to X taking (x,g) to xg, satisfying the two conditions
• (xg)h=xgh;
• xe=x, where e is the identity of G.
The map taking x to xg is a permutation of X, and the map taking g to this permutation is a homomorphism from G to the symmetric group on X.

group-divisible design
 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.

Top

Hadamard matrix (Topics, External )
An n×n matrix H with entries +1 and -1 satisfying HHT=nI.

Hall's marriage theorem
Hall's marriage theorem asserts that a family of sets has a system of distinct representatives if and only if any k of the sets in the family contain among them at least k elements, for all k.

Hall triple system
A Hall triple system is a Steiner triple system in which any three points not forming a triple are contained in a (unique) 9-point subsystem.

Hamming bound
A term used in coding theory for the sphere-packing bound.

Hamming codes (Example)
A family of perfect 1-error-correcting codes defined over arbitrary Galois fields GF(q). The length of such a code is (qn-1)/(q-1), for some integer n.

Hamming distance
The Hamming distance between two n-tuples x and y is the number of positions i for which xi and yi are different.

Hamming scheme (Example)
The Hamming scheme H(n,q) is the association scheme whose elements are all n-tuples over an alphabet of q symbols, where two elements are ith associates if and only if their Hamming distance is i, for i=1,...,n.

homomorphism
A map from one algebraic structure to another preserving the algebraic operations. Thus, in structures with addition, a homomorphism satisfies F(a+b) = F(a)+F(b), with a similar equation in structures with multiplication.

Howell design
A Howell design H(s,m) (for m even) is an s×s array with the properties
• each cell either is empty or contains an unordered pair of symbols from a fixed alphabet of m symbols;
• each symbol occurs exactly once in each row and once in each column;
• each unordered pair of symbols occurs in at most one cell of the array.
A Room square is a Howell design with m=s+1.

hypergraph
A hypergraph consists of a set Vof vertices and a collection of subsets of V called edges (or hyperedges). If every edge contains two vertices, it is a (simple) graph.

Top

incidence geometry
An incidence geometry consists of a set V of varieties, a set T of types, a type map t from V to T and symmetric incidence relation on V such that two varieties of the same type are incident if and only if they are equal. Sometimes, additional conditions are imposed: for example, that a maximal set of pairwise incident varieties contains exactly one variety of each type.

If there are just two types (traditionally called "points" and "blocks"), we usually speak of an incidence structure.

incidence graph
The incidence graph of an incidence structure (also called the Levi graph) is the graph whose vertices are the points and blocks of the structure, with an edge joining a point and a block if and only if they are incident. It is bipartite, the points and blocks providing the bipartition.

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.

incidence matrix
The incidence matrix of an incidence structure is the matrix with rows indexed by points and columns by blocks, the (p,B) entry being 1 if p and B are incident and 0 otherwise. For a non-binary block design, the (p,B) entry is the number of occurrences of treatment p on plots in block B (which may be greater than one).

 Sometimes the transpose of this matrix is used (especially in coding theory).

incidence structure
An incidence structure consists of a set of points and a set of blocks with a relation of incidence between points and blocks.

incomplete-block design
A block design in which not every treatment occurs in a block.

index of subgroup
The index of a subgroup H of a group G is the order of G divided by the order of H. This is an integer, by Lagrange's Theorem; it is equal to the number of cosets of H in G.

inner product
An inner product on a vector space over the real numbers is a real-valued function of two variables (we write the inner product of u and v as u·v) which is
• linear as a function of each variable,
• symmetric (that is, u·v=v·u), and
• positive definite (that is, u·u>=0, with equality only if u is the zero vector.
If u=(u1,...,un) and v=(v1,...,vn) are written in coordinate form, then the standard inner product is given by
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).

isomorphism
An isomorphism is a homomorphism which is also a bijection (one-to-one and onto). In other words, it is a one-to-one correspondence between two objects which preserves all their mathematical structure. Two objects connected by an isomorphism are called isomorphic, and are identical from the algebraic point of view.

 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?

Top

join
The least upper bound of two elements of a lattice.

Johnson scheme
The Johnson scheme J(v,k) is the association scheme whose elements are the k-element subsets of a set of size v, where two elements are ith associates if their intersection has size k-i.

Top

kernel
The kernel of a homomorphism from one algebraic structure A to another structure B is the set of elements of A which are mapped to the zero or identity element of B.

Kirkman triple system (Example)
A resolvable Steiner triple system. (The existence of such a design of order 15 is Kirkman's Schoolgirl Problem.)

Top

Lagrange's Theorem
Lagrange's Theorem asserts that the order of a subgroup of a group divides the order of the group.

Latin rectangle
A Latin rectangle is an m×n rectangular array of symbols from an alphabet of size n, such that each symbol occurs once in each row and at most once in each column.

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.

Latin square (Encyc, Example)
A Latin square is an n×n array with entries from an alphabet of size n, such that each symbol in the alphabet occurs once in each row and once in each column.

lattice
A lattice is a poset in which any two elements have a greatest lower bound and a least upper bound.

least upper bound
The least upper bound of two elements x and y in a poset is an element z with the properties
• z>=x and z>=y;
• if w is any element satisfying w>=x and w>=y, then w>=z.
The definition extends to more than two elements.

length of a code
The length of a code is the number of symbols in each of its codewords.

Levi graph
The Levi graph of an incidence structure (also called the incidence graph) is the graph whose vertices are the points and blocks of the structure, with an edge joining a point and a block if and only if they are incident.

group of Lie type
These groups are related to certain groups of matrices, and account for most of the finite simple groups. The best-known and commonest example is PSL(2,p), the group of unimodular linear fractional transformations over the integers modulo p (where p is prime).

line graph
The line graph L(G) of a simple graph G is the graph whose vertices are the edges of G, where two vertices of L(G) are adjacent if and only if the corresponding edges of G share a vertex.

linear code
A linear code is a code one whose alphabet is a Galois field, such that the code is a subspace of the vector space of all n-tuples over the field.

linear space
A linear space is an incidence structure in which the blocks are called "lines", having the properties that every line is incident with at least two points, and any two points are incident with exactly one line.

loop
A loop is a quasigroup containing an element e which is an identity for the operation (that is, ae=ea=a holds for all elements a.)

Top

MacWilliams relation
A relation between the weight enumerator of a linear code and that of its dual.

Mathieu groups
The Mathieu groups are five sporadic simple groups discovered by É. Mathieu in the nineteenth century. They are denoted by M11, M12, M22, M23 and M24. They are groups of automorphisms of interesting t-designs with parameters 4-(11,5,1), 5-(12,6,1), 3-(22,6,1), 4-(23,7,1), 5-(24,8,1) respectively; these are referred to as the Witt designs.

matroid (External )
A matroid is a combinatorial structure which abstracts the idea of linear independence in a vector space. A family of subsets of a set is the family if independent sets of a matroid if it is closed under taking subsets and satisfies the exchange property.

maximum-distance separable code
A code attaining the Singleton bound.

MDS
Short for "maximum-distance separable".

meet
The greatest lower bound of two elements of a lattice.

minimum distance
The minimum distance of a code is the smallest Hamming distance between two distinct codewords.

minimum weight
The minimum weight of a linear code is the smallest weight or number of non-zero coordinates in any non-zero codeword.

Möbius function of poset
The Möbius function of the poset P on a set X is the function µ of two variables, given by
• µ(x, y) = 0 unless x<=y;
• µ(x, x) = 1;
• Sum µ(x, z) = 0, where the sum is over all z with x<=z<=y (where x and y are given with x<y).
It is the inverse of the zeta function.

Möbius inversion
Let P be a poset on X with Möbius function µ. If f and g are functions of two variables on X which satisfy
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.

MOLS
Short for mutually orthogonal Latin squares.

multipartite graph
A multipartite graph is one having a partition of the vertices so that any edge joins vertices in different parts. If the number of parts is r, the graph is called r-partite.

multiplicative group of field
The group consisting of the non-zero elements of the field, with the operation of multiplication.

mutually orthogonal Latin squares (Encyc)
A set of Latin squares, any two of which are orthogonal. MOLS for short. Also called "pairwise orthogonal Latin squares" (POLS).

multiset
A multiset is a generalisation of a set, in which elements occur with multiplicities which may be greater than one. It can be regarded also as a list in which the order of the list items is irrelevant.

Top

neighbour design (Example)
In general terms, a neighbour design is a design in which there is a concept of elements of a block being "neighbours", so that every pair of elements occur as neighbours in a block the same number of times.

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".

net (Encyc)
A net of order n and degree r is a partial linear space in which each line has n points, each point is on r lines, and Euclid's parallel postulate holds. A net is equivalent to a set of r-2 mutually orthogonal Latin squares of order n. It is a special kind of partial geometry.

normal subgroup
A subgroup H of a group G is normal if g-1Hg=H for any element g of G. A subgroup is normal if and only if it is a union of conjugacy classes. A normal subgroup is the same thing as the kernel of a group homomorphism.

null polarity
A polarity of an incidence structure is null if every point is absolute.

Top

1-factorisation of graph
A partition of the edge set of the graph into classes, each of which forms a partition of the vertex set of the graph. This is the same thing as a resolution, if we think of the graph as an incidence structure with blocks of size 2.

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.

order of a group, design, etc.
 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.

orthogonal
 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.

orthogonal array
An orthogonal array of strength t and index l over an alphabet A is a rectangular array with elements from A having the property that, given any t columns of the array, and given any t elements of A (equal or not), there are exactly l rows of the array where those elements appear in those columns.

There is a more general definition which permits using alphabets of different cardinalities in the different coordinate positions.

orthogonal design
This term has two quite unrelated meanings.
1. An orthogonal design is a square matrix A, whose entries are either 0 or ±xi, where x1, ..., xs are indeterminates, such that AAT is diagonal.
2. An orthogonal design is, roughly speaking, one where the various factors in the design are orthogonal in the sense of partitions. (More on this later?)

Top

pairwise balanced design
An incidence structure in which any two points are incident with lambda blocks (but block size is not assumed to be constant). Sometimes it is assumed that lambda=1.

Pappus' Theorem
A configuration theorem for projective planes, which holds in a plane if and only if it can be coordinatised by a (commutative) field.

parallel class
A class in a resolution; that is, a set of blocks which partition the point set.

parity check matrix
A parity check matrix of a linear code is a matrix (with linearly independent rows) whose null space is the given code. It is a generator matrix for the dual code.

partial geometry
A partial geometry is a partial linear space satisfying the following three conditions:
• the number of points on a line is constant;
• the number of lines through a point is constant;
• given a point p not on a line L, the number of points on L collinear with p is constant.
A net is an example of a partial geometry.

partial Latin square
An n×n array whose cells are either empty or contain a symbol from an alphabet of size n, such that each symbol occurs at most once in each row or column. A Latin rectangle is an example.

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).

partial linear space
A partial linear space is an incidence structure in which the blocks are called "lines", having the properties that every line is incident with at least two points, and any two points are incident with at most one line.

partially balanced design (partially balanced incomplete-block design, or PBIBD)
A design is partially balanced with respect to an association scheme if the number of blocks containing two points depends only on which class of the partition contains the given pair of points.

partially ordered set (Topics)
A partially ordered set (for short, a poset) is a set X with a binary relation < satifying the conditions
• for no x does x<x hold;
• if x<y and y<z, then x<z.

partition
A partition of a set X is a collection of non-empty subsets of X such that every element of X lies in exactly one set of the partition.

PBIBD
Short for partially balanced incomplete-block design.

perfect code
A code which attains the sphere-packing bound with respect to Hamming distance.

permutation
A permutation can be thought of in two ways: in passive form, it is an arrangement of the elements of a set in order; in active form, it is a one-to-one and onto function from the set to itself (so that the passive form is the image of the "natural" order of the set). For example, the permutation whose passive form is (2,4,1,3) is, in active form the function which maps 1 to 2, 2 to 4, 3 to 1, 4 to 3.

Permutations in active form are functions and can be composed. This composition is the group operation in the symmetric group.

permutation group
A permutation group on a set X is a group whose elements are permutations of X and whose operation is composition of permutations.

In other words, it is a subgroup of the symmetric group on X.

plot
An experimental unit, to which a single treatment is applied.

polarity of an incidence structure (Example)
A polarity is a duality of order 2; that is, a map t from points to blocks which preserves incidence such that, if p is incident with qt, then q is incident with pt.

If we order the points as p1,...,pn, and the blocks as p1t,...,pnt, then the incidence matrix of the incidence structure is symmetric.

POLS
Same as MOLS.

poset
Short for partially ordered set.

prime power canonical form
An expression of a finite Abelian group as a direct sum of cyclic groups, where the order of each cyclic group is a power of a prime.

prime subfield of field
The prime subfield is the unique smallest subfield of a field. In the case of a Galois field with pn elements, the prime subfield has p elements, and is isomorphic to the integers mod p.

primitive root
An element in a Galois field (or in the integers modulo n) which generates the multiplicative group (so that any non-zero element of the field, or any unit of the integers mod n, is a power of the primitive root). Every Galois field has a primitive root; there is a primitive root modulo n if and only if n is pa, 2pa, or 4, where p is an odd prime.

projective plane (Topics)
A 2-(n2+n+1,n+1,1) design (necessarily square). The points and lines of the projective space of dimension 2 form an example.

projective space
A projective space of dimension n over a field F is constructed from the vector space of dimension n+1 over F as follows: the objects are all the subspaces of the vector space, two objects being incident if one contains the other. Subspaces with dimension 1, 2, n (as vector spaces) are called points, lines, and hyperplanes respectively.

proper block design
A block design is proper if all blocks have the same cardinality.

The corresponding term for hypergraphs is uniform.

Top

quadratic residue, quadratic non-residue
A quadratic residue is an element (of a Galois field, for example), which is the square of some element; a quadratic non-residue is one which is not. In a Galois field of odd order, half of the non-zero elements are quadratic residues (all the even powers of a primitive root), and half are not.

quasi-complete Latin square (Example)
A Latin square is quasi-complete if it is both row-quasi-complete and column-quasi-complete.

quasigroup
A quasigroup is a set with a binary operation whose operation table (or Cayley table) is a Latin square.

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.

Top

Rees neighbour design
A neighbour design in which blocks have a circular structure so that each pair of elements occurs as neighbours in a circle exactly once.

regular hypergraph
A hypergraph is regular if the number of edges incident with a vertex is constant. This constant is called the valency, or the degree, of the hypergraph.

The analogous term for block designs is equireplicate.

regular graph
A graph is regular if the number of edges incident with a vertex is constant. This constant is called the valency, or the degree, of the graph.

repeated blocks
An incidence structure of points and blocks has repeated blocks if there are two blocks incident with exactly the same points.

resolvable
An incidence structure of points and blocks is resolvable if there is a partition of the blocks of the structure with the property that each point is incident with exactly one block from each equivalence class. Such an equivalence relation is called a resolution of the structure.

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.

Room square
A room square of (odd) side n is an n×n array with the properties
• each cell either is empty or contains an unordered pair of symbols from a fixed alphabet of n+1 symbols;
• each symbol occurs exactly once in each row and once in each column;
• each unordered pair of symbols occurs in exactly one cell of the array.
It is a special kind of Howell design.

round-dance neighbour design (Example)
A neighbour design in which blocks are complete (each treatment occurs once in each block) and have a circular structure so that each pair of elements occurs as neighbours in a circle exactly once.

row-complete Latin square
A Latin square is row-complete if each ordered pair of distinct symbols occurs precisely once in consecutive positions in a row of the square.

row-quasi-complete Latin square
A Latin square is row-quasi-complete if each unordered pair of distinct symbols occurs precisely twice in consecutive positions in a row of the square.

Top

SDR
Short for system of distinct representatives.

self-dual incidence structure
An incidence structure is self-dual if it is isomorphic to its dual. Equivalently, the points and blocks can be ordered in such a way that the incidence matrix is symmetric.

self-orthogonal Latin square (Example)
A Latin square cannot be orthogonal to itself. So, unfortunately, the term "self-orthogonal" is used of a Latin square which is orthogonal to its transpose.

SOLSSOM
Short for self-orthogonal Latin square with symmetric orthogonal mate (that is, having a symmetric Latin square which is orthogonal to both the given square and its transpose).

semi-Latin square (Example, External)
A semi-Latin square with parameters (n,k) is an n×n array, each of whose entries is a k-element subset of an alphabet of size nk, such that each symbol in the alphabet occurs once in each row and once in each column.

sequencing of a group (Example)
A sequencing of a finite group G of order n is an ordering (g1,g2,,...,gn) of the elements of G such that the partial products g1, g1g2, ..., g1g2···gn are all distinct. The sequence of partial products is called a directed terrace. Sequencings give rise to complete Latin squares.

simple graph
A graph with no loops or multiple edges.

simple group
A simple group is a group whose only normal subgroups are itself and the identity.

The finite simple groups have been classified.

simple incidence structure
An incidence structure of points and blocks is simple if it has no repeated blocks.

Singleton bound
The Singleton bound asserts that a code with length n and minimum distance d over an alphabet of q symbols has at most qn-d+1 codewords.

A code meeting this bound is called maximum-distance separable.

Smith canonical form
An expression of a finite Abelian group as a direct sum of cyclic groups, where the order of each cyclic group divides the order of the next.

SOMA (External )
A SOMA (simple orthogonal multi-array) with parameters (n,k) is a semi-Latin square with these parameters having the further property that the sets of entries in different cells of the array have at most one symbol in common.

sphere-packing bound
In a space where the distances are all integers, if a set of points have mutual distances at least 2e+1, then the spheres of radius e with centres at these points are pairwise disjoint, and so the number of points cannot exceed the number of points in the space divided by the least number of points in a sphere (or ball) of radius e. This is the sphere-packing bound, also known as the Hamming bound.

In coding theory, a code which attains this bound is called a perfect code.

sporadic group
One of twenty-six simple groups which do not fit into an infinite family in a natural way. They include the multiply-transitive Mathieu groups.

square design (Example)
A design is square if it has equally many points and blocks. The points and hyperplanes of a projective space form an example.

 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.)

square lattice graph
The square lattice graph L2(n) is the line graph of the complete bipartite graph with two bipartite blocks containing n vertices each. It is strongly regular.

SQS
Short for Steiner quadruple system.

Steiner quadruple system
A 3-(v,4,1) design.

Steiner system
A t-design with lambda=1.

Steiner triple system (Encyc)
A 2-(v,3,1) design.

strongly regular graph
A (simple) graph is strongly regular if the identity matrix, the adjacency matrix of the graph, and the adjacency matrix of its complement form an association scheme. Equivalently, the graph is regular, the number of common neighbours of two adjacent vertices is constant, and the number of common neighbours of two non-adjacent vertices is constant.

STS
Short for Steiner triple system.

subgroup
A subgroup of a group is a subset which forms a group in its own right (with respect to the same operations).

symmetric design
Another term for a square 2-design.

symmetric group
The symmetric group Sn is the group consisting of all permutations of the set {1,...,n}. The group operation is composition of permutations. The order of Sn is n! .

syndrome decoding (Example)
A decoding method where one computes a linear function (called the syndrome) of a received word with the properties that the syndrome of a codeword is zero while different error patterns have different syndromes. Thus the syndrome determines the error pattern and hence the transmitted word.

system of distinct representatives (Topics)
Let A1, ..., An be sets. A system of distinct representatives (or SDR) is an n-tuple (a1, ..., an) of distinct elements with the property that ai in Ai for i=1,...,n.

Hall's marriage theorem gives a necessary and sufficient condition for a family of sets to have a SDR.

Top

t-design (Encyc)
A t-(v, k, lambda) design is an incidence structure with the properties that there are v points; every block is incident with k points; and any t points are incident with lambda blocks.

ternary
A ternary code is one whose alphabet is {0,1,2} (or the Galois field with three elements).

terrace in a group
A terrace in a finite group G of order n is an ordering (h1,h2,,...,hn) of the elements of G such that, among the elements hi-1hi+1, for i=1,...,n-1, each element of order 2 occurs once, and each inverse pair of elements of order greater than 2 is represented twice. Terraces are used to construct quasi-complete Latin squares.

transversal design
A transversal design is a group-divisible design in which every block is a transversal to the groups (that is, it contains one point from each group).

triangular graph
The triangular graph T(n) is the line graph of the complete graph Kn. It is strongly regular.

Trojan square
A semi-Latin square formed by superimposing a family of mutually orthogonal Latin squares using pairwise disjoint sets of symbols.

Top

uniform hypergraph
A hypergraph is uniform if all its edges have the same cardinality. If this cardinality is k, we call it a k-uniform hypergraph. Thus, a graph is a 2-uniform hypergraph.

The corresponding term for binary block designs is proper.

unit
This term has two quite unrelated meanings:
1. An element which has an inverse. In the integers mod n, an element m is a unit if and only if it is coprime to n. In a field, every non-zero element is a unit.
2. A synonym for plot in a design.

Top

(v,k,lambda) graph (Example)
A strongly regular graph with lambda=mu. It is associated with a polarity of a square 2-design with no absolute points.

valency of a (hyper)graph
The valency, or degree, of a vertex of a graph (or hypergraph) is the number of edges containing that vertex. If all vertices have the same valency, the graph or hypergraph is regular, and this number is the valency, or degree, of the graph (or hypergraph).

variance balance
A block design is variance-balanced if the variances of the best estimators of all the normalised treatment contrasts are equal. (See the Topic essay on "Estimation and variance in block designs".)

For a connected, proper, equireplicate block design, variance balance coincides with the combinatorial condition of pairwise balance. See also balance.

vector space
A vector space over a field F is a structure whose elements can be added to one another or multiplied by scalars (elements of F). The standard model of a vector space is the set of all n-tuples of elements of F, with pointwise addition and scalar multiplication.

Top

weight of a codeword
Assuming that the alphabet contains a zero element, the weight of a word is the number of non-zero entries in the word. If the alphabet is a field, the Hamming distance between two words is the weight of their difference.

weight enumerator of a code
The weight enumerator of a code is the generating function for the number of codewords of given weight in the code.

Witt designs
Five interesting t-designs with parameters 4-(11,5,1), 5-(12,6,1), 3-(22,6,1), 4-(23,7,1), 5-(24,8,1) respectively. Their automorphism groups involve the Mathieu groups, and they are also closely connected with the Golay codes.

Top

Top

Youden "square" (Example)
A Youden "square" can be obtained from the incidence matrix of a square 2-(v,k,lambda) design by replacing the non-zero entries by the symbols 1,...,k in such a way that each symbol occurs exactly once in each row and once in each column.

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".

Top

zeta function of poset
The zeta function of a poset P on a set X is the function Z of two variables given by
• Z(x,y) = 1 if x<=y;
• Z(x,y) = 0 otherwise.

Top

Peter J. Cameron
26 October 2002