Topological methods.

*(English)*Zbl 0851.52016
Graham, R. L. (ed.) et al., Handbook of combinatorics. Vol. 1-2. Amsterdam: Elsevier (North-Holland). 1819-1872 (1995).

This article concerns applications of topological results in the solution of combinatorial problems. The chapter is written in two parts – the first gives many examples of this approach while the second collects all the necessary background material and relevant theorems from combinatorial topology. The arguments in the first part are sketched in varying degree of detail, with frequent references to Part II for the necessary topological theory. Apart from a few references to other chapters in the handbook, the article is entirely self-contained.

The examples in Part I fall into a few different types. The first applications are to evasive graph properties, fixed points of order-preserving maps, and Kneser’s conjecture, that any partition of the \(n\)-subsets of a \((2n + k)\)-element set into \(k + 1\) classes has a class with two disjoint sets. In each case, a simplicial complex is identified whose topological structure reflects the combinatorial situation. Then theorems from algebraic topology are invoked to yield the desired topological, hence combinatorial, conclusions. The next group of applications has a more geometric flavor, involving partitions of finite sets in \(R^n\) and their convexity properties. Typical is the “Tverberg problem”, that any set of \((p-1) (d + 1) + 1\) points in \(R^d\) can be partitioned into \(p\) blocks whose convex hulls have a point in common. This and similar combinatorial/geometric propositions are seen to follow from topological arguments, some quite sophisticated, along the lines of the Borsuk-Ulam Theorem and its corollaries. In some cases, the topological method has led to proofs of results more general than those originally conceived.

The next applications come from matroid theory. The motivating example is a topological proof by L. Lovasz of a conjecture concerning colorings of \(k\)-connected graphs. The methods rely only on the underlying matroid or greedoid structure – these notions are defined in the paper. Here the topology and combinatorics become more intertwined. Simplicial complexes arising naturally are shown to be simply-connected. As a consequence, combinatorial moves of certain types (for instance, on the bases of a greedoid, or the copoints of a geometric lattice) are seen to be composed of a few elementary moves, allowing case-by-case proof that some operation is well-defined. An example of this method is Tutte’s characterization of regular matroids by forbidden minors, using his “homotopy theorem for matroids”. The author sketches Tutte’s argument “in the briefest possible fashion”.

The author proceeds to a definition of oriented matroids and a sketch of the proof of the topological representation theorem of Folkman and Lawrence. This result shows that oriented matroids are the “same thing” as arrangements of tamely embedded codimension one spheres in \(S^n\). The topological view is exploited to give several quick proofs of nontrivial combinatorial properties of oriented matroids. There is also a sketch of the well-definition of basis signatures on oriented matroids using the homotopy method of the preceding section.

Part I closes with a survey of applications of the hard Lefschetz theorem of algebraic geometry to combinatorics, including a discussion of the role of this theorem in Stanley’s proof of the Erdös-Moser conjecture and a sketch of the proof of the characterization of \(f\)-vectors of simplicial polytopes.

The second part contains the topological details needed for most of the arguments discussed in Part I. The general approach is to view a simplicial complex as a partially ordered set, and, conversely, to associate to a poset its simplicial complex of chains. This section provides a compendium of topological results tailored for combinatorial applications, quite comprehensive, with most proofs deferred to other references. It is an excellent, and unique, resource for this diverse collection of material.

For the entire collection see [Zbl 0833.05001].

The examples in Part I fall into a few different types. The first applications are to evasive graph properties, fixed points of order-preserving maps, and Kneser’s conjecture, that any partition of the \(n\)-subsets of a \((2n + k)\)-element set into \(k + 1\) classes has a class with two disjoint sets. In each case, a simplicial complex is identified whose topological structure reflects the combinatorial situation. Then theorems from algebraic topology are invoked to yield the desired topological, hence combinatorial, conclusions. The next group of applications has a more geometric flavor, involving partitions of finite sets in \(R^n\) and their convexity properties. Typical is the “Tverberg problem”, that any set of \((p-1) (d + 1) + 1\) points in \(R^d\) can be partitioned into \(p\) blocks whose convex hulls have a point in common. This and similar combinatorial/geometric propositions are seen to follow from topological arguments, some quite sophisticated, along the lines of the Borsuk-Ulam Theorem and its corollaries. In some cases, the topological method has led to proofs of results more general than those originally conceived.

The next applications come from matroid theory. The motivating example is a topological proof by L. Lovasz of a conjecture concerning colorings of \(k\)-connected graphs. The methods rely only on the underlying matroid or greedoid structure – these notions are defined in the paper. Here the topology and combinatorics become more intertwined. Simplicial complexes arising naturally are shown to be simply-connected. As a consequence, combinatorial moves of certain types (for instance, on the bases of a greedoid, or the copoints of a geometric lattice) are seen to be composed of a few elementary moves, allowing case-by-case proof that some operation is well-defined. An example of this method is Tutte’s characterization of regular matroids by forbidden minors, using his “homotopy theorem for matroids”. The author sketches Tutte’s argument “in the briefest possible fashion”.

The author proceeds to a definition of oriented matroids and a sketch of the proof of the topological representation theorem of Folkman and Lawrence. This result shows that oriented matroids are the “same thing” as arrangements of tamely embedded codimension one spheres in \(S^n\). The topological view is exploited to give several quick proofs of nontrivial combinatorial properties of oriented matroids. There is also a sketch of the well-definition of basis signatures on oriented matroids using the homotopy method of the preceding section.

Part I closes with a survey of applications of the hard Lefschetz theorem of algebraic geometry to combinatorics, including a discussion of the role of this theorem in Stanley’s proof of the Erdös-Moser conjecture and a sketch of the proof of the characterization of \(f\)-vectors of simplicial polytopes.

The second part contains the topological details needed for most of the arguments discussed in Part I. The general approach is to view a simplicial complex as a partially ordered set, and, conversely, to associate to a poset its simplicial complex of chains. This section provides a compendium of topological results tailored for combinatorial applications, quite comprehensive, with most proofs deferred to other references. It is an excellent, and unique, resource for this diverse collection of material.

For the entire collection see [Zbl 0833.05001].

Reviewer: M.J.Falk (Flagstaff)

##### MSC:

52B40 | Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) |

05B35 | Combinatorial aspects of matroids and geometric lattices |

57M15 | Relations of low-dimensional topology with graph theory |