Topological combinatorics
The Topological Combinatorics is a recent field of mathematics, which has emerged in the last quarter of the 20th century and deals with the following types of problems:
The topological combinatorics is to a certain extent a reversal of the combinatorial topology of a specialist area, which dealt with the application of combinatorial methods in topology and has risen in algebraic topology in the early 20th century.
An important role in topological combinatorics play - among other things - issues such as the topology of posets and simplicial complexes, collapsibility and ease of peeling, theorems of Borsuk - Ulam type and their combinatorial analogues, equivariant topology and obstruction theory.
Concrete examples of the types of problems mentioned above are listed below.
Applications 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 commonly regarded as the beginning of topological combinatorics. Martin Kneser published this conjecture in 1955 in the annual report of the DMV in the form of a task.
Kneser conjecture: In each partition of the subsets of a quantity in classes a class that contains a disjoint pair of sets exists.
This statement can be easily into a problem on the chromatic number of a certain family of graphs - the Kneser graphs - rephrase. Lovász ' breakthrough idea was, each graph a simplicial complex, called the neighborhood complex to associate and to establish the following theorem.
Theorem ( Lovász 1978): Let be a graph with neighborhood complex. If the geometric realization of topologically -connected, then the graph is non- colorable.
The core of the proof of this theorem is the Borsuk -Ulam theorem in algebraic topology. The proof that the neighborhood complexes of the Kneser graphs actually have the correct topological connection is easily accomplished by a Schälbarkeitsargument - applied to the emerging posets - provided (see example ).
The establishment of lower bounds for the chromatic number of a graph has a great importance in the research literature in this part of topological combinatorics. Other research activities deal with otherwise problems of graph theory, results of partition of point sets in Euclidean space and complexity results, such as evasive graph properties and decision tree algorithms.
Topological generalizations of problems in discrete geometry
A topological generalization of a theorem of Helge Tverberg about partitions 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 map of the standard - in pairs simplex in the exist disjoint sides, so that the average is not empty.
The open question of whether this theorem is true also for the case that no is Primpotenz is known as the continuous Tverberg problem. The prime case, so the case was shown by Imre Bárány, SB Shlosman and A. Szucs 1981. The topological tool which played a decisive role in their proof is essentially due to a set of Dold, which is a generalization of the Borsuk -Ulam theorem. Dolds theorem has become a very important and successful tool in the topological combinatorics.
Theorem (Albrecht Dold 1983). Be a non-trivial finite group, and ( sufficiently nice ) topological spaces with a free action. It should also be discontinuous and the dimension of the same. If a - equivariant mapping from to exist, the following applies.
Other areas of employment in this subarea include problems of fair sharing and mass partition problems ( this also includes the splitting theorem of Noga Alon Necklace ). These problems also affect algorithmic problems and include discrete versions of the Borsuk -Ulam theorem sets type.
Discretization of topological concepts
Discrete Morse theory is a discrete version of Morse theory in the field of differentiable manifolds. Similar to Morse theory functions are considered in the discrete Morse theory, assign the simplices real values under certain constraints. An application of the discrete Morse theory is as follows.
Be a fixed amount. Identify a graph on the vertex set with the set of edges. With the help of this identification form all graphs with vertex set that are non- contiguous, a simplicial complex, which we denote by. For example, in Vassiliev's theory of knot invariants, it is of importance, the topology of simplicial complexes which are associated with certain graph properties - study - such as.
Theorem (Eric Babson et al. 1999, Victor Turchin 1997). For, the geometric realization of the homotopy type of a wedge of spheres of dimension.
In the course of the proof Babson et al construct. to show a discrete Morse function with exactly one critical cell to that the geometric realization of a certain simplicial complex is contractible.
The analogies between the continuous and discrete Morse theory are far-reaching. An important example is the following statement.
Theorem (Robin Forman 1995). Assumed is a simplicial complex to a discrete function Morse, then the geometric realization of homotopy equivalent to a CW complex having exactly one cell in the dimension for each of the simplex critical dimension.
Another important area of research includes discretization of the curvature term.