Glossary of Terms in Combinatorics
This glossary (rather old and out-of-date) accompanies a web site of
Open Problems in Graph Theory and Combinatorics.
The glossary collects terms and gives quick reminders of definitions,
too abbreviated in most cases to give full introduction.
An attempt has been made to list standard notations.
Typically, G denotes a graph, D a directed
graph, H a graph or hypergraph, P a poset, L a lattice,
M a matroid. Also u, . . .,z are vertices or elements, uv
is an edge, n is the number of vertices or elements, and e is an
edge or (as a function) is the number of edges. The set of the first n
natural numbers is denoted [n].
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".
Abstract dual - a graph whose cycles correspond to the bonds of the original
graph
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 P-symbol
Adjacency matrix A - entry i,j is number of edges from vertex i to
vertex j (symmetric if graph is undirected)
Adjacency set N(v) - the set of vertices adjacent to v
Adjacent - vertices joined by an edge ("<-> " means "is
adjacent to", "\nadj " means "is not adjacent to")
Advance - for a permutation σ, a value x such that
σ-1(x)<σ-1(x+1)
Affine - 1) for a vector space, ...; 2) for a geometry, ...;
3) for a lattice
Ahlswede-Daykin inequality - if α,β,γ,δ are
non-negative functions satisfying
α(x)β(y) ≤ γ(x∧y)δ(x∨y) for all
x,y∈L,
then α(X)β(Y) ≤ γ(X∧Y)δ(X∨Y)
for all X,Y⊆L, where f(X)=∑x∈Xf(x)
Algebraic dependence - satisfies a polynomial with coefficients over a field
Almost always - having probability asymptotic to 1
α-critical - deletion of any edge increases the independence number
Alteration principle - the two-step randomization in probabilistic methods
Alternating cycle - in a poset, a collection of k incomparable pairs
(x1,y1),...,(xk,yk) such that
yi ≤ xi+1 for all i (modulo k);
they cannot occur together in an extension
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 V(H) whose edges are the sets intersecting
each edge of H at most once
Antichain - set of pairwise incomparable elements
Anticlique - stable set
Antihole - induced subgraph whose complement is Ck for some k ≥ 4
Antisymmetric relation - (x,y),(y,x)∈R imply x=y
Arborescence - a directed forest in which every vertex has out-degree at most
one
Arboricity Υ(G) - minimum number of forests covering the edges of G
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 σ, a value i such that σ(i)<σ(i+1)
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 Γ - the group of automorphisms, under composition
Balanced k-partite - having part-sizes differing by at most one (see
equipartite)
Balanced graph - among subgraphs, average vertex degree is maximized by the
full graph
δ-Balanced comparison - a pair of incomparable elements such that
x < y in a fraction between δ and 1-δ of the
linear extensions
Ballot list - list of n 0s and n 1s in which each prefix has at least as
many 0s as 1s
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 [n]
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
β-perfection - for each induced subgraph H,
ω(H) α(H) ≥ n(H)
Biadjacency matrix - matrix recording the edges of a bipartite graph
Bicentral tree - a tree with two vertices in its center
X,Y-bigraph - bipartite graph with partite sets X,Y
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 k of n distinct objects
Binomial sequence - sequence of polynomials, pn of degree n, with
pn(x+y)=∑k=0n{n\choose k}pk(x)pn-k(y)
k-binomial expansion - expression of an integer as
∑i=jk {mi\choose i} with
mk > . . . >mj
Bidimension - (also biorder dimension) Ferrers dimension: minimum number
of biorders whose intersection is D
Bijection - function that yields each element of its target exactly once
Binomial Theorem - (x+y)n≥∑k≥0 {n\choose k}xkyn-k
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 G, the minimum n such that
2-coloring the edges of Kn,n forces a monochromatic G
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 k-sets from a v-set such that every pair of
elements appears together λ times
Block graph - intersection graph of the blocks
Block-cutpoint graph - bipartite graph on the blocks and cut-vertices of
G where adjacency represents membership
Board (forbidden positions) - set of positions in a grid
Bond - a minimal edge cut
Bond space - cocycle space
Book embedding - a decomposition of G into outerplanar graphs with a
consistent ordering of the vertices (as on the spine of a book)
Boolean algebra - a common name for the subset lattice
Boolean function - function from subset lattice to {0,1} (False/True)
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 G is the intersection graph of boxes
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 H (usually a cycle), a component of G-H together
with the edges to its vertices of attachment
Brooks' Theorem - χ(G) ≤ Δ(G), except for cliques and odd cycles
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
Cactus - a graph in which every edge appears in at most one cycle
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 G1\cart G2 - graph with
V(G)1)×V(G)2) as vertices, having
(u1,u2)<-> (v1,v2) if 1)
u1=v1 and u2<-> v2
in G2 or 2) u2=v2 and
u1<-> v1 in G1
Cartesian product P×Q - poset with {(p,q): p∈P,q∈Q}
as elements, having (p,q) ≤ (p',q') if and only if p ≤ p' in P and
q ≤ q' in Q
Catalan numbers Cn= {2n\choose n}/(n+1) - sequence with
C0=1 and Cn=∑i=1n
Ci-1Cn-i, solution for many counting problems such as
ballot lists
Caterpillar - tree with one path (the spine) containing or incident to every
edge
Cayley graph - given a group Γ and a set S of generators, this is graph
with vertex set Γ defined by u<-> v if u=gv or u=g-1v for some
g∈S
Cayley's formula - there are nn-2 labeled trees on n vertices
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
δ-central element - an element belong to between δ and 1-δ of the
ideals
Centroid - for a region in Rn, the vector whose
ith coordinate is ∫xidV / ∫dV
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 φ - 1) for a graph, the
characteristic polynomial of the adjacency matrix (roots are the eigenvalues);
2) for a poset, the generating function of the Möbius function by co-rank
Characteristic roots - roots of the characteristic equation
Characteristic vector - indexed by the elements of a universe, records the
characteristic function for a set
χ -bounded - family with chromatic number bounded by a function of clique
number
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 [n] to one of its members
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 χ - 1) minimum number of colors in a proper coloring.
2) for a surface, the minimum k such that all graphs embeddable on it are
k-colorable).
Chromatic polynomial χ (G;λ) - a polynomial whose value at an integer
λ=k is the number of proper colorings of G using any or all of colors
1,...,k.
k-chromatic - having chromatic number k
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 Δ(G)
Class 2 - simple graph with chromatic index Δ(G)+1
Claw - the graph K1,3
Claw-free - having no induced claw
Clique - 1) a pairwise adjacent set of vertices; 2) a complete (sub)graph
Clique cover number \theta - 1) minimum number of cliques to cover V(G).
2) sometimes used for minimum number of cliques to cover E(G) (intersection
number)
Clique number ω - maximum size of a clique in G
Clique partition number - minimum number of cliques to partition E(G)
Clique tree - minimal representation of a chordal graph as an intersection
graph of subtrees of a tree
Clique-vertex incidence matrix - entry (i,j) is 1 if vertex j belongs to
maximal clique i, otherwise 0
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 G
Code - a set of binary vectors
Coding polynomial - used to encode messages in a polynomial code
k-cofamily - a family containing no k+1-element antichain
Cograph - a graph with no induced P4
Cointerval graph - complement of an interval graph
Colexicographic order - x < y if xii in
the last place where they differ
k-colorable - chromatic number ≤ k
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 P-symbol
by reading columns in order
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
k-coloring - a partition of the vertices into k independent sets
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 - x < y or y < x
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 D by u<-> v if
u,v have a common out-neighbor in D
Complement \ov{G} (or Gc) - 1) for graphs, the graph with the same
vertices as G and u<-> v in Gc iff u\nadj v in G; 2) for digraphs,
u -> v in Dc iff u\nadj v in D
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 - m by n bipartite graph with mn edges
Complete digraph - for every pair v,w of vertices, at least one of vw
and wv appears as an arc
Complete graph Kn - every pair of the n vertices is adjacent
Complete k-partite graph Kn1,...,nk - k-partite graph in which
every pair of vertices not belonging to the same part is adjacent (part-sizes
are n1,...,nk)
Complete matching - edge set of a 1-factor
Complete r-uniform hypergraph - hypergraph having vertex partition into r
sets so that edges are the sets consisting of one vertex from each partite set
Complete symmetric digraph - every ordered pair of vertices is an edge (once)
Component - maximal connected subgraph
Composition G1[G2] - graph whose vertex set is the cartesian product of the
vertex sets of the factors, with (u1,u2)<-> (v1,v2) if and only if
u1<-> v1 in G1, or
u1=v1 and u2<-> v2 in G2
Conditional probability Prob(A|B) - probability of the intersection divided
by the probability of B
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 n - related pairs of integers are those differing
by a multiple of n
Conjugate partition - partition whose Ferrers diagram is transpose of Ferrers
diagram of original partition
Connected - 1) for graphs and digraphs, having a (u,v)-path for every pair of
vertices u,v; 2) for posets, having a connected comparability graph; 3) for
matroids, each pair of elements lies in a circuit
k-connected - having connectivity ≥ k
k-connected component - a maximal k-connected subgraph
Connection coefficients - matrix to convert between expansions in terms
of various binomial sequences
Connectivity κ(G) - the minimum number of vertices whose deletion
disconnects the graph (sometimes called "vertex connectivity" for clarity)
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 f(x) assigned to elements x
by x < y if f(x)⊂f(y)
Contraction - 1) a graph obtained by a sequence of elementary contractions;
2) contraction of matroid M to F is the matroid on F whose spanning sets
are the subsets of F that together with \Fb are spanning in M
Converse D-1 - u -> v in D-1 iff v -> u in D
Convex family - intersection of an ideal and a dual ideal
Convex polyhedron - the set of points satisfying a set of linear
inequalities in Rd
Convex polytope - the set of convex combinations of a finite set of points in
Rd
Convex property - holds for all objects between two objects where it holds
Convolution - 1) for sequences < a >,< b >, new sequence given by
ck=∑iaibk-i; 2) for incidence functions f,g, new function given
by h(x,y)=∑x≤z≤yf(x,z)g(z,y)
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
E(XY) ≥ E(X)E(Y) or Prob(A∩B) ≥ Prob(A)Prob(B)
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 N
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 (x,y) such that
y covers x
Covering problem - in hypergraphs, find the minimum number of edges in H
that cover V(H)
Covers - y covers x if x<y in a poset and no element is between them
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(G) - minimum number of edge crossings in a drawing of
G in the plane
k-cube - graph with vertex set {0,1}k, defined by u<-> v if and only
if u and v differ in exactly one place
Crown - the poset with elements i,i' for 1≤i≤n+k
related by i||j' for i≤j≤i+k (modulo (n+k))
and otherwise i<j'
Cryptomorphism - map from one aspect of a matroid to another
Cubic graph - a regular graph of degree 3
Cubicity - minimum dimension in which G is the intersection graph of cubical boxes
Cut [S,\ov{S}] - the edges from S to \Sb
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
v1,...,vn of maximum over j of
the number of edges joining vertices earlier than vj
to vertices later than vj in the ordering
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
k-cycle - a cycle of length k, i.e., consisting of k vertices
and k edges
Cycle double cover conjecture - a bridgeless graph has a collection of cycles
together covering each edge exactly twice
Cycle matroid - for graph G, the matroid on E(G) whose circuits are the
cycles in G
Cycle rank - dimension of cycle space; |E(G)|-|V(G)|+k for graph G with k
components
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 k-edge-connected - cyclic edge-connectivity at least k
Decomposition - an expression of G as an edge-disjoint union
of subgraphs
Decomposition number - minimum size of a decomposition of G using subgraphs
in a specified class
Defect - for a partial transversal, the number of sets not represented
Deficiency - for a set in a bipartite graph, min{0,|Y|-|N(Y)|}
Degree d(v) - 1) for a vertex, the number of edges containing it (loops count
once or twice, depending on context); 2) for a regular graph, the degree of each
vertex; 3) for a face of an embedding, the length of the boundary; 4) for a
poset element, its degree in the comparability graph
Degree-majorization - one degree sequence degree-majorizes another if
it dominates it; i.e., the ith largest entry in the first is at least
as large as the corresponding entry in the second, for all i
Degree sequence d1 ≥ . . . ≥ dn - the list of
vertex degrees, usually in nonincreasing order
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
t-design - a family of k-sets from a v-set such that every t-set of
elements appears together λ times
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 w(P) chains
Dilworth's Theorem - a poset of width k has a covering by k chains
Dimension - for posets, order dimension
k-dimension - minimum number of chains of size k in whose product P
embeds
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 G1+G2 - the union of two graphs with disjoint
vertex sets (or the union of posets with disjoint sets of elements)
Distance d(u,v) - the minimum number of edges (arcs) in a (u,v)-path
Distribution models - classical enumeration problems for objects in boxes
Distributive lattice - a lattice in which x∧ (y∨ z) =
(x∧ y)∨ (x∧ z) for all x,y,z
Division algorithm - finds quotient and remainder
Domain - set on which a function is defined
Dominance ordering - ordering on partitions in which μ ≤ λ if
every partial sum in μ is at most the corresponding partial sum in λ
Domination number - the minimum size of a dominating set of vertices
Dominating set - a set S⊆ V such that every vertex outside S has
a neighbor in S
Double shift graph - graph on triples of numbers from [n] such that
i,j,k is adjacent to l,m,n if i < j < k and l < m < n and (j,k)=(l,m)
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 G* - for a plane graph, the graph with a vertex for each
region of G, in which vertices are adjacent if the boundaries of the
corresponding regions of G share an edge (also makes sense for 2-cell
embeddings on any surface)
Dual poset P* - obtained by reversing all the relations
Dual program - a special linear (or integer) program bounding the original
optimization problem
Dual matroid M* - the bases are the complements of the bases of M
Dual ideal - an ideal in the dual of P
Duplication of vertices - adding a vertex whose neighborhood is that of the
vertex duplicated
Ear - maximal path such that internal vertices have degree 2
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 (E(G) denotes the edge set).
2) in a hypergraph, a subset of the vertices
Edge chromatic number χ' - the minimum number of colors in a proper
edge-coloring
Edge color class - the edges assigned a given color in a proper edge coloring
k-edge colorable - edge chromatic number ≤ k
Edge coloring - an assignment of labels to the edges
k-edge connected - edge connectivity ≥ k
Edge connectivity κ'(G) - minimum number of edges whose deletion
disconnects G
Edge cover - a set of edges incident to all the vertices
Edge cut [S,\ov{S}] - the set of edges joining a vertex in S to
a vertex not in S
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
EKR(k,t)-family - antichain of sets in which all have size at most k
and pairs have at least t common elements
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
k-error detecting - a code with minimum distance k+1
k-error correcting - a code with minimum distance 2k+1
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
k in an intersecting family is the collection of k-sets containing a
single element, if k ≤ n/2
Euclidean algorithm - procedure for extracting greatest common denominator
of a and b and expressing it as an integer combination of a and b
Euler characteristic χ - alternating sum of number of faces of each
dimension in a simplicial complex
Euler totient - number of elements in [n] relatively prime to [n]
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-γ surface, 2-2γ
Euler's formula - the formula n-m+f=2-2γ for any 2-cell embedding
of a connected n-vertex graph with m edges and f faces
on a surface of genus γ
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, X⊆ σ(X)
Expectation - for random variable X taking integer values, ∑ kProb(X=k)
Exponential generating function - formal power series expressing a sequence
{an} as ∑ anxn/n!
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
Face - a region of an embedding
Factor - a spanning subgraph
k-factor - a regular spanning subgraph of degree k
k-factorable - having a k-factorization
Factor-critical - graph where each single-vertex-deleted subgraph has a
1-factor
Factorial n! - ∏i=1n i
Factorization - an expression of G as the edge-disjoint union of spanning
subgraphs
Falling factorial n(k) -
∏i=0k-1 (n-i)
Family - a collection of elements in a poset
k-family - a family containing no k+1-chain
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
k-factorization - a decomposition of a graph into k-factors
Feasible flow - a network flow satisfying edge-constraints and having net
flow 0 at each vertex
Fermat's Little Theorem - if a is an integer not divisible by a prime
p, then ap-1-1 is divisible by p
Ferrer's diagram - an arrangement of unit squares with λi left-justified
positions in the ith row, where λ is a partition of n
Ferrer's digraph - a digraph with no x,y,z,w (not necessarily distinct) such
that x -> y and z -> w but failure of both z -> y and x -> w; equivalently, the
successor sets or predecessor sets are ordered by inclusion; equivalently, the
adjacency matrix has no 2 by 2 permutation submatrix.
Fibonacci numbers - sequence with F0=0,
F1=1, Fn=Fn-1+Fn-2 for
n ≥ 2
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 - {((a,b),(c,d))} such that c < d in every
extension having a < b
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
H-Free - a graph not containing H as an induced subgraph
Free matroid - uniform matroid of rank |E|
Fundamental cycle - for a spanning tree, a cycle formed by adding an edge to it
Gammoid - a matroid induced on a subset of the vertices of a digraph
Generalized partition matroid - a direct sum of uniform matroids
Genus γ - 1) for a surface, the number of handles in its topological
description; 2) for a graph, the minimum genus surface on which it embeds
Geodesic - a shortest path between its endpoints
Geodetic - a graph in which each pair of vertices u,v are the endpoints
of a unique path of length d(u,v)
Geometric lattice - a semimodular lattice without infinite chains in which
every element is a join of atoms
Girth g - the length of the shortest cycle in G
k-gon - in an embedding, a k-cycle bounding a region
k-gon order - a containment order of a collection of k-gons in the plane
Good coloring - often means proper coloring
Graceful labeling - injective vertex labeling from {0,...,|E(G)|} such
that the differences between the labels on endpoints of edges form
1,...,|E(G)|
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 r(G1,...,Gk) - the minimum n such that
coloring the edges of Kn forces an i-monochromatic copy of Gi for some i
Greatest lower bound x∧ y - a lower bound of x and y that is
greater than any other lower bound of x and y
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 P
Greedy extension - linear extension such that xk+1 covers xk if some
minimal element of the subposet induced by xk+1,...,xn covers xk
Greene-Kleitman Theorem - for every poset and every k, there is a chain
partition that is both k and k+1-saturated
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
Hadamard matrix - an n-by-n matrix with entries in {+1,-1} 1
whose product with its transpose is n times the identity
Hadwiger conjecture - a k-chromatic graph has a subgraph contractible to Kk
(true for "almost all" graphs)
Hajós conjecture - a k-chromatic graph has a subgraph
homeomorphic to Kk (false for k≥7)
Halin graph - obtained from a planar embedding of a tree by adding a
cycle through the leaves in order
Hall's Condition - 1) |N(S)| ≥ |S| for all S⊆ X;
2) |∪i∈I Ai}| ≥ |I| for all
I⊆ [m]
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 γ handles is at most
⌊½(7+√{1+48γ})⌋.
Height - size (or one less than size) of largest chain in poset (or having
x at the top
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 k such that the sets in F have
a common intersection if every k sets of F have a common intersection
Hereditary class - a class F for which every subgraph of a graph in F
is also in F
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 E, may be specified by an
order ideal I, the antichain of maximal elements of I, the antichain of
minimal elements not in I, a rank function r, a span function σ, or
other "aspects"
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 f: V(G) -> V(H) that preserves adjacency
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
Ideal I - a collection of elements such that x ≤ y∈I implies x∈I
Idempotence - f2=f, where f is a function
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 fg
defined by fg(x,y)=∑x≤z≤yf(x,z)g(z,y)
Incidence matrix - the matrix in which entry (i,j) is 1 if vertex
j belongs to edge i, and 0 if not (for a digraph, 1 if vertex
j is the head of edge i, -1 if it is the tail, 0 otherwise)
Incident - 1) for a vertex v and edge e, v belongs to e.
2) edges are incident if they intersect
Incomparable x||y - neither x < y nor y < x
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 α - maximum size of an independent set of vertices
Independent domination number - minimum size of an independent dominating set
Independent events - Prob(A∩B)=Prob(A)Prob(B)
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
u<-> v if and only if |f(u)-f(v)| ≤ 1
Induced sub(di)graph (GA or G[A]) - the sub(di)graph on vertex set
A⊂V obtained by taking all edges of the original graph that join two
vertices in A
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
S-intersecting family - a family whose pairwise intersections have sizes
only in S
t-intersecting family - a family whose pairwise intersections have size at
least t
Intersection - 1) for posets P,Q on the same set, the poset
on that set having x ≤ y if and only if x ≤ y in both P and Q;
2) for matroids, the hereditary system whose independent sets are the sets
independent in both matroids
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 G is an intersection
graph of subsets of it (equals minimum number of cliques covering edges)
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 t such that G (or P) has a t-interval
representation
Interval order - a poset representable by real intervals such that
x < y if and only if Ix is completely to the left of
Iy.
Interval representation - a collection of intervals whose intersection graph
is G (or that represent P)
t-Interval representation f - a mapping f:V(G) ->
R such that each image consists of at most t intervals and
v<->w iff f(v)∩ f(w)≠∅
Inversion - 1) a pair of elements k,l in a permutation σ of [n] such
that σ(i)=k and σ(j)=l with k,l in the opposite order to i,j
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 V(G) into V(H)
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.
Jeu de Taquin - procedure of reducing a skew tableau to a column-strict tableau
Join G∨ H - a graph combination obtained by taking disjoint copies of
G,H and putting u<->v for every u∈V(G),v∈V(H)
Join x∨ y - the least upper bound
Joined to - adjacent to
Kempe chain - a path alternate between two colors
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 m k-sets having the minimum
k-1-shadow is the first m k-sets in the reverse lexicographic order
Kuratowski's theorem - a graph is planar if and only if it has no subgraph
homeomorphic to K5 or K3,3
Labeling - a mapping to the integers
Latin square - an n by n arrangement of n copies each of n symbols,
such that each symbol appears exactly once in each row and column
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 +1 in one coordinate
Leaf - an endvertex of a tree
Least upper bound x∧ y - an upper bound of x and y that
is less than any other upper bound of x and y
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 (n)
Lexicographic product - composition
Line - another name for edge
Line graph L(G) - the intersection graph of the edges of G, i.e.
vertices correspond to edges of G and are adjacent if the corresponding edges
intersect
Linear code - a code f in which message words and codewords belong to vector
spaces, f(x+y)=f(x)+f(y), and f(ax)=af(x)
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 n variables, subject to linear constraints
q-Linear matroid - matroid whose independent sets are representable as the
sets of independent columns of a matrix over a field of q elements
Link - edge
k-linked - a stronger condition than k-connected, in which for
every choice of two k-tuples of vertices (u1,...,uk) and
(v1,...,vk), there exists a set of k internally disjoint
paths connecting corresponding vertices ui,vi.
Locally finite - every interval has finitely many elements
Log-concave sequence - ak2 ≥ ak+1ak-1
Log-supermodular function - μ(x∧ y)μ(x∨ y) ≥ μ(x)μ(y)
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 Q⊂P - an extension of Q such that
x>y whenever x∈Q, y∈P-Q, and x||y
Lower semimodular lattice - y\prec x∨ y implies x∧ y\prec x for all
x,y
Lucas numbers - satisfy the Fibonacci recurrence and have
L1=1 and L2=3.
LYM inequality - the sum of reciprocals of rank-sizes is at most 1
LYM property - every antichain satisfies the LYM inequality
Majorization - for random variables, Prob(G>r) ≥ Prob(H>r) for all
r
Martingale - sequence of random variables in which the expectation of Xi
given the values of X1,...,Xi-1 is the value of Xi-1
Matching - a set of pairwise disjoint edges in a graph or hypergraph
b-matching - given a constraint vector b, a subgraph H with
dH(v) ≤ b(v) for all v
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 G as cofactor of the
matrix D-A(G)
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 M1 and M2 on E is the
minimum of r1(X)+r2(E-X) over sets X⊆E
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 of the vertex degrees
Maximum flow - a feasible flow of maximum value, or the value of such a flow
Maximum genus γM(G) - the maximum genus of a surface on
which G is 2-cell-embeddable
Meet x∧ y - the greatest lower bound
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 δ(G) - minimum of the vertex degrees
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 ζ in the incidence algebra,
defined on intervals of P by μ(x,x)=1 and
μ(x,y)=-∑x≤z<yμ(x,z)
Möbius inversion formula - generalization of inclusion-exclusion to
posets, in which f is obtained from g satisfying
g(x)=∑y≤xf(y) by
f(x)=∑y≤xg(y)μ(y), where μ(y) is the
value μ(0,y) for the Möbius function of the poset
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 - x∧ (y∨ z)=(x∧ y)∨ z whenever z ≤ x
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
Nash equilibrium - optimal strategies for players in a matrix game
Neighbors - (noun) the vertices adjacent to a given vertex; (verb) "is
adjacent to"
Neighborhood N(v) - if "open," same as adjacency set; if
"closed," then includes in addition the vertex itself (and notation
becomes N[v])
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 A at rank k with
shadow A* at rank k+1, |A*|/Nk+1 ≥ |A|/Nk
Null graph - graph having no vertices
Odd anti-hole - complement of an odd hole
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 P
Ordered set - partially ordered set
Order-reversing - a function from the elements of one ordered set to another
such that x ≤ y implies f(x) ≥ f(y)
Order polynomial - value at k counts the order-preserving functions from P
to [k]
Order polytope - the order-preserving functions from a poset to the interval
[0,1], viewed as a subset of R|P|
Order-preserving - a function from the elements of one ordered set to another
such that x ≤ y implies f(x) ≤ f(y)
Ordinal sum P⊕ Q - a poset obtain from the disjoin union P+Q by
placing each element of Q above each element of P
Ordinary generating function - formal power series expressing <a> as
∑ anxn
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 number - the maximum number of something findable in a graph without
violating some condition such as pairwise disjointness, nonadjacency, etc.
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 u,v,
(u,v)-paths of all lengths at least d(u,v)
Pancylic - having cycles of all lengths at least 3
Parallel edges - multiple edges
Parallel elements - circuits of size two in a matroid
k-partite - having a vertex partition into k parts such that no edges
join vertices in the same part; same as k-colorable
Partial extension - an extension of a poset, usually not a linear extension
Partially ordered set P=(X,R) - formally, a set of elements X and binary
order relation R that is reflexive, antisymmetric, and transitive
Partite set - what are usually called the "parts" in a k-partite graph
Partition matroid - matroid with independent sets being those with at most
one element in each block of a given partition of E
Partitionable graph - G such that for any x∈V(G), G-x is partitionable
into α(G) cliques of size ω(G) and into ω(G) stable sets of size α(G)
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)
(u,v)-path - a path with u and v as endpoints
Pattern inventory - a generating function in many variables in which the
coefficient of xjej is the number of patterns in which type j appears
with weight ej
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 - same as perfect
γ-perfect - a graph whose complement is perfect
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 n-by-n matrix, the sum over all collections of n
independent positions of the product of the entries in those positions
Permutation graph - representable by a permutation σ such that
vi<->vj if and only if σ reverses the
order of i and j
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
kth-power (Gk) - the graph on the same vertices as G in which vertices
are joined by an edge if G has a walk of length k thbetween them
Predecessor - for v in a digraph, a vertex u with u -> v
Predecessor set - for v in a digraph, the set of precedessors
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 G
as an induced subgraph
Projective plane - n2+n+1 points and n2+n+1 lines with each two points on
one common line and each two lines having one common point
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 n-2 obtained by
successively deleting the leaf with smallest label and recording its neighbor's
label
Pseudograph - graph model with both loops and multiple edges permitted
Radius - the minimum eccentricity of the vertices
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 p of adjacency;
typically, p=1/2 or p is a function of n
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 X; 3) for a
hypergraph, gives largest size of an edge contained in S
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
i,j is 1 if there is a path from vertex i to vertex j, otherwise 0
Realizer - a collection of extensions whose intersection is P
Reciprocity theorem - in general, a relationship between two functions
f,f' stating f'(n,k)=(-1)nf(n,-k)
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 R, having xRx for all x
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 k cover the same number of elements and be
covered by the same number of elements, for all k; 3) for a matroid,
being representable as a linear matroid over any field.
Regular covering - nonempty list of maximal chains such that every element
appears as often as as every other element in its rank
k-regular - having all vertex degrees equal k
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 M to elements F is the matroid
on F whose independent sets are the subsets of F independent in M
Reverse lexicographic order - x < y if
xi<yi in last component where they differ
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 [n] to pairs of Young tableaux on n elements having the same
shape; extended by Knuth beyond permutations
Saturated arc - for a network flow, an arc in which the flow equals
the capacity
k-Saturated partition - a partition whose k-norm equals the largest size
of a k-family
Saturated vertex - 1) for a matching, a matched vertex.
2) for a b-matching, a vertex with b(v) incident edges.
Score sequence - the sequence of outdegrees in a tournament
k-scrambling - a family of sets where any k yield a Venn diagram with all
cells nonempty
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 P×Q, a collection in which comparable pairs must
differ in both coordinates
Semi-strong perfect graph theorem - intermediate between the perfect graph
theorem and strong perfect graph theorem, concerns the P4-structure of
a graph
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") x∧ y\prec x
implies y\prec x∨ y for all x,y
Semiorder - a poset representable by a function f and threshold δ such
that x < y if and only if f(x) < f(y)-δ
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 n such that deleting at most that many vertices from a graph
in the class splits the remaining vertices in a balanced way
k-Shadow - for a family F, the set of elements with rank k that are
related to elements of F
Shannon capacity - limit of kth root of independence number
of kth power of graph
Signed (di)graph - special case of weighted (di)graph, assinging + or - to
each edge
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 n-person game in which every subset of players is winning
or losing, equivalent to an order-preserving function on Bn
Simplex - 1) method for solving linear programs; 2) the convex hull of d+1
nondegenerate points in a d-dimensional metric space
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 σ(X) - in hereditary systems and matroids, X together with
the elements that complete circuits with elements of X
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
k-Sperner property - having a maximum k-family consisting of the union
of k ranks
Sperner's lemma - a properly labeled simplicial decomposition of a simplex
has a completely labeled fundamental simplex
Sperner's theorem - Bn has the Sperner property
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 (K1,n-1);
2) in hypergraphs (or families of sets), a collection all containing a single
vertex (element)
Steiner triple system - block design using blocks of size 3
Steinitz(-Maclane) exchange property - for a set function σ,
e∉ σ(X) and e∈σ(X∪ f) imply f∈σ(X∪ e)
Stirling's formula - n!=nne-n√{2πn}(1+o(1))
Stirling number (of the second kind) S(n,k) - counts partitions of [n] into
k blocks
Stirling numbers of the first kind s(n,k) - the number of permutations of
[n] with k cycles, multiplied by (-1){n-k}
Strict chain - x1 < x2< . . . < xn
Strict correlation - Prob(A|B)>Prob(A)
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 Sn - σ\prec τ if τ is obtained from σ by
transposing any pair of elements to increase the number of inversions
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 G1⋅G2 - a graph product with vertex set
V(G1)× V(G2) and edge set (u1,v1)<-> (u2,v2) if
u1=u2 or u1<-> u2 and
v1=v2 or v1<-> v2
Strong Sperner property - k-Sperner for all k
Strongly connected - digraph having a (u,v)-path for each ordered pair
(u,v) of vertices
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 G
Sublattice - a subposet of a lattice that is a lattice and inherits meets and
joins from the full lattice
Submodular function - r(x∧ y)+r(x∨ y) ≤ r(x)+r(y)
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 u in a digraph, a vertex v with u -> v
Successor set - for u in a digraph, the set of successors
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 G is a subgraph
Supermodular function - r(x∧ y)+r(x∨ y) ≥ r(x)+r(y)
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 u -> v iff v -> u (equivalent to an undirected graph);
3) for a binary relation R, having xRy iff yRx
Symmetric chain - in a poset of rank n, meeting ranks j and n-j for
some set of indices j
Symmetric chain decomposition - partition of P into symmetric consecutive
chains
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 - the first vertex of an edge in a digraph
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 θG - the minimum number of planar graphs whose union
(G) G
Threshold graph - having a threshold and a vertex weighting such that
u\nadj v iff w(u)+w(v) ≤ t
Threshold dimension - minimum number of threshold graphs whose union is G
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 G
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 G as the intersection graph of unions of intervals on the real line
Total graph - the intersection graph of the sets in V(G)∪ E(G), for some
G
Total order - chain
Totally unimodular - all square submatrices have determinant in {0,-1,+1}
Toughness - minimum t such that |S| ≥ tc(G-S) for all S⊆ V(G),
where c(G-S) is the number of components of G-S
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 x1,...,xk, a stable
set on y1,...,yk, and the edges yixi and yixi+1 (cyclically) for
all i
Transitive - 1) for a digraph, uw must be an arc whenever uv and vw
are arcs. 2) for a group action, such as the automorphism group acting on the
vertice set, the existence of a group operator mapping each element to any other
Transitive closure - 1) for a digraph D, the digraph with u -> w whenever
there is a path from u to w in D; 2) for a relation R, the relation S
with xSy whenever there is a sequence x0,...,xk with
x=x0Rx1R . . . Rxk=y
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 E whose independent sets are the partial
systems of distinct representatives of a fixed set system on E
Tree - a connected graph with no cycles
Triangle - a cycle of length 3; i.e., K3
Triangle inequality - d(x,y)+d(y,z) ≥ d(x,z)
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 n,k,b,
Turán's theorem - charcterization of the complete equipartite r-partite
graphs as the largest graphs of a given order with no r+1-clique
Tutte's Theorem -
1) characterization of graphs with 1-factors (also f-factors);
2) 3-connected planar graphs have embeddings with all bounded faces convex;
3) characterization of 3-connected graphs by contractions to wheels.
Underlying graph - the undirected graph obtained by removing the orientation
from the edges of a directed graph
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
k-Uniform hypergraph - having each edge of size k
Uniform matroid Uk(n) - has as bases all k-sets of the n-element ground
set
Unimodal - a sequence such that a1 ≤ . . . ≤ ak ≥ ak+1 ≥ . . . ≥ n
for some k
Unimodular - for matrices, having determinant 0, +1, or -1
Union 1) for graphs, G1∪ G2 is a graph whose vertex set is the union
of the vertices in G1 and G2 and whose edge set is the union of the
edges in G1 and G2 (written G1+G2 if the vertex sets are
disjoint); 2) for matroids, M1∪ M2 is the matroid whose independent sets
are the unions of independent sets in M1 and M2
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 Q⊂P - an extension of Q such that
x < y for all x∈Q, y∈P-Q, x||y
Valence - degree
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 [n] such that k-colorings of the
integers [n] must have a monochromatic arithmetic sequence with l terms
Vectorial matroid - representable matroid
Vertex - element of V(G), the vertex set
Vertex cut - a separating set of vertices
Vertex set V(G) - the set of elements on which the graph is defined
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 - χ'(G)≤Δ(G)+1 for graphs;
χ'(G)≤Δ(G)+μ(G) for multigraphs, where μ(G) is
the maximum multiplicity of an edge
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.
Walk - a sequence of vertices and edges in a graph such that
each vertex belongs to the edge before and after it (in a digraph, must follow
arrows)
Weak chain - x1 ≤ x2 ≤ . . . ≤ xn
Weak order - a ranking
Weak order on Sn - σ\prec τ if τ is obtained from σ
by transposing adjacent elements to increase the number of inversions
Weak product G1⊗ G2 - a graph product with vertices
V(G1)× V(G2), and edges (u1,v1)<-> (u2,v2) iff u1<-> u2
and v1<-> v2
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 w(P) - size of largest antichain
X-join - lexicographic product
XYZ inequality - the events x < y and x < z are positively correlated (in
any poset)
Young lattice - lattice of partitions of all integers, ordered componentwise
Young tableau - placement of the integers [n] in the positions of a Ferrers
diagram so that entries are increasing in every row and column
Zeta function - incidence function defined by ζ(x,y)=1 for all x≤y