An (n,g)-cage is a graph which is n-regular and has girth equal to g.


A chain (more commonly called a path ) in a graph is a sequence {x1, x2, x3, ... xk} of nodes such that {[x1, x2], [x2, x3], ... [xk-1, xk]} are edges of the graph. In a non-simple graph (one with repeated edges) it is necessary to impose the condition that no edge occur in the sequence more than it's repetition number. In a simple graph, each edge can appear at most once.

Chromatic Number

The chromatic number (gamma of G) of a graph is the smallest number of colors such that colors can be assigned to all nodes of the graph without having connected nodes with the same color.


A fully connected subgraph of a graph .


A subset of the vectors from a vector space over a finite field , these vectors are collectively called "code words" and the finite field is usually GF(2), although there are useful codes over GF(3) and GF(4) as well.

In an error-correcting code, the code words are chosen such that the "distance" between them is maximized, thus small transmission errors can be recovered by interpreting the received vector as the nearest code word.

See Hamming distance


Let r be a non-negative integer. An r-combination of a set is an unordered selection of r elements out of the set. Equivalently, an r-combination is an r-subset of the original set.


The graph G:xy formed by replacing distinct nodes x and y with a single new node z which is connected to any nodes that were connected to either x or y is called a contraction of G .


A set in Rd is convex if it contains the line segment connecting any two of its points.

Convex Hull

The intersection of convex regions containing a set in Rd.

Coxeter/Dynkin Diagram

A diagram used to visualize a Coxeter group, it is a labeled graph with nodes indexed by the generators of a Coxeter group and (Pi Pj) is an edge whenever Mij > 2 which is labeled with Mij. Where Mij is an entry in the Coxeter matrix corresponding to the given Coxeter group.

Coxeter group

A group generated by the elements Pi with i in {1,2, ... n}, subject to the relations

\[  (P_i P_j)^{M_{ij}} = 1  \] ,

where Mij are the elements of a Coxeter matrix.

Coxeter matrix

A Coxeter matrix of rank n is an n x n matrix M with Mii = 1 and Mij = Mji > 1 (possibly infinite) for all i and j in {1,2, ... n}.

Cross Polytope

A regular polytope, the convex hull of the points formed by permuting the coordinates of (1,0,0,,...,0) and (-1,0,0,,...,0). In three dimensions, this is the octahedron.


In graph theory a cycle is a subset of the edge-set of a graph that form a chain , the first node of which is also the last.

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

An On-line Dictionary of Combinatorics