Certainly many terms are missing, and some terms are lacking definitions
due to lack of time. Also, the conversion of tex commands leaves much to be
desired. Please send notice of items that should be added (or corrected or
clarified) to Douglas B. West at
*west@math.uiuc.edu*.
This glossary is based on the glossary of
*Combinatorial Mathematics*, a graduate textbook
expected to be published in 2004.

For ease in accessing desired definitions, click below on the first letter
or first two letters of the term sought.

A
B
Ca
Ch
Co
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

To search for a specific string on this page, use the "Edit" menu on your
browser and select "Find".

Acyclic - without cycles

Acyclic orientation - an orientation of a graph that is an acyclic digraph

Admissible transposition - applied to a permutation, a transposition that does not change the

Adjacency matrix

Adjacency set

Adjacent - vertices joined by an edge ("

Advance - for a permutation

Affine - 1) for a vector space, ...; 2) for a geometry, ...; 3) for a lattice

Ahlswede-Daykin inequality - if

Algebraic dependence - satisfies a polynomial with coefficients over a field

Almost always - having probability asymptotic to 1

Alteration principle - the two-step randomization in probabilistic methods

Alternating cycle - in a poset, a collection of

Alternating group - the group of permutations with even sign

Alternating path - a path alternating between edges in some set and not in the set (used mostly when the set is a matching)

Angle order - containment order on a collection of angles in the plane

Antiblocker - the hypergraph on

Antichain - set of pairwise incomparable elements

Anticlique - stable set

Antihole - induced subgraph whose complement is

Antisymmetric relation -

Arborescence - a directed forest in which every vertex has out-degree at most one

Arboricity

Arc - directed edge (ordered pair)

Arithmetic progression - sequence of integers differing by a constant

Articulation point - a vertex whose deletion increases the number of components

Ascent - for a permutation

Assignment problem - minimize (or maximize) the sum of the edge weights in a perfect matching of a complete bipartite graph with equal part-sizes

Asteroidal triple - three vertices such that each pair is connected by a path containing no neighbor of the third vertex

Asymmetric - having no automorphisms other than the identity

Atom - element of rank 1

Augmentation property - ability to augment one independent set from a larger one

Augmenting path - 1) for a matching, an alternating path connecting unsaturated vertices; 2) for a flow, a path to increase its value

Automorphism - an edge- or arc-preserving permutation of the vertices

Automorphism group

Balanced graph - among subgraphs, average vertex degree is maximized by the full graph

Ballot list - list of

Bandwidth - minimum, over injective numberings of vertices, of the largest absolute difference between adjacent labels

Barycenter - in a graph, the subgraph induced by vertices with minimum sum of distances to all other vertices

Base - 1) maximal independent set of a matroid; 2) maximal element of an ideal

2-Basis - basis for the cycle space of a graph in which every element appears in at most two elements

BCH (Bose-Chaudhuri-Hocquenghem) code - type of multiple-error-correcting polynomial code

Bell number - number of partitions of

Berge graph - a graph having no odd hole or odd antihole

Bertrand's Ballot Problem - probability that candidates in an election never change order during the counting

Biadjacency matrix - matrix recording the edges of a bipartite graph

Bicentral tree - a tree with two vertices in its center

Binary (matrix, vector, list) - having all entries 0 or 1

Binary matroid - representable over the two-element field

Binary tree - a rooted tree with vertex degrees 1 or 3, except for a root of degree 2

Binomial coefficient - number of ways to select

Binomial sequence - sequence of polynomials,

Bidimension - (also biorder dimension) Ferrers dimension: minimum number of biorders whose intersection is

Bijection - function that yields each element of its target exactly once

Binomial Theorem -

Biorder - name for Ferrers digraph from viewpoint of relations

Bipartite graph - having a vertex partition into (at most) two independent sets

Bipartite Ramsey number - for a bipartite

Bipartite poset - poset whose comparability graph is bipartite

Bipartition - a partition of the vertex set into two independent sets

Birkhoff diamond - a reducible configuration for 4-coloring of planar graphs

Block - 1) maximal (sub)graph with no cutvertex. 2) member of a partition of a set

Block code - a code in which all codewords have the same length

Block design - a family of

Block graph - intersection graph of the blocks

Block-cutpoint graph - bipartite graph on the blocks and cut-vertices of

Board (forbidden positions) - set of positions in a grid

Bond - a minimal edge cut

Bond space - cocycle space

Book embedding - a decomposition of

Boolean algebra - a common name for the subset lattice

Boolean function - function from subset lattice to

Boundary - the cycle bounding a region in an embedding of a graph on a surface

Bounded poset - having one minimal element 0 and one maximal element 1

Box - a rectilinear parallelopiped with sides parallel to the coordinate axes

Boxicity - minimum dimension in which

Bracketing structure - encoding of subsets describing an explicit symmetric chain decomposition

Branch of tree - a subtree obtained by deleting the central edge or by taking a maximal subtree with the central vertex having degree 1

Branch vertex, Branchpoint - vertex of degree at least 3

Branching - a directed graph in which each vertex has indegree one except for a single vertex (root) with indegree 0

Branching forest - arborescence

Breadth-first search - exploration of a graph in order of distance from a fixed vertex

Bridge - 1) an edge whose deletion increases the number of components of a graph. 2) for a subgraph

Brooks' Theorem -

Broom - union of a path and a star at a common leaf

deBruijn graph - describes the possible transitions between words in a stream of letters from an alphabet

Bumping procedure - produces a pair of Young tableaux from a permutation

Burnside's Lemma - tool for counting equivalence classes under group action

Cage - a regular graph of given degree and girth having minimal number of vertices

Canonical cycle representation - listing of cycles of a permutation, each cycle with least element first, cycles in decreasing order of least element

Canonical simplex - simplex in the order polytope associated with a particular linear extension

Canonical tableaux - tableau encoding linear programs using inequality constraints, to emphasize duality

Capacity - a limit on flow through an arc in a network

Cartesian product

Cartesian product

Catalan numbers

Caterpillar - tree with one path (the spine) containing or incident to every edge

Cayley graph - given a group

Cayley's formula - there are

2-cell - on a surface, a region homeomorphic to a disc, i.e. having no handle and having a simple closed curve as boundary

2-cell embedding - an embedding in which every boundary encloses a 2-cell

Center - subgraph induced by the vertices of minimum eccentricity

Central tree - a tree with one vertex in its center

Centroid - for a region in

Chain - 1) set of pairwise comparable elements (totally ordered poset); 2) in graphs, used by some authors to mean a walk

Chain hypergraph - hypergraph on the elements of a poset in which the edges are the sets forming chains

Characteristic equation - polynomial equation related to a linear constant-coefficent recurrence

Characteristic function - for a set, has value 1 on the set, 0 off it

Characteristic polynomial

Characteristic roots - roots of the characteristic equation

Characteristic vector - indexed by the elements of a universe, records the characteristic function for a set

Chinese postman problem - problem of finding the cheapest closed walk covering all the edges in an edge-weighted graph

Choice function - function mapping each subset of

Choosability - list-chromatic number

Chord - edge not in a path or cycle but joining its vertices

Chordal - having no chordless cycle

Chordal poset - having a chordal comparability graph

Chordless cycle - an induced subgraph isomorphic to a cycle of length at least 4

Chromatic index - edge-chromatic number

Chromatic number

Chromatic polynomial

Chvátal conjecture - 1) in an ideal of sets, the largest intersecting family consists of those containing a single element; 2) bounded toughness yields spanning cycle

Circle graph - an intersection graph of chords of a circle

Circuit - 1) for graphs, a closed trail without distinguishing start, used to mean "cycle" by some authors; 2) for matroids, a minimal dependent set

Circle order - containment order on a collection of circles

Circular arc graph - an intersection graph of arcs of a circle

Circulation - an assignment of flows to the arcs of a directed graph such that the net flow at each vertex is 0

Circumference - the length of the longest cycle

Class 1 - simple graph with chromatic index

Class 2 - simple graph with chromatic index

Claw - the graph

Claw-free - having no induced claw

Clique - 1) a pairwise adjacent set of vertices; 2) a complete (sub)graph

Clique cover number

Clique number

Clique partition number - minimum number of cliques to partition

Clique tree - minimal representation of a chordal graph as an intersection graph of subtrees of a tree

Clique-vertex incidence matrix - entry

Closed ear - a cycle being added to a 2-edge-connected graph

Closed neigborhood - a vertex and all its neighbors

Closed walk - a walk with last vertex the same as the first

Closed set - set of matroid elements whose span is itself; more generally, a set invariant under a closure operator

Closure operator - an expansive, order-preserving, idempotent function from subset lattice to itself

Co-atom - element of co-rank 1

Cobase - base of the dual (complement of a base)

Cocircuit - circuit in the dual (matroid)

Cocycle matroid - matroid whose circuts are the bonds of

Code - a set of binary vectors

Coding polynomial - used to encode messages in a polynomial code

Cograph - a graph with no induced

Cointerval graph - complement of an interval graph

Colexicographic order -

Color class - in a coloring, a set of vertices receiving the same color

Color critical - deletion of any edge or vertex reduces chromatic number

Coloring - a mapping to the integers

Column matroid - matroid whose independent sets are the independent sets of columns of a matrix

Column-canonical permutation - permutation obtained from its

Column-strict tableau - placement of integers in the positions of a Ferrers diagram so that rows are strictly increasing and columns are nondecreasing

Columns condition - Rado's condition for monochromatic integer solutions to a matrix equation

Combinatorial geometry - matroid

Common system of distinct representatives - a set of elements that is a system of distinct representatives for each of two families of sets

Comparable -

Comparability digraph - the order relation of a poset, viewed as a digraph

Comparability graph - graph obtained from a partial order by letting elements be adjacent if they are comparable in the partial order

Competition graph - graph obtained from a directed graph

Complement

Complement reducible graph - reducible to isolated vertices by complementation within components

Complementary slackness - condition that in pairs of variables in dual linear programs, at most one is nonzero in optimal solutions

Complete bipartite graph -

Complete digraph - for every pair

Complete graph

Complete

Complete matching - edge set of a 1-factor

Complete

Complete symmetric digraph - every ordered pair of vertices is an edge (once)

Component - maximal connected subgraph

Composition

Conditional probability

Cone - 1) in a poset, the elements comparable to a given element; 2) in linear programming, the positive linear combinations of a set of vectors

Congruence relation mod

Conjugate partition - partition whose Ferrers diagram is transpose of Ferrers diagram of original partition

Connected - 1) for graphs and digraphs, having a

Connection coefficients - matrix to convert between expansions in terms of various binomial sequences

Connectivity

Consecutive chain - a maximal chain between its endpoints (i.e., skipping no ranks)

Consecutive ones property for columns - existence of a row permutation such that ones appear consecutively in each column

Conservation - for a flow, the condition of net flow 0 at a vertex

Containment graph - subgraph of an intersection graph consisting of edges generated by containment

Containment order - poset generated by sets

Contraction - 1) a graph obtained by a sequence of elementary contractions; 2) contraction of matroid

Converse

Convex family - intersection of an ideal and a dual ideal

Convex polyhedron - the set of points satisfying a set of linear inequalities in

Convex polytope - the set of convex combinations of a finite set of points in

Convex property - holds for all objects between two objects where it holds

Convolution - 1) for sequences

Cocycle space - orthogonal complement to cycle space, generated by cocycles

Co-rank - distance from the top in a lattice

Correlational inequality - a statement of positive correlation, as in

Cospectral - having the same spectrum

Cothreshold graph - complement of a threshold graph

Cotriangulated graph - complement of a triangulated graph

Cotree - with respect to a graph, the edges not belonging to a given spanning tree

Countable - set with same cardinality as

Counting two ways - proving identity by finding a set counted by both sides

Cover diagram - cover graph drawn with vertical displacement encoding cover relation

Cover graph - the underlying graph of the cover relation

Cover relation - the order relation consisting of the pairs

Covering problem - in hypergraphs, find the minimum number of edges in

Covers -

Critical classes - sets of positions in the Hales - Jewes Theorem

Critical graph - used with respect to many graph properties, indicating that the deletion of any vertex (or edge, depending on context) destroys the property

Critical pair - an incomparable pair not forced by any other pair

Crossing number cr

Crown - the poset with elements

Cryptomorphism - map from one aspect of a matroid to another

Cubic graph - a regular graph of degree 3

Cubicity - minimum dimension in which

Cut

Cut-edge - an edge whose deletion disconnects a connected graph

Cutset - a set of vertices whose deletion disconnects a graph

Cut-vertex - vertex whose deletion increases number of components

Cutwidth - minimum over vertex orderings

Cycle - 1) an orbit in a permutation; 2) a simple graph whose vertices can be cyclically arranged so that the edges are the pairs of consecutive vertices

Cycle double cover conjecture - a bridgeless graph has a collection of cycles together covering each edge exactly twice

Cycle matroid - for graph

Cycle rank - dimension of cycle space;

Cycle space - the nullspace of the boundary operator, also the set of linear combinations of cycles (modulo 2)

Cyclic codes - codes in which all blocks are translates of a single block

Cyclic edge-connectivity - number of edges that must be deleted to disconnect a component so that every remaining component contains a cycle

Cyclically

Decomposition number - minimum size of a decomposition of

Defect - for a partial transversal, the number of sets not represented

Deficiency - for a set in a bipartite graph,

Degree

Degree-majorization - one degree sequence degree-majorizes another if it dominates it; i.e., the

Degree sequence

Degree set - the set of vertex degrees (listed once each)

Dependent set - contains a circuit

Deletion method - modification technique after generating a random object

Demand - a constraint in the Transportation Problem

Density - 1) in graphs, ratio of number of edges to number of vertices;

Dependency graph - graph on a set of events in which independent sets of vertices correspond to mutually independent sets of events

Derangements - permutations with no fixed point

Diameter - the maximum distance between pairs of vertices in a graph

Digraph - directed graph

Dijkstra's algorithm - finds shortest paths from a vertex, in increasing order of distance

Dilworth decomposition - a partition into

Dilworth's Theorem - a poset of width

Dimension - for posets, order dimension

Direct product - Cartesian product, especially for posets

Direct sum - the matroid union of matroids on pairwise disjoint sets

Directed edge - ordered pair of vertices, also called arc or edge

Directed graph - model in which edges are ordered pairs of vertices

Directed walk, trail, path, cycle, etc. - one that respects edge orientations in a digraph, dropping "directed" does not change the meaning

Disc - in a surface of genus 0, the region bounded by a simple closed curve

Discrepancy - the minimum, over all plus/minus colorings of the vertices, of the maximum sum on an edge

Disconnected - a graph with more than one component

Disjoint union

Distance

Distribution models - classical enumeration problems for objects in boxes

Distributive lattice - a lattice in which

Division algorithm - finds quotient and remainder

Domain - set on which a function is defined

Dominance ordering - ordering on partitions in which

Domination number - the minimum size of a dominating set of vertices

Dominating set - a set

Double shift graph - graph on triples of numbers from

Double star - a tree with at most two nonleaf vertices

Doubly stochastic matrix - matrix in which every row and every column sums to 1

Double torus - the (orientable) surface with two handles

Double width - maximum size of a double antichain

Down-set - ideal

Dual code - the code whose code words form the orthogonal complement of the space of code words of the original code

Dual graph

Dual poset

Dual program - a special linear (or integer) program bounding the original optimization problem

Dual matroid

Dual ideal - an ideal in the dual of

Duplication of vertices - adding a vertex whose neighborhood is that of the vertex duplicated

Ear decomposition - successive removal of ears in a 2-connected graph

Eccentricity - for a vertex, the maximum distance to other vertices

Edge - 1) in a graph, a pair of vertices (

Edge chromatic number

Edge color class - the edges assigned a given color in a proper edge coloring

Edge coloring - an assignment of labels to the edges

Edge connectivity

Edge cover - a set of edges incident to all the vertices

Edge cut

Edge-deleted subgraph - a subgraph obtained by deleting an edge (but not deleting its endpoints)

Edge independence number - the maximum size of a matching

Edge-induced subgraph - the subgraph consisting of a set of edges and all vertices contained in them

Edge-reconstructible - a graph that can be determined (up to isomorphism) by knowing the multiset of subgraphs obtained by deleting single edges

Edge-reconstruction conjecture - the conjecture that every graph with at least four edges is edge-reconstructible

Edge-transitive - a graph where the automorphism group act transitively on the edges (as unordered pairs)

Eigenvalue - for a graph, an eigenvalue of the adjacency matrix

Elementary contraction - "shrinking" an edge by replacing the endpoints with a single vertex incident to all other edges incident to the original endpoints

Elementary cycle - 1) boundary of a region in a plane graph. 2) used to mean (simple) cycle by some authors who use cycle to mean circuit

Elementary subdivision - replacement of an edge by a path of two edges connecting the endpoints of the original edge (also called "edge subdivision")

Embedding - a mapping of a graph into a surface, such that (the images of) its edges do not intersect except at endpoints

Empty graph - having no edges

End-block - a block that intersects only one other

Endpoint - for an edge, either of its members

End-vertex - a vertex of degree 1

Equipartite - having part-sizes differing by at most one

Equivalence relation - reflexive, symmetric, and transitive relation

Equivalence class - a block of the partition induced by an equivalence relation

Equivalent codes - having the same set of codewords

Erdös number - distance from Erdös in the collaboration graph of mathematicians

Erdös-Ko-Rado theorem - the largest collection of sets of size at most

Euclidean algorithm - procedure for extracting greatest common denominator of

Euler characteristic

Euler totient - number of elements in

Euler tour - Eulerian circuit

Eulerian - having an Eulerian circuit

Eulerian circuit - a closed trail containing every edge

Eulerian (di)graph - a graph or digraph having an Eulerian circuit

Eulerian trail - a trail containing every edge

Euler characteristic - for a genus-

Euler's formula - the formula

Even cycle - cycle with an even number of edges (or vertices)

Even graph - graph with all vertex degrees even

Even vertex - vertex of even degree

Expansive property - for set functions,

Expectation - for random variable

Exponential generating function - formal power series expressing a sequence

Exponential formula - a relation between generating functions for connected objects and arbitrary objects of the same type

Extension - for a poset, a poset on the same elements obtained by adding relations

Exterior region - the unbounded region in a plane graph

Factor - a spanning subgraph

Factor-critical - graph where each single-vertex-deleted subgraph has a 1-factor

Factorial

Factorization - an expression of

Falling factorial

Family - a collection of elements in a poset

Fano plane / Fano matroid - design with blocks 124, 235, 346, 457, 561, 672, 713

Fáry's Theorem - a planar graph has a straight-line embedding in the plane

Feasible flow - a network flow satisfying edge-constraints and having net flow 0 at each vertex

Fermat's Little Theorem - if

Ferrer's diagram - an arrangement of unit squares with

Ferrer's digraph - a digraph with no

Fibonacci numbers - sequence with

Field - set endowed with addition and multiplication to form an additive group with identity 0 and a multiplicative group on the nonzero elements

Filter - a dual ideal

Fixed point - an element mapped to itself

FKG inequality - positive correlation for monotone functions on a distributive lattice with a log-supermodular weight function

Flat - a closed set in a matroid

Flow - an assignment of values to variables for each arc of a network

Flower snark -

Forcibly Hamiltonian - a degree sequence such that every simple graph with that degree sequence is Hamiltonian

Forcing relation -

Forest - a disjoint union of trees

Four color theorem - the theorem that planar graphs are 4-colorable

Four function inequality - Ahlswede-Daykin inequality

Fractional - for various packing and covering parameters, the solution to the linear programming relaxation of the integer program for the unmodified parameter

Free matroid - uniform matroid of rank

Fundamental cycle - for a spanning tree, a cycle formed by adding an edge to it

Generalized partition matroid - a direct sum of uniform matroids

Genus

Geodesic - a shortest path between its endpoints

Geodetic - a graph in which each pair of vertices

Geometric lattice - a semimodular lattice without infinite chains in which every element is a join of atoms

Girth

Good coloring - often means proper coloring

Graceful labeling - injective vertex labeling from

Graceful graph - a graph with a graceful labeling

Graceful tree - a tree with a graceful labeling

Graded poset - all maximal chains have the same length

Graeco-Latin square - an orthogonal pair of Latin squares

Graph - a collection of pairs of elements from some set

Graphic matroid - a matroid that is the cycle matroid of some graph

Graphic sequence - a list of integers realizable as the vertex degrees in a simple graph

Graph Ramsey number

Greatest lower bound

Greedy algorithm - a fast non-backtracking algorithm to find a good feasible solution by iteratively making a heuristically good choice

Greedy coloring - given a vertex ordering, color each vertex with the least-indexed color not appearing on earlier neighbors

Greedy dimension - minimum number of greedy extensions realizing

Greedy extension - linear extension such that

Greene-Kleitman Theorem - for every poset and every

Grötzsch graph - the smallest triangle-free 4-chromatic graph

Grundy number - the maximum number of colors in an application of the greedy coloring algorithm

Hadwiger conjecture - a

Hajós conjecture - a

Halin graph - obtained from a planar embedding of a tree by adding a cycle through the leaves in order

Hall's Condition - 1)

Hall's Theorem - Hall's Condition is necessary and sufficient condition for the existence of a 1) matching, 2) system of distinct representatives

Hamilton tour - Hamiltonian cycle

Hamiltonian - having a Hamiltonian cycle

Hamiltonian-connected - having a spanning path from each vertex to every other

Hamiltonian cycle - a cycle containing each vertex

Hamiltonian path - a path containing each vertex

Hamming distance - number of positions in which coordinates differ

Harary graphs - graphs of minimum size for given order and connectivity

Hasse diagram - cover diagram

Head - the second vertex of an edge in a digraph

Head partition matroid - the partition matroid induced on the edges of a digraph by the partition according to heads

Heawood Theorem - the chromatic number of a graph embedded on the oriented surface with

Height - size (or one less than size) of largest chain in poset (or having

Helly property - the property of the real line (or trees) that any collection of pairwise intersecting subsets has a common intersection point

Helly number - for some universe, the number

Hereditary class - a class

Hereditary hypergraph - every subset of an edge is an edge (an ideal of sets)

Hereditary property - a graph property preserved by taking induced subgraphs

Hereditary system - on a ground set of elements

Homeomorphic - obtainable from the same graph by subdivision of edges

Homogeneous set - in Ramsey theory, a set whose subsets receive the same color

Homomorphism - a map

Hook - L-shaped subset of positions in a tableau

Hook length - size of hook

Hook length formula - formula for number of tableaux of a given shape

Hungarian method - an algorithm for solving the assignment problem

Husimi tree - a graph in which every block is a clique

Hypergraph - a generalization of graph in which edges may be any subset of the vertices, equivalently, a set system

Hyperplane - a maximal closed nonspanning set of matroid elements

Hypohamiltonian - a non-Hamiltonian graph whose vertex-deleted subgraphs are all Hamiltonian

Hypotraceable - a non-traceable graph whose vertex-deleted subgraphs are all traceable

Idempotence -

Identification - an operation replacing two vertices by a single vertex with the combined incidences (similar to contraction if the vertices were adjacent

Implication class - a collection of edges such that the orientation of any one determines the orientation of the others in any transitive orientation

Incidence algebra - functions defined on intervals in a poset, with

Incidence matrix - the matrix in which entry

Incident - 1) for a vertex

Incomparable

Incomparable pair - ordered pair of incomparable elements

Incomparability graph - obtained from a partial order by letting elements be adjacent if they are incomparable in the partial order

Indegree - for a vertex in a digraph, the number of edges of which it is the head

Independence number

Independent domination number - minimum size of an independent dominating set

Independent events -

Independent set - 1) in graphs, a set of pairwise nonadjacent vertices; 2) in hereditary systems and matroids, an element of the ideal

Indifference graph - representable by assigning weights to vertices such that

Induced sub(di)graph (

Integer program - a combinatorial optimization problem in integer variables

Internal vertices - 1) for a path, the non-endvertices. 2) for a plane graph, the vertices that do not belong to the boundary of the exterior face

Internally disjoint paths - paths intersecting only at end-vertices

Intersecting family - a pairwise intersecting collection of sets

Intersection - 1) for posets

Intersection graph - for a collection of sets, the graph with a vertex for each set, in which vertices are adjacent if the sets intersect

Intersection number - minimum size of a set such that

Interval count - minimum number of distinct interval lengths in a representation of an interval graph

Interval dimension - minimum size of a realizer by interval extensions

Interval extension - interval order that is an extension

Interval graph - a graph having an interval representation

Interval number - minimum

Interval order - a poset representable by real intervals such that

Interval representation - a collection of intervals whose intersection graph is

Inversion - 1) a pair of elements

Involution - a permutation of order two (fixed points and disjoint transpositions)

Involution principle - a procedure for generating bijective proofs from involutions

Irreducible poset - deletion of any element reduces the dimension

Isolated - vertex (or edge) incident to no (other) edge

Isometric embedding - a distance-preserving mapping of

Isomorphism - a bijection between sets of vertices (or elements) that preserves structure; graphs (preserves adjacency), digraphs (preserves succession), posets (preserves order), lattices (preserves meets and joins), etc.

Join

Join

Joined to - adjacent to

Kernel - independent dominating set

Kirchhoff's current law - net flow around a closed walk is 0

Kirkman triple system - resolvable Steiner triple system

Kleitman's inequality - membership in ideals is positively correlated (holds as generally as distributive lattices

Knotting graph - a modification of a graph that is bipartite if and only if the graph is a comparability graph

König's Theorem - independence number equals edge cover number for bigraphs

König-Hall-Egervary Theorem - maximum matching equals vertex cover number for bipartite graphs

Kronecker product - weak product

Kruskal's algorithm - greedy algorithm for minimum weighted spanning tree

Kruskal-Katona theorem - the collection of

Kuratowski's theorem - a graph is planar if and only if it has no subgraph homeomorphic to

Latin square - an

Lattice - poset where each two elements have a greatest lower bound and a least upper bound

Lattice path - a path from one integer point to another, moving by a specified set of integer steps, usually

Leaf - an endvertex of a tree

Least upper bound

Length - 1) in graphs, the number of edges (counted with multiplicity, if necessary); 2) in posets, height; 3) in codes, the number of code digits (

Lexicographic product - composition

Line - another name for edge

Line graph

Linear code - a code

Linear extension - an extension of a poset that is a chain

Linear order - totally ordered set (chain)

Linear program - maximization (or minimization) of a linear objective function of

Link - edge

Locally finite - every interval has finitely many elements

Log-concave sequence -

Log-supermodular function -

Loop - an edge joining a vertex to itself; a circuit of size 1 in a matroid

Loop-graph - pseudograph

Lower bound - 1) for elements in a poset, an element that is less than or equal to all of them; 2) for a poset, an element less than all others

Lower extension of

Lower semimodular lattice -

Lucas numbers - satisfy the Fibonacci recurrence and have

LYM inequality - the sum of reciprocals of rank-sizes is at most 1

LYM property - every antichain satisfies the LYM inequality

Martingale - sequence of random variables in which the expectation of

Matching - a set of pairwise disjoint edges in a graph or hypergraph

Matric matroid - representable matroid

Matrix game - 2-person 0-sum game, with payoff from one player to other given by a matrix indexed by the player's pure options

Matrix-tree theorem - counting of spanning trees of

Matroid - a hereditary system satisfying any one of a plethora of equivalent useful additional conditions

Matroid intersection theorem - the maximum size of a common independent set in matroids

Max-flow min-cut theorem - maximum flow value equals minimum cut value

Maximal - used with sets satisfying any property, meaning that addition of anything destroys the property (examples follow)

Maximal chain - no additional element is comparable to all elements of the chain

Maximal clique - a maximal vertex set inducing a clique

Maximal element - an element of a poset that is not covered by any other

Maximal planar graph - a simple planar graph where adding any edge destroys planarity

Maximum - a "maximum set" of some type is a maximum-sized set of that type (implies maximal) (examples - maximum antichain, maximum clique)

Maximum degree

Maximum flow - a feasible flow of maximum value, or the value of such a flow

Maximum genus

Meet

Metric - a real-valued symmetric non-negative binary function that is 0 only when the arguments are equal and satisfies the triangle inequality

Menger's theorems - minimax characterizations of connectivity by number of internally-disjoint or edge-disjoint paths between pairs of vertices

Minimal - used with any property, meaning that deletion of anything destroys the property

Minimum - a "minimum set" of some type is a minimum-sized set of that type (implies minimal) (examples - minimum chain cover)

Minimum cost flow problem - miinimize the cost of a feasible flow

Minimum cut - a network cut having minimum value, or the value of such a cut

Minimum cutset - a minimum-sized set of elements meeting all maximal chains

Minimum degree

Minimum spanning tree - spanning tree with minimum sum of edge weights

Minimum vertex cover - a minimum-sized set of vertices covering the edges

Min-max relation - a universal equality between the solution values to a pair of natural dual combinatorial optimization problems, typically dual linear integer programming problems

Minor - 1) a contraction of a subgraph; 2) a restriction of a contraction

Mixed graph - a graph concept allowing directed and undirected edges

Möbius function - the inverse of

Möbius inversion formula - generalization of inclusion-exclusion to posets, in which

Möbius ladder - obtained by adding to an even cycle the chords between diametrically opposite vertices (a ladder with a twist)

Möbius strip - the non-orientable surface obtained by identifying two opposite sides of a rectangle using opposite orientation

Modular lattice -

Monochromatic - in a coloring, a set having all elements the same color

Monotone property - a graph property preserved by taking arbitrary subgraphs

Multigraph - allows multiple edges (arcs), but generally no loops

Multiple edges - repeated pairs of vertices in the edge set

Neighbors - (noun) the vertices adjacent to a given vertex; (verb) "is adjacent to"

Neighborhood

Net flow - at a vertex, the sum of flows on exiting edges minus the sum of flows on entering edges

Network - a directed graph with a distinguished initial vertex (set) and a distinguished terminal vertex (set), in which each edge is assigned a flow capacity and sometimes also a flow demand (lower bound)

Node - vertex, especially in network flow problems

Node potential - dual variable in min cost flow problem

Normal product - strong product

Normalized matching property - for any set of elements

Null graph - graph having no vertices

Odd component - component with an odd number of vertices

Odd cycle - cycle with an odd number of edges (vertices)

Odd hole - chordless odd cycle

Odd vertex - vertex of odd degree

On-line algorithm - algorithm that only learns the input one item at a time

Open walk - walk in which the end-vertices differ

Optimal tour - solution to Traveling Salesman problem or Chinese Postman problem

Order - the number of vertices, sometimes called "size" when no confusion is (hopefully) possible

Order dimension - minimum number of linear extensions whose intersection is

Ordered set - partially ordered set

Order-reversing - a function from the elements of one ordered set to another such that

Order polynomial - value at

Order polytope - the order-preserving functions from a poset to the interval

Order-preserving - a function from the elements of one ordered set to another such that

Ordinal sum

Ordinary generating function - formal power series expressing

Orientable surface - a surface with two distinct sides

Orientation - an assignment of order to each of the edge pairs in an undirected graph, making it a directed graph

Orthogonal - 1) for two chain decompositions, having no pair on the same chain in both decompositions; 2) for a chain partition and an antichain partition, each chain intersects each antichain; 3) for Latin squares, each pair of elements appears in corresponding positions exactly once

Outdegree - for a vertex, the number of arcs of which it is the tail

Outerplanar graph - a planar graph embeddable in the plane so that all the vertices belong to the boundary of the exterior region

Out-of-Kilter algorithm - algorithm to solve min-cost flow problems

Overlap graph - subgraph of the intersection graph of a set of intervals, obtained by discarding edges generated by one interval contained in another

Packing problem - in hypergraphs, find the largest edge in the antiblocker

Page - one of the outerplanar subgraphs in a book embedding

Pagenumber - minimum number of pages in a book embedding

Pan-connected - the condition of having, for every pair of vertices

Pancylic - having cycles of all lengths at least 3

Parallel edges - multiple edges

Parallel elements - circuits of size two in a matroid

Partial extension - an extension of a poset, usually not a linear extension

Partially ordered set

Partite set - what are usually called the "parts" in a

Partition matroid - matroid with independent sets being those with at most one element in each block of a given partition of

Partitionable graph -

Part-sizes - sizes of the partite sets

2-part Sperner property - largest semiantichain in product poset is a single rank

Path - an open walk with no repeated vertices (in a digraph, must follow arrows)

Pattern inventory - a generating function in many variables in which the coefficient of

Pendant edge - incident with a pendant vertex

Pendant vertex - 1-valent vertex

Perfect code - single-error correcting code in which every possible received word is within distance one of a codeword

Perfect graph - chromatic number equals clique number for all induced subgraphs

Perfect graph theorem - a graph is perfect if and only if its complement is perfect

Perfect matching - edge set of a 1-factor

Permanent - for an

Permutation graph - representable by a permutation

Petersen graph - a graph disproving many reasonable conjectures, it is the complement of the intersection graph of the 2-sets of a 5-element set

Pigeonhole principle - in a set of numbers, there is one that is at least the average

Planar - embeddable in the plane 1) for graphs, drawable in plane without crossings; 2) for posets, having a planar cover diagram

Plane graph - a particular planar embedding of a planar graph

Plane partition - placement of integers in the position of a Ferrers diagram so that rows and columns are nondecreasing

Platonic solid - bounded regular polyhedron

Point - vertex

Poisson paradigm - technique for obtaining sharp threshold functions

Polya's Theorem - technique for counting equivalence classes by patterns

Polygon matroid - cycle matroid

Polyhedron - an intersection of half-spaces

Polynomial code - linear codes encoded by polynomial multiplication

Polytope - the convex hull of a set of vertices

Poset - partially ordered set

Potential - a vertex labeling used in the dual to the min-cost flow problem

Predecessor - for

Predecessor set - for

Principle ideal - an ideal generated by one element (having one maximal element)

Product - obtained by combining factors in several possible ways - see Cartesian product, direct product, normal product, strong product, weak product

Product dimension - minimum number of cliques whose weak product contains

Projective plane -

Proper coloring - 1) for vertices, a coloring in which no edge is monochromatic. 2) for edges, a coloring in which no intersecting edges get the same color

Proper interval graph - having an interval representation in which no interval contains another

Proper subgraph - a subgraph not equal to the graph itself

Prüfer code - for a labeled tree, a sequence of length

Pseudograph - graph model with both loops and multiple edges permitted

Ramsey number - the minimum number of vertices such that assigning colors to all pairs of those vertices produces a monochromatic clique of specified size (or a specified graph) in one of the colors

Random graph - a graph from a probability space, most often the space in which each labeled pair of vertices independently has probability

Rank - 1) in posets, length of longest chain, a set of elements with the same height, or the maximum size of a minimal relaizer by linear extensions

Rank function - 1) in a poset, increases by 1 with cover relations; 2) in a matroid, gives largest size of an independent set in

Ranked - having a rank function

Ranking - a ranked poset having all relations between ranks

Reachability matrix - for a directed graph, the matrix in which entry

Realizer - a collection of extensions whose intersection is

Reciprocity theorem - in general, a relationship between two functions

Reconstructible - a graph determined (up to isomorphism) by its multiset of subgraphs obtainable by deleting a single vertex

Reconstruction conjecture - the conjecture that all graphs with at least 3 vertices are reconstructible

Rectilinear crossing number - the minimum number of crossings in a drawing of the graph in the plane in which all edges appear as straight line segments

Reflexive - 1) for a digraph, having a loop at every vertex; 2) for a binary relation

Region - for an embedding of a graph on a surface, a maximal connected subset of the surface that does not contain any part of the graph

Regular - 1) for a graph, having all vertex degrees equal; 2) for a poset, having each element at rank

Regular covering - nonempty list of maximal chains such that every element appears as often as as every other element in its rank

Removable pair - pair of elements whose deletion reduces dimension by at most 1

Representable matroid - a matroid whose independent sets are the independent sets of columns of some matrix (over some field)

Restriction - restriction of a matroid

Reverse lexicographic order -

Rigid circuit graph - chordal graph

Root - 1) a distinguished vertex; 2) for a directed tree, a vertex from which every other is reachable

Rooted - having a root specified

Rotation scheme - a description of a 2-cell embedding; a circular permutation of the edges at each vertex, giving their counter-clockwise order around the vertex

RSK (Robinson-Shensted-Knuth) correspondence - a bijection from permutations of

Saturated vertex - 1) for a matching, a matched vertex. 2) for a

Score sequence - the sequence of outdegrees in a tournament

Second moment method - method for obtaining threshold functions

Self-complementary - isomorphic to the complement

Self-converse - isomorphic to the converse

Self-dual - isomorphic to the dual

Semiantichain - in

Semi-strong perfect graph theorem - intermediate between the perfect graph theorem and strong perfect graph theorem, concerns the

Semilattice - poset where each pair of elements has a greatest lower bound (meet semilattice), or where each pair has a least upper bound (join semilattice)

Semimodular lattice - (also "upper semimodular")

Semiorder - a poset representable by a function

Semipath - for a digraph, a path in the underlying graph

Semiwalk - for a digraph, a walk in the underlying graph

Separating set - a vertex set whose deletion increases the number of components

Separator theorem - for a hereditary class of graphs, specifies a small function of

Shannon capacity - limit of

Signed (di)graph - special case of weighted (di)graph, assinging

Simple - 1) graph having no loops or multiple edges; 2) hypergraph having no loops or edges sharing two vertices; 3) matroid having no loops or parallel elements; 4) poset having width equal to the number of maximal chains; 5) polytope having every vertex of degree equal to the number of dimensions

Simple game - an

Simplex - 1) method for solving linear programs; 2) the convex hull of

Simplicial - 1) vertex whose neighbors induce a clique; 2) hypergraph where every subset of an edge is also an edge; 3) polytope where every face is a simplex

Sink - the distinguished terminal vertex (set) in a network

Size - the number of edges, sometimes used for the number of vertices

Source - the distinguished initial vertex (set) in a network

Span function

Spanning - 1) subgraph containing each vertex; 2) subset of matroid elements that span the entire ground set

Spectrum - the set of eigenvalues

Sperner property - for a ranked poset, having a maximum antichain consisting of a single rank

Sperner's lemma - a properly labeled simplicial decomposition of a simplex has a completely labeled fundamental simplex

Sperner's theorem -

Split graph - having a vertex partition into a clique and an independent set

Splitting element - comparable to every other

Square of a graph - the second power

Star - 1) in graphs, a tree with at most one non-leaf (

Steiner triple system - block design using blocks of size 3

Steinitz(-Maclane) exchange property - for a set function

Stirling's formula -

Stirling number (of the second kind)

Stirling numbers of the first kind

Strict chain -

Strict correlation -

Strict Sperner property - all maximum antichains are single ranks

Strictly balanced - average vertex degree is strictly greater than average vertex degree of any subgraph

Strong component - maximal strongly connected subdigraph

Strong digraph - strongly connected

Strong order on

Strong orientation - strongly connected orientation

Strong perfect graph theorem - a graph is perfect if and only if it has no odd hole or odd antihole

Strong product

Strong Sperner property -

Strongly connected - digraph having a

Strongly chordal - a chordal graph having a perfect elimination scheme in which the neighbors of the vertex to be deleted have neighborhoods forming a chain under inclusion; equivalent to forbidding trampolines as induced subgraphs

Strongly perfect - a graph in which some stable set meets every maximal clique

Subdigraph - a subgraph of a directed graph

Subdivision - replacement of edges by paths

Subgraph - a graph whose vertices and edges all belong to

Sublattice - a subposet of a lattice that is a lattice and inherits meets and joins from the full lattice

Submodular function -

Subposet - a poset on a subset of the elements that inherits all relations among the elements (analogous to induced sugraph)

Subspace - a closed set in a matroid

Successor - for

Successor set - for

Sum - 1) for cycles and cocycles, taken modulo 2. 2) for a graph, the disjoin union. 3) for matroids on disjoint sets, the matroid on their union whose independent sets are all unions of an independent set from each

Supergraph - a graph of which

Supermodular function -

2-switch - replacing two independent edges with two edges forming a 4-cycle with them

Symmetric - 1) for a graph, having a non-trivial automorphism; 2) for a digraph, having

Symmetric chain - in a poset of rank

Symmetric chain decomposition - partition of

Symmetric chain order - having a symmetric chain decomposition

System of distinct representatives - from a collection of sets, a choice of one member from each set so that all the representatives are distinct

Tail partition matroid - the partition matroid induced on the edges of a digraph by the partition according to tails

Tait coloring - for a planar cubic graph, a proper 3-edge-coloring

Tensor product - weak product

Terminal edge - a cut edge incident with an endvertex

Thickness

Threshold graph - having a threshold and a vertex weighting such that

Threshold dimension - minimum number of threshold graphs whose union is

Threshold function - a parametrized expression for probability in a sequence of random variables that almost ensures or almost forbids a property, depending on the value of the parameter

Topological minor - a graph for which a subdivision occurs as a subgraph of

Toroidal - 1) graph having a 2-cell embedding on the torus; 2) topological parameter on the torus in place of the plane (toroidal thickness, crossing number, etc.)

Torus - the (orientable) surface with one handle

Total coloring - a labeling of both the vertices and edges

Total domination number - minimum number of vertices such that

Total interval number - minimum of the total number of intervals used to represent

Total graph - the intersection graph of the sets in

Total order - chain

Totally unimodular - all square submatrices have determinant in {0,-1,+1}

Toughness - minimum

Tournament - an orientation of the complete graph

Traceable - having a Hamiltonian path

Trail - a walk in which no edge appears more than once

Trampoline - a split graph consisting of a clique on

Transitive - 1) for a digraph,

Transitive closure - 1) for a digraph

Transitive orientation - an orientation of an undirected graph that makes it a transitive digraph

Transposition - interchange of two elements in a permutation

Transportation problem - generalization of the assignment problem with supplies at each source and demands at each destination

Transversal - set of vertices meeting each edge of a hypergraph, sometimes

Transversal matroid - matroid on

Tree - a connected graph with no cycles

Triangle - a cycle of length 3; i.e.,

Triangle inequality -

Triangle-free - having no induced triangle

Triangulated - having no chordless cycle

Triangulation - a graph embedding on a surface such that every region is a 3-gon

Trivalent - 3-regular

Trivial - having no edges

Turán number - 1) for a specified hypergraph, -. 2) for parameters

Turán's theorem - charcterization of the complete equipartite

Tutte's Theorem - 1) characterization of graphs with 1-factors (also

Unforced pair - critical pair, minimal element of forcing relation

Unichain - in a product, a chain that is constant in one coordinate

Unicyclic - having exactly one cycle

Uniform matroid

Unimodal - a sequence such that

Unimodular - for matrices, having determinant 0, +1, or -1

Union 1) for graphs,

Unit interval graph - having a representation using intervals of the same length

Universally correlated - events positively correlated in every poset

Up-set - a dual ideal

Upper bound - 1) for elements in a poset, an element greater than or equal to all of them; 2) for a poset, an element dominating all others

Upper bound graph - undirected graph on the elements of poset such that vertices are adjacent if and only if the corresponding elements of the poset have a common upper bound

Upper extension of

Value - 1) for a flow, the net flow out of the source or into the sink; 2) for a matrix game, the best result that each player can guarantee

Van der Waerden number - minimum

Vectorial matroid - representable matroid

Vertex - element of

Vertex cut - a separating set of vertices

Vertex set

Vertex chromatic number - chromatic number

Vertex connectivity - connectivity

Vertex cover - a set of vertices containing at least one endpoint of every edge

Vizing's Theorem -

Voltage graph - a directed graph with edges labeled by elements of a group; used to study embeddings of a larger graph derived from the voltage graph.

Weak chain -

Weak order - a ranking

Weak order on

Weak product

Weakly connected - a directed graph whose underlying graph is connected

Weight - 1) a real number; 2) for a binary vector, the number of ones

Weighted - having an assignment of weights (to edges and/or vertices)

Wheel - a graph obtained by taking the join of a cycle and a single vertex

Whitney numbers (of the second kind) - rank sizes of poset

Whitney numbers of the first kind - coefficients of the characteristic polynomial

Width

XYZ inequality - the events

Young tableau - placement of the integers