Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0851.52017
Lovász, László; Pyber, L.; Welsh, D.J.A.; Ziegler, G.M.
Combinatorics in pure mathematics. (English)
[A] Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland). 2039-2082 (1995). ISBN 0-444-88002-X/set; ISBN 0-444-82346-8/vol1; ISBN 0-444-82351-4/vol2; ISBN 0-262-07169-X/set; ISBN 0-262-07170-3/vol1; ISBN 0-262-07171-1/vol2

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.\par 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.\par 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 \times \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.\par 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.\par 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.\par 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.
[M.J.Falk (Flagstaff)]

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

Keywords: Hamming cone; multi-commodity flow; coherent configuration; Cohen-Macaulay ring; algebra with straightening law; Stanley-Reisner ring; shellability; hyperplane arrangement; matroid; Jones polynomial; Tutte polynomial; combinatorics; commutative algebra

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]