Topological combinatorics

The title of this article is ambiguous. The mathematical subject, previously called combinatorial topology , can be found under algebraic topology

The topological combinatorics is a junior field of mathematics that has emerged in the last quarter of the 20th century and deals with the following types of problems:

1. Application of methods from topology to problems of discrete mathematics ,
2. topological generalizations of problems of discrete geometry ,
3. the discretization of topological concepts.

Topological combinatorics is thus to a certain extent a reversal of combinatorial topology, a subject that dealt with the application of combinatorial methods in topology and which was absorbed into algebraic topology at the beginning of the 20th century .

Topological combinatorics play an important role - among others - topics such as the topology of partial orders and simplicial complexes , collapsibility and peelability, theorems of the Borsuk-Ulam type and their combinatorial analogues, equivariant topology and obstacle theory.

Specific examples of the types of problems mentioned above are given below.

Application of methods from topology to problems of discrete mathematics

The proof of the Kneser conjecture by László Lovász in 1978 with the help of topological methods is generally regarded as the beginning of topological combinatorics. Martin Kneser published this assumption in the annual report of the DMV in 1955 in the form of a task.

Kneser's conjecture : In each partition of the -subset of a -set in classes there is a class that contains a disjoint pair of -sets. ${\displaystyle n}$ ${\displaystyle (2n+k)}$ ${\displaystyle k+1}$ ${\displaystyle n}$

This statement can easily be reformulated into a problem about the chromatic number of a certain family of graphs - the Kneser graphs . Lovász 'groundbreaking idea was to assign a simplicial complex , the so-called neighborhood complex , to each graph and to establish the following theorem. ${\displaystyle G}$ ${\displaystyle N(G)}$

Theorem (Lovász 1978): Let be a graph with a neighborhood complex . If the geometrical realization is topologically connected, then the graph cannot be colored. ${\displaystyle G}$ ${\displaystyle N(G)}$ ${\displaystyle N(G)}$ ${\displaystyle (k-1)}$ ${\displaystyle G}$ ${\displaystyle (k+1)}$

The core of the proof of this theorem is the Borsuk-Ulam theorem from algebraic topology . The proof that the neighborhood complexes of the Kneser graphs actually have the correct topological relationship is easily provided by a peelability argument - applied to the occurring partial orders (see for example).

The establishment of lower bounds for the chromatic number of a graph is of great importance in the research literature in this part of topological combinatorics. Further research activities deal with other problems in graph theory, partition results of point sets in Euclidean space and complexity results, for example for evasive graph properties and decision tree algorithms.

Similar to the way Brouwer's Fixed Point Theorem has its analog in discrete geometry in Sperner's Lemma (the derivation of Brouwer's Fixed Point Theorem from Sperner's Lemma was included in The Book of Proofs , Chapter 25), Borsuk-Ulam's theorem has an analog in Tucker's lemma (that is, one sentence follows from the other and vice versa).

Topological generalizations of discrete geometry problems

A topological generalization of Tverberg 's theorem, named after Helge Tverberg , about decompositions of point sets in Euclidean space and their convex hulls is the following.

Theorem (Murad Özaydin 1987, Karanbir Sarkaria 2000, Alexei Volovikov 1996). Be , a Primpotenz and . For every continuous mapping of the standard simplex in the there exist pairwise disjoint sides , so that the intersection is not empty. ${\displaystyle d\geq 1}$ ${\displaystyle q=p^{k}}$ ${\displaystyle N=(q-1)(d+1)}$ ${\displaystyle f\colon \Delta ^{N}\rightarrow \mathbb {R} ^{d}}$ ${\displaystyle N}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle q}$ ${\displaystyle \sigma _{1},\ldots ,\sigma _{q}\subset \Delta ^{N}}$ ${\displaystyle f(\sigma _{1})\cap \cdots \cap f(\sigma _{q})}$

The open question of whether this theorem also holds for the case that there is no prime power is known as the continuous Tverberg problem . The prime number case , i.e. the case , was shown by Imre Bárány , SB Shlosman and A. Szücs in 1981. The topological tool, which played the decisive role in their proof, essentially goes back to a theorem of Dold , which is a generalization of the theorem of Borsuk-Ulam. Dold's theorem became an extremely important and successful tool in topological combinatorics. ${\displaystyle q}$ ${\displaystyle k=1}$

Theorem ( Albrecht Dold 1983). Let be a non-trivial finite group, and be topological spaces with free -action. Furthermore, be -connected and the dimension of the same . If there is an -equivariant mapping from to , then . ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle (n-1)}$ ${\displaystyle Y}$ ${\displaystyle m}$ ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle m\geq n}$

Other areas of employment in this branch include problems of fair sharing and mass partition problems (this also includes the splitting Necklace theorem of Noga Alon ). These problems also touch algorithmic questions and involve discrete versions of sentences of the Borsuk-Ulam type.

Discretization of topological concepts

Discrete Morse Code is a discrete version of the Morse Code from the field of differentiable manifolds . Similar to Morse code theory, discrete Morse code theory considers functions that assign simplices to real values ​​under certain constraints. One application of the discrete Morse code is as follows.

Be a fixed amount. Identify a graph on the node set with the edge set . With the help of this identification, all graphs with sets of nodes that are not connected form a simplicial complex that we want to denote. For example, in Vassiliev's theory of knot invariants , it is important to study the topology of simplicial complexes that are associated with certain graph properties - such as -. ${\displaystyle V}$ ${\displaystyle n}$ ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle V}$ ${\displaystyle 2}$ ${\displaystyle \Delta _{n}^{2}}$ ${\displaystyle \Delta _{n}^{2}}$

Theorem ( Eric Babson et al. 1999, Victor Turchin 1997). For has the geometric realization of the homotopy type of a wedge of spheres of dimension . ${\displaystyle n\geq 3}$ ${\displaystyle \Delta _{n}^{2}}$ ${\displaystyle (n-2)!}$ ${\displaystyle 2n-5}$

In the course of the proof, Babson et al. a discrete Morse function with exactly one critical cell to show that the geometric realization of a certain simplicial complex is contractible. ${\displaystyle 0}$

The analogies between the continuous and the discrete Morse code are extensive. An important example of this is the following statement.

Theorem ( Robin Forman 1995). Assuming a simplicial complex with a discrete Morse function, then the geometrical realization of homotopy equivalent to a CW complex with exactly one cell of the dimension for each critical simplex of the dimension . ${\displaystyle \Delta }$ ${\displaystyle \Delta }$ ${\displaystyle p}$ ${\displaystyle p}$

Another important area of ​​research includes discretizations of the concept of curvature.

literature

• Jiří Matoušek : Using the Borsuk-Ulam Theorem. Lectures on Topological Methods in Combinatorics and Geometry. Springer-Verlag, Berlin et al. 2003, ISBN 3-540-00362-2 ( Universitext ).
• Mark de Longueville: A Course in Topological Combinatorics. Springer New York, 2012, ISBN 978-1441979094 ( university text ).
• Dmitry Kozlov : Combinatorial Algebraic Topology , Springer 2007

credentials

1. ↑ Martin Kneser. Exercise 360th Annual Report of the DMV, 58 (2): 27, 1955.
2. ↑ Mark de Longueville. 25 Years of Proof of the Kneser Conjecture - The Beginning of Topological Combinatorics pdf , DMV-Mitteilungen 4, 8 - 11, 2003.
3. ↑ Anders Björner. Topological Methods. In R. Graham, M. Grötschel, L. Lovász (Ed.), Handbook of Combinatorics . North Holland, Amsterdam, 1819-1872, 1994.
4. ↑ I. Bárány, SB Shlosman, A. Szucs On a topological generalization of a theorem of Tverberg , J. London Math. Soc. (2), Vol. 23, 1981, pp. 158-164
5. ^ Jiří Matoušek. Using the Borsuk-Ulam theorem. Lectures on topological methods in combinatorics and geometry. Written in collaboration with Anders Björner and Günter M. Ziegler. Universitext , Springer, Heidelberg, 2003.
6. ↑ Eric Babson, Anders Björner, Svante Linusson, John Shareshian, Volkmar Welker: Complexes of not i-connected graphs, Topology, Volume 38, 1999, pp. 271-299
7. ^ Turchin, Homology of Complexes of 2-Connected Graphs, Russ. Math. Surveys, Vol. 52, 1997, pp. 426-427.
8. ^ Forman, A discrete Morse theory for cell complexes, in: ST Yau (Ed.), Geometry, Topology & Physics for Raoul Bott, International Press, 1995.
9. ↑ Robin Forman. Combinatorial differential topology and geometry. In Louis Billera et al. (Ed.), New perspectives in algebraic combinatorics , Cambridge University Press, MSRI Publ. 38, 177-206, 1999.