|
| THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |
1
By C(n,k) we denote the binomial
coefficient n!/(k!(n-k)!).
2
Two figures in the plane are congruent if one
can be transformed into the other by rotations and translations in
the plane.
3
A graph is three-connected if the removal of
any two vertices (and the adjacent edges) leaves a connected graph.
4
The prism of a graph G is formed by taking
two copies of G and adding a perfect matching whose edges join
corresponding copies of vertices.
5
A planar graph is one that can be embedded in the plane
without crossing edges. A plane graph is a planar graph that has
been embedded in the plane.
6 The square of a graph G, denoted G2, is the graph obtained from G by adding edges between vertices if they are at distance 2 in G. All of the original edges of G are present in G2.
7 A link is a finite collection of non-intersecting knots (where a knot is a closed, non-self-intersecting curve that is embedded in three dimensions; the trivial knot is a simple loop). A Brunnian link is a link which is non-trivial, yet every proper sub-collection is trivial. A trivial link is one that can be projected to a collection of non-intersecting circles in the plane.
8 A bipartite graph is one in which the vertices can be partitioned into two sets A and B where every edge is incident with a vertex from A and a vertex from B. The n-cube is bipartite, and thus so is the Venn dual.
9 A binary De Bruijn cycle of order n is a circular binary sequence of length 2n with the property that all length n subsequences are distinct.
10 The signed Gauss code of a link is composed of a series of entries for each curve in the link, one entry for each crossing. At each crossing the entry denotes which curve crosses which, whether the crossing is "over" or "under", and the "sign" of the crossing (which depends on the orientation of the curves involved). If a link's shadow is projected onto the plane the Gauss code will correspond to the Grünbaum encoding of the resulting diagram, as the sign of the crossings and the over/under information is ignored.
11 The Tutte embedding is a way of embedding a 3-connected planar graph in the plane with the property that all the faces are convex, and all edges are straight lines. Tutte proved in [Tu] that such an embedding can be constructed by starting with one face, making it convex, and then making every other vertex lie at the centre of gravity of its neighbours (i.e. each coordinate is the average of the neighbouring points' coordinates).
12 A Venn diagram is convex if all of its component curves are convex; a curve is convex if, for any two points inside the curve, a line between the two points is also inside the curve (i.e. the curve does not contain any "dents").
|
| THE ELECTRONIC JOURNAL OF COMBINATORICS (ed. June 2005), DS #5. |