# zbMATH — the first resource for mathematics

##### Examples
 Geometry Search for the term Geometry in any field. Queries are case-independent. Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact. "Topological group" Phrases (multi-words) should be set in "straight quotation marks". au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted. Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff. "Quasi* map*" py: 1989 The resulting documents have publication year 1989. so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14. "Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic. dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles. py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses). la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 any anywhere an internal document identifier au author, editor ai internal author identifier ti title la language so source ab review, abstract py publication year rv reviewer cc MSC code ut uncontrolled term dt document type (j: journal article; b: book; a: book article)
Combinatorics in pure mathematics. (English) Zbl 0851.52017
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 ${\ell }_{1}$ or ${\ell }_{\infty }$ norms, and whose dimensions exceed prescribed bounds. The second treats the problem of characterizing those $n$ by $n$ matrices which arise as matrices of mutual distances between finite sets of points in ${L}_{1}$ spaces. The set of such matrices forms a polyhedral cone ${H}_{n}$, 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 ${H}_{n}$. 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 $G$ on ${\Omega }$ 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 $G$ on ${\Omega }×{\Omega }$ 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 $A$ with a specified set of generators and a special kind of normal form algorithm. The algorithm is encoded by a partially-ordered set $P$. Combinatorial properties of $P$, such as shellability, can be used to prove that the algebra is Cohen-Macauley and to construct a particularly nice decomposition of $A$, via the Stanley-Reisner ring of $P$. 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 ${C}^{\ell }$ 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.

##### MSC:
 52B40 Matroids (convex geometry) 52C35 Arrangements of points, flats, hyperplanes 57Q45 Knots and links in high dimensions (PL-topology) 05B35 Matroids, geometric lattices (combinatorics)