Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland). 2039-2082 (1995).
The authors present a wide variety of applications of combinatorial reasoning in fields ranging from metric geometry to knot theory. The article consists of seven chapters, described in detail below. The topics covered give just a sampling of the applications of combinatorics in pure mathematics, yet provide a good impression of the breadth of combinatorial techniques that have proved useful in other fields. Definitions, proofs and examples are given sufficient to make the material easily accessible to non-specialists.
The first chapter concerns finite dimensional normed spaces. Arguments from extremal combinatorics are used to prove the existence of subspaces on which the norm is well-approximated by or isometric to the or norms, and whose dimensions exceed prescribed bounds. The second treats the problem of characterizing those by matrices which arise as matrices of mutual distances between finite sets of points in spaces. The set of such matrices forms a polyhedral cone , called the Hamming cone, and satisfy so-called hypermetric inequalities. The geometry of the hypermetric cone is related to multi-commodity flows on graphs and lattice-point-free ellipsoids. These connections provide non-trivial results toward a description of . The third section gives an application of matching theory to measure theory, presenting a simple proof of the existence of the Haar measure on a compact topological group using P. Hall’s Marriage Theorem.
The minimal degree of a group action of on is the smallest number of points moved by a non-trivial element of the group. This is the subject of the fourth chapter. The action on is modelled by a collection of digraphs called a coherent configuration. Elementary combinatorial arguments then lead to good lower bounds on the minimal degree.
The fifth section provides a nice introduction to combinatorial methods in commutative algebra. An algebra with straightening law is an algebra with a specified set of generators and a special kind of normal form algorithm. The algorithm is encoded by a partially-ordered set . Combinatorial properties of , such as shellability, can be used to prove that the algebra is Cohen-Macauley and to construct a particularly nice decomposition of , via the Stanley-Reisner ring of . The method is demonstrated with an analysis of the Grassmann variety in its Plücker embedding.
The next section outlines some of the applications of combinatorial methods in the theory of complex hyperplane arrangements. A finite set of hyperplanes or arrangement in is seen to be a realization of combinatorial structure in the form of a matroid. The matroid controls much of the topology and analytic geometry of the arrangement, allowing application of combinatorial tools such as the broken circuit complex. Included in this section are discussions of the cohomology algebra of the complement of a union of hyperplanes, the homotopy type of the complement and of the singularity link determined by an arrangement, arrangements whose matroids are supersolvable, uniform, or “2-generic”, and an extensive treatment of free arrangements.
The final section exposes the connection between the recently discovered polynomial invariants of knots and links and the classical Tutte polynomial of graph theory. A definition of the Jones polynomial is given in terms of Kauffman’s bracket polynomial on link diagrams, and is proven to be an isotopy invariant of links. In the case of an alternating knot or link, the Jones polynomial is shown to be a specialization of the Tutte polynomial of the graph obtained by 2-coloring the regions of the knot diagram, placing a vertex in each region, and connecting regions of the same color with an edge. The authors present a well-known application of the Jones polynomial in the proof of Tait’s conjecture on the number of crossings in alternating projections of an alternating link.