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. (Of course we are not responsible for the
availability or content of external web pages.)

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(n^{2},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, n1 (as vector spaces) are called points, lines, and hyperplanes
respectively.

algebra

An algebra is a structure A which is a vector
space over a field F, which also has an
operation of multiplication, with some obvious rules connecting the scalar
multiplication with the algebra multiplication.
If the ring multiplication satisfies the associative
law, we have an associative algebra. Similarly, if the
commutative law holds, we have a commutative
algebra. The prototypical example
of an associative algebra is the set of all n×n
matrices over the field F. Other kinds of algebra such as
Lie algebras and Jordan algebras can be
defined by different laws.

alphabet

The alphabet of a code or an orthogonal
array is the set of symbols used in the codewords or the array entries.
Sometimes we allow the use of different symbols in different coordinate
positions, in which case there is an alphabet associated with each
coordinate.

alternating bilinear form

A bilinear form B is alternating if
B(x,x)=0 for all vectors x.

alternating group

The alternating group A_{n} 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 A_{n} is n!/2 . The alternating group is
simple for n>4.

anallagmatic pavement

This is Sylvester's term for a Hadamard matrix.

ancestral set

An ancestral set in a partially ordered set is a set
A with the property that, if a is in A and
b > a, then b is in A.

antichain

An antichain in a partially ordered set is a set
of pairwise incomparable elements.

association scheme
(Example,
Topics,
External1,
External2)

A set of symmetric zeroone matrices, containing the identity, having sum
equal to the allone 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 use the term for a homogeneous configuration, that
is, one for which the identity is one of the matrices. Yet others don't require
the matrices to be symmetric but do require that they commute. In view of this
confusion, we strongly advocate using the term association scheme in the
sense defined here, and using the terms commutative coherent
configuration, homogeneous coherent configuration, and
coherent configuration for the more general concepts.

If a permutation group is
stratifiable, then its symmetrised
basis matrices form an association scheme. If it
is generously transitive, then the basis matrices
form an association scheme.

associative law

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

atomic Latin square

A Latin square is atomic if every
conjugate of it is
rowHamiltonian. The Cayley table
of a cyclic group of prime order is an example.

automorphism

An automorphism of a mathematical object is a onetoone 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.) For example, given a
resolved design, we could define a weak automorphism
to preserve the design and the resolution, while a strong automorphism fixes
every parallel class in the resolution.

autoparatopy

An autoparatopy of a Latin square is a
paratopy from the square to itself.

autotopy

An autotopy of a Latin square is an
isotopy from the square to itself.

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

In combinatorics, pairwise balance means that two points
are contained in a constant number of blocks. This obviously generalises to
twise 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 1designs). To add to the complication, the combinatorialist's
3design 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.
A basis of a matroid is a maximal independent set.

basis matrices for a permutation group

Let G be a permutation group
on the set {1,...,n}. Then
G has a natural action on the set of ordered pairs (i,j),
for i,j in {1,...,n}. Each orbit in this
action can be represented by a n × n matrix
with (i,j) entry 1 if the pair lies in the orbit, 0 otherwise.
These are the basis matrices of the permutation group.

BIBD

Short for "balanced incompleteblock design", a binary
block design with v treatments, block size k<v, and
any two treatments occurring together in lambda blocks.
Otherwise known as a 2design (with k<v).

bilinear form

A bilinear form on a vector space is a function of two variables which is
linear in each variable if the other is kept constant.
A bilinar form B can be represented by a matrix A:
B(x,y) = xAy^{T}.

binary

This term has several meanings, associated with the number 2 or the set
{0,1} in some way. (To a logician, the number 2 and the set {0,1} are the same
thing!)

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

A relation or operation is binary if it has two arguments. (So composition
in a group is a binary operation, and adjacency in a
graph is a binary relation.)

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 2partite 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 "2design"
(see tdesign).


blocktransitive

See transitive.

blocking set

A blocking set, in a hypergraph or family of sets,
is one of two things: either a set which intersects every edge of the
hypergraph (every set in the family); or else a set which intersects every
edge of the hypergraph and contains no edge. Blocking sets in the second
sense may or may not exist.

BoseMesner algebra

The BoseMesner 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.

cartesian product

The cartesian product A × B of two sets
A and B is the set of all ordered pairs (a,b), for
a in A and b in B. This is extended in the
obvious way to more than two sets.
If the sets A and B carry some structure, for example if
they are groups or graphs, then we would expect that their cartesian product
would carry the same kind of structure, defined coordinatewise. Indeed, the
direct product of groups, or the direct
sum of abelian groups or vector spaces, is defined in exactly
this way. However, for various reasons, the coordinatewise product of graphs
is called the categorical product; the
cartesian product of graphs is defined
differently.
Other graph products include
the lexicographic product and the
strong product.

cartesian product of graphs

The cartesian product of graphs A and B is defined as follows.
The vertex set is the cartesian product of the sets A and B.
Two vertices (a,b) and (a',b') are adjacent if and only if
either
 a is adjacent to a' and b=b'; or
 a=a' and b is adjacent to b'.

categorical product of graphs

The categorical product of graphs A and B is defined as follows.
The vertex set is the cartesian product of the sets A and B.
Two vertices (a,b) and (a',b') are adjacent if and only if
a is adjacent to a' and b is adjacent to b'.

Cayley graph
(Topics)

The Cayley graph of a group G with respect to a subset S
(which should be closed under taking inverses and not contain the identity)
is the graph with vertex set G and an edge joining g to
sg for all g in G and s in S. It
is vertextransitive; indeed, it admits the
group G acting by right multiplication. (This is the action in
Cayley's Theorem: hence the name.)
Not every vertextransitive graph is a Cayley graph; the
Petersen graph is an exception.

Cayley table

Given a set of n elements x_{1}, ...,
x_{n}, 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
x_{i} o x_{j}, where o denotes
the binary operation. Sometimes we take the entry to be the index k
for which
x_{i} o x_{j} = x_{k}.
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.

chain

A chain in a partially ordered set is a subset which
is totally ordered (that is, any pair of elements is comparable).

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
iadjacent (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,...,v1 (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!


circuit

A circuit in a matroid is a minimal dependent set.

classuniform resolvable design

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

classical group

This term refers to a special linear,
symplectic,
orthogonal, or
unitary group, or to the "projective" version of
one of these (the factor group by the group of scalar matrices.)

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
ntuple of symbols taken from some fixed set A called the
alphabet of the code.

coherent configuration

A set of zeroone matrices having sum equal to the allone matrix, having the
identity matrix as the 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.
The basis matrices of a permutation
group form a coherent configuration. Such a configuration is called
Schurian.

Some authors use the term "association scheme" for any coherent
configuration. Others use the term for a homogeneous configuration, that
is, one for which the identity is one of the matrices. Yet others don't require the matrices to be symmetric but do require that they commute. In view of this
confusion, we strongly advocate using the term association scheme for
a coherent configuration all of whose matrices are symmetric,
and using the terms commutative coherent
configuration, homogeneous coherent configuration, and
coherent configuration for the more general concepts.


columncomplete Latin square

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

columnquasicomplete Latin square

A Latin square is columnquasicomplete 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.

complement of a graph

The complement of a simple graph G is the graph
G' with the same vertex set as G, in which two vertices are
joined if and only if they are not joined in G.

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.

completeblock 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
K_{n}.

complete Latin square
(Example)

A Latin square is complete if it is both
rowcomplete and columncomplete.

complete multipartite graph

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

completely symmetric matrix

A square matrix is completely symmetric if all its diagonal entries are equal
and all its offdiagonal entries are equal; in other words, if it has the form
aI+bJ, where I and J are the identity and the
all1 matrices.

composition of functions permutations

The composition of two mappings (functions or permutations)
is the mapping obtained by applying the first and then the second of the given
mappings.

concurrence matrix

The concurrence matrix of a block design is the matrix NN',
where N is the incidence matrix. In the case
of a binary design, its (i,j) entry is the
number of blocks containing the points i and j.

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^{1}gx for some element
x of G. Conjugacy is an equivalence
relation whose equivalence classes are called conjugacy classes.

conjugate of a Latin square

A conjugate of a Latin square is a Latin square obtained
by permuting the roles of "rows", "columns", and "symbols". For example, if
L is a Latin square, then there is a conjugate whose (i,j) entry
is k if and only if the k,j entry of L is i.

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 design
(External)

A (v,k,t)covering design is a collection of kelement subsets,
called blocks, of {1,2,...,v}, such that any telement subset
is contained in at least one block.
See also tight singlechange covering design.

covering radius

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

critical set

A critical set in a Latin square is a set of entries
in a square grid which can be embedded in precisely one Latin square,
with the property that if any entry of the critical set is deleted,
the remaining set can be embedded in more than one Latin square.
If the second condition is deleted, the set is a uniquely
completable set.

crossing

Let A and B be sets carrying collections of
binary relations.
The structure obtained by crossing A and B has the
cartesian product
A × B as its point set; for each relation
R on A, and each relation S on B, there is a
relation (R,S) which holds between pairs (a,b) and (a',b')
precisely when a and a' are in the relation R and
b and b' are in relation S.
The analogous concept for permutation groups is
the direct product.

cubic lattice design

See lattice design.

cyclic design

A design is cyclic if we can label its points with 0,...,v1 (the
integers mod v) in such a way that the cyclic shift
x>x+1 (mod v) is an
automorphism. Equivalently, a design is cyclic if it has
an automorphism permuting the points in a single cycle. Compare
1rotational design.

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

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
distanceregular cyclic graph.

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.

general linear group

The group of all nonsingular linear transformations of a vector space.

generalized inverse

The generalized inverse, or MoorePenrose inverse, of a symmetric real
matrix L is the matrix L^{} such that
LL^{}=L^{}L is the orthogonal projection onto
the row space of L.

generalized polygon

A generalized ngon is an incidence structure
satisfying the following three conditions:
 the number of points on a line is constant;
 the number of lines through a point is constant;
 the incidence graph is connected with diameter
n and girth 2n.
A generalized 3gon is a projective plane, while a
generalized 4gon is a generalized quadrangle.

generalized quadrangle

A generalized quadrangle or GQ is a special case of a
partial geometry. It 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, there is a unique point
on L collinear with p.
The constants in the first two conditions are usually denoted by s+1
and t+1; s and t are the parameters of the GQ.

generator matrix

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

generously transitive permutation group

A permutation group is generously transitive if its
basis matrices are symmetric;
equivalently, if every two points in the domain can be interchanged
by some group element.

gerechte design

A gerechte design is a Latin square L of order
n where the cells are divided into n regions, each containing
n cells, such that each symbol occurs once in each region.
If n=9 and the regions are 3×3 subsquares, this is precisely
the solution to a Sudoku puzzle.
If the regions are the symbol positions in another Latin square L',
then the condition asserts that L and L' are
orthogonal.

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.

GQ

See generalized quadrangle.

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.

graph products

A graph product takes two graphs A and B and produces a graph
whose vertex set is the cartesian product of the
vertex sets of A and B. The most important types of graph
product are the cartesian product,
categorical product, strong
product, and lexicographic product.

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
(Topics)

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 x^{g},
satisfying the two conditions
 (x^{g})^{h}=x^{gh};
 x^{e}=x, where e is the identity of G.
The map taking x to x^{g} is a permutation of X,
and the map taking g to this permutation is a
homomorphism from G
to the symmetric group on X.

groupdivisible 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 lambda_{1} blocks,
while any two points in different groups lie in lambda_{2}
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
lambda_{1}=0, that is, a block and a group share at most
one common point.

Lagrange's Theorem

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

Laplacian matrix of a graph

For a graph with vertices v_{1},...,v_{n},
the Laplacian matrix is the n×n matrix whose
(i,i) entry is equal to the degree of v_{i}, and
whose (i,j) entry for distinct i and j is equal to
1 if i and j are adjacent, 0 otherwise. It is symmetric and
positive semidefinite.

Latin cube

There are several definitions of a Latin cube (information on this is
coming!) The simplest, and easiest to generalise, is an
n×n×n array over an alphabet of n
symbols such that each symbol occurs once in each "line"; in other words,
an orthogonal array of strength 3 and index 1 having
four columns, over an alphabet of n symbols.

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

Association scheme or strongly regular graph
of Latin square type

A set of mutually orthogonal Latin
squares gives rise to an association scheme as follows:
the points are the cells of the squares; two points are first associates if
they lie in the same row or column or contain the same entry in one of
the squares, and are second associates otherwise.
The graph whose adjacent pairs are first associates is a
strongly regular graph of Latin square type.

lattice

There are two unrelated meanings:
1. A lattice is a partially ordered set in which any two
elements have a greatest lower bound and a
least upper bound. Typical examples are the lattice of all
subsets of a set, and the lattice of all subgroups of a
group, ordered by inclusion in each case.
2. A lattice is a discrete subgroup of the additive group of a Euclidean space.
This means that the lattice is closed under addition and negation, and that
there is a nonzero minimum distance between two points of the lattice. An
example is the integer lattice consisting of all points with integer
coordinates.
Based on the second meaning, various combinatorial and statistical designs
have the word lattice in their names, suggesting the regular
arrangement of points in a lowdimensional integer lattice.

lattice design

Lattice designs are particular kinds of resolved
incompleteblock design.
For a square lattice design, there are n^{2}
treatments in rn blocks of size n. The treatments are
allocated to the cells of an n × n square array.
The blocks of the first two
replicates are the rows and columns, respectively, of the array. The remaining
replicates, if any, are defined by r2
mutually orthogonal
latin squares of order n;
the letters of each square define the blocks in the corresponding replicate.
The lattice design is simple if r=2.
Square lattice designs are also called nets. They are
partially balanced with respect to an
association scheme of
Latin square type; first
associates concur once in blocks, second associates never.
For a rectangular lattice design, there are n(n  1)
treatments in rn blocks of size n1. The construction is
similar to that for a square lattice design, except that n cells are
removed from the square array. The removed cells should form a
transversal to
all the Latin squares used in the construction. A rectangular lattice design
is partially balanced if
r=2, n1 or n, but not otherwise.
For a cubic lattice design, there are n^{3} treatments
in 3n^{2} blocks of size n. The treatments form a cube
of order n; the blocks are the 1dimensional slices.

lattice square

This is a design for n^{2} treatments in r
blocks, each of which is a n × n square array.
The construction uses a square
lattice design in 2r replicates.
Pairs of replicates in the old design are combined so that their blocks
form the rows and columns, respectively, of squares in the new design.

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.

lexicographic product of graphs

The lexicographic product B[A] of graphs A and
B is defined as follows.
The vertex set is the cartesian product of the sets A and B.
Two vertices (a,b) and (a',b') are adjacent if and only if
either
 b is adjacent to b'; or
 b=b' and a is adjacent to a'.
This construction is analogous to nesting.

group of Lie type

These groups are related to certain groups of matrices, and account for most
of the finite simple groups. They include the
classical groups.
The bestknown and
commonest example is PSL(2,p), the group of unimodular linear fractional
transformations over the integers modulo p (where p is
prime): the elements are mappings of the form
z > (az+b)/(cz+d),
where a,b,c,d are integers mod p and
adbc = 1.

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 ntuples 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

Note the two different meanings!
A loop in a graph is an edge whose two vertices are the same.
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.) If the elements are 1,...,n, with
e=1, then the Cayley table is a
normalised Latin square.

1factorisation 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 1factorisation is that it is
regular. It follows from
Hall's marriage theorem that, for
bipartite graphs, this condition is also
sufficient.

1rotational design

A block design is 1rotational if it has an automorphism
fixing one point and permuting the others in a single cycle. Compare
cyclic design.

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 g^{m}=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 n^{2}+n+1 (resp. n^{2})
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), 201223.

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 P_{1} and
P_{2} of a set
X are said to be orthogonal if, for any parts Y_{1} and
Y_{2} of P_{1} and P_{2}, the
size of their intersection is equal to
Y_{1}·Y_{2}/X. In other
words, the proportion of elements of each part of P_{1} which
belong to a given part Y_{2} of P_{2} is
constant.
Two Latin squares L_{1} and
L_{2} are
orthogonal if, for each pair (k,l) of symbols, there is a unique cell
(i,j) in which L_{1} has symbol k and
L_{2} has symbol l.
The term orthogonal design has two entirely different
meanings.
An orthogonal array is different again  see below.

orthogonal array
(Example)

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. The requirement is that
the number of rows where given elements occur in t prescribed
columns is constant over all choices of the elements, but is allowed to
vary for different sets of columns. Such an orthogonal array does not have
an index. The example is of this "mixed alphabet" type.

orthogonal block structure

A set carrying a family of partitions such that
 each partition is uniform (all parts have the
same size);
 the any two partitions in the set are
orthogonal;
 the set of partitions is a sublattice of the partition lattice
(that is, it is closed under meet and
join and contains the partition into singletons and
the partition with a single part).
Simple orthogonal block structures and poset
block structures are examples.

orthogonal design

This term has two quite unrelated meanings.
 An orthogonal design is a square matrix A, whose entries are
either 0 or ±x_{i}, where
x_{1}, ..., x_{s} are indeterminates,
such that AA^{T} is diagonal.
 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?)

orthogonal group

The group of linear transformations preserving a nonsingular
quadratic form.

orthogonal polarity

A polarity of projective space
defined by a symmetric
bilinear form.

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.

parabolic quadric

See quadric.

parallel class

A class in a resolution. It is a set of blocks
which form a partition of the point set, in
other words a spread.

paratopy

A paratopy of a Latin square (sometimes called a
main class equivalence) is a transformation which
is a combination of an isotopy (independent permutations
of the sets of rows, columns and symbols) and a permutation of the classes
"rows", "columns" and "symbols".
The word also refers to the equivalence relation thus generated on the set
of Latin squares.

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.
Nets and generalized quadrangles are
examples of partial geometries.

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
incompleteblock design, or PBIBD)
(Example)

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 nonempty subsets of X
such that every element of X lies in exactly one set of the
partition.

PBIBD
 Short for partially balanced incompleteblock
design.

perfect code

A code which attains the spherepacking
bound with respect to Hamming distance.

perfect matroid design

A matroid with the property that, for any number
k not exeeding the rank of the matroid, all flats
of rank k have the same cardinality.

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
onetoone 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
(Topics)

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.

Petersen graph

The Petersen graph is the graph whose vertices are the 2element subsets of
{1,2,3,4,5}, two vertices adjacent if and only if they are disjoint. In
other words, it is the complement of the
triangular graph T(5).
Among its many remarkable properties, it is
strongly regular and
vertextransitive.

PIE (Principle of Inclusion and Exclusion)

See inclusionexclusion principle.

plot

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

plot structure

The need for experimental design, even when comparing an unstructured set
of treatments, is caused by inhomogeneity in the set of
plots.
A common form of structure consists of one or more partitions. In the case
of a single partition, we use a block design. For a pair
of partitions, we use a nested block design or a
rowcolumn design if the
partitions are nested or crossed
respectively. More complicated structures are possible!
There may be further structure as well, such as a neighbour relation, for
which we use a neighbour design.

PMD

See perfect matroid design.

pointtransitive

See transitive.

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 q^{t}, then q is incident
with p^{t}.
If we order the points as p_{1},...,p_{n},
and the blocks as
p_{1}^{t},...,p_{n}^{t},
then the incidence matrix of the incidence structure
is symmetric.

POLS

Same as MOLS.

poset

Short for partially ordered set.

poset block structure

Poset block structures are a special class of orthogonal block
structures which include the simple orthogonal block
structures. The points form the cartesian product
of a family of sets
with trivial structure indexed by a partially ordered set,
and there is a partition corresponding to each ancestral
set in the poset.
The poset block structures corresponding to the 2element
antichain and chain
correspond respectively to crossing and
nesting.

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 p^{n} elements,
the prime subfield has p elements, and is isomorphic to the
integers mod p.

primitive permutation group
(Topics)

A permutation group is said to be primitive if there
is no partition of the domain which is preserved
by the group apart from the trivial partitions
(the partition into singletons, and the partition
with just one part). It is customary to require a primitive group to be
transitive  this excludes the trivial group
acting on two points, which would otherwise qualify as primitive.

primitive root

An element in a Galois field (or in the integers modulo n) which
generates the multiplicative group (so that any nonzero 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 p^{a}, 2p^{a},
or 4, where p is an odd prime.

Principle of Inclusion and Exclusion

See inclusionexclusion principle.

projective plane
(Topics)

A 2(n^{2}+n+1,n+1,1) design (necessarily
square). The points and lines of the projective space
of dimension 2 form an example.

product action

See direct product of permutation groups.

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, that is, contain the same number of plots. For
binary designs, this just means that all blocks
contain the same number of points.
The corresponding term for hypergraphs is
uniform.

Strongly regular graph of pseudoLatin square type

A strongly regular graph is of pseudoLatin square type
L_{s}(n) if its parameters are those which would arise
from s2 MOLS of order n: that is,
v=n^{2},
k=s(n1),
lambda=s^{2}3s+n,
mu=s(s1).

Schurian coherent configuration

A coherent configuration formed by the
basis matrices of a
permutation group.

SDR

Short for system of distinct representatives.

selfdual incidence structure

An incidence structure is selfdual if it is isomorphic
to its dual. Equivalently, the incidence
matrix can be transformed into its transpose
by row and column permutations.

selforthogonal Latin square
(Example)

A Latin square cannot be
orthogonal to itself.
So, unfortunately, the term "selforthogonal" is used of a Latin square which
is orthogonal to its transpose.

selfpolar incidence structure

An incidence structure is selfpolar if it admits a
polarity. Equivalently, its rows and columns can be
ordered so that the incidence matrix is
symmetric.

semiLatin square
(Example,
External)

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

semilinear

A function f on a vector space is semilinear (with respect to a field
automorphism a) if
 f(x+y) = f(x)+f(y;
 f(cx) = c^{a}f(x).

sequencing of a group
(Example)

A sequencing of a finite group G of order
n is an ordering
(g_{1},g_{2},,...,g_{n})
of the elements of G such that the partial products
g_{1}, g_{1}g_{2}, ...,
g_{1}g_{2}···g_{n}
are all distinct. The sequence of partial products is called a
directed terrace. Sequencings give rise to
complete Latin squares.

sesquilinear form


A sesquilinear form on a vector space is a function of two variables which is
linear in the first variable and semilinear
in the other.

sharply transitive set of permutations

A set of permutations of {1,...,n} is sharply transitive if,
given any two symbols i and j,
there is a unique permutation in the set carrying i to j.
This is equivalent to saying that the permutations form the rows of a
Latin square.

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.

simple orthogonal block structure

A set carrying a family of partitions, obtained from sets with trivial
structure (carrying only the relation of equality and the universal relation)
by repeated crossing and
nesting.
It is a special kind of orthogonal block structure.

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 q^{nd+1} codewords.
A code meeting this bound is called maximumdistance
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.

SOLSSOM

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

SOMA
(External
)

A SOMA (simple orthogonal multiarray) with parameters (n,k) is a
semiLatin 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.

special linear group

The group of all linear transformations of a vector space having
determinant 1.

spherepacking 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
spherepacking bound, also known as the Hamming bound.
In coding theory, a code which attains this bound is
called a perfect code.

splitplot design

Another term for a nested block design.

sporadic group

One of twentysix simple groups which do not fit
into an infinite family in a natural way. They include the multiplytransitive
Mathieu groups.

spread

A spread in an incidence structure of points and blocks is a set of
blocks which partition the point set (that is, each
point lies in exactly one block of the spread).
Each parallel class in a
resolution is a spread.

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 2designs (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 design

See lattice design.

square lattice graph

The square lattice graph L_{2}(n) is the
line graph
of the complete bipartite graph with two bipartite
blocks containing n vertices each. We can regard it as an
n × n grid, with two vertices adjacent if they
lie in the same row or column. Alternatively, it is the
categorical product of two
complete graphs with n vertices each.
It is strongly regular.

SQS

Short for Steiner quadruple system.

Steiner quadruple system

A 3(v,4,1) design. See tdesign.

Steiner system

A tdesign with lambda=1.

Steiner triple system
(Encyc)

A 2(v,3,1) design. See tdesign.

stratifiable permutation group

A permutation group is stratifiable if its
symmetrised basis matrices commute. (The
set of basis matrices is closed under transposition;
we replace each pair A, A^{T} by their sum.)

strength

The strength of a proper block design
is the maximum value of t for which it is a tdesign; the
strength of an orthogonal array is the maximum value of
t for which any t symbols occur in any t distinct
coordinates a constant number of times.

strong product of graphs

The strong product of graphs A and B is defined as follows.
The vertex set is the cartesian product of the sets A and B.
Two vertices (a,b) and (a',b') are adjacent if and only if
one of the following holds:
 a is adjacent to a' and b=b';
 a=a' and b is adjacent to b';
 a is adjacent to a' and b is adjacent to b'.
In other words, it has the edges of both the cartesian
and categorical products of the two graphs.

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 nonadjacent vertices is constant.
It is common to use the parameter v for the number of vertices, and
the numbers k,lambda,mu for neighbours of, respectively, one vertex,
two adjacent vertices, and two nonadjacent vertices.

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

Sudoku

The popular Sudoku puzzle involves a uniquely completable
set in a 9 × 9 square grid divided into nine
3 × 3 subsquares, where "completion" involves filling the grid
to form a gerechte design for this partition of the
grid (that is, each digit occurs once in each row, column or subsquare).

Hadamard matrix of Sylvester type

A Hadamard matrix of order 2^{n}
formed by taking the nfold Kronecker product
of the Hadamard matrix of order 2:

symmetric

A binary relation R is symmetric if
R(x,y) implies R(y,x) for all (x,y). A
typical example is adjacency in a graph.
A matrix is symmetric if it is equal to its
transpose. Thus, the adjacency
matrix of a graph is symmetric.
For further meanings of the term, see below.

symmetric bilinear form

A bilinar form B is symmetric if
B(y,x)=B(x,y) for all vectors x,y.

symmetric design

Another term for a square 2design.

symmetric group

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

symplectic group

The group of linear transformations preserving a nonsingular
alternating bilinear form.

symplectic polarity

A polarity of projective space
defined by an alternating bilinear form.

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 A_{1}, ..., A_{n} be sets. A system of
distinct representatives (or SDR) is an ntuple
(a_{1}, ..., a_{n}) of distinct elements
with the property that a_{i} in A_{i} for
i=1,...,n.
Hall's marriage theorem gives a necessary and sufficient
condition for a family of sets to have a SDR.