Topological combinatorics
The discipline of combinatorial topology used combinatorial concepts in topology and in the early 20th century this gradually turned into the field of algebraic topology.
In 1978 the situation was reversed when methods from algebraic topology were used to solve a problem in combinatorics when László Lovász proved the Kneser conjecture, thus beginning the new study of topological combinatorics.
Lovász's proof used the Borsuk-Ulam theorem and this theorem retains a prominent role in this new field. This theorem has many equivalent versions and analogs and has been used in the study of fair division problems.
The most notable application of topological combinatorics has been to graph coloring problems. Also in 1987 the necklace problem was solved by Noga Alon. It has also been used to study complexity problems in linear decision tree algorithms and the evasiveness conjecture. Other areas include topology of partially ordered sets and bruhat orders.
Also methods from differential topology now have a combinatorial analog in discrete Morse theory.
See also
References
- de Longueville, Mark (2004), "25 years proof of the Kneser conjecture - The advent of topological combinatorics" (PDF), EMS Newsletter, Southampton, Hampshire: European Mathematical Society, pp. 16–19, retrieved 2008-07-29
{{citation}}:|format=requires|url=(help); Cite has empty unknown parameters:|coeditors=and|coauthors=(help).
Further reading
- Trends in Topological Combinatorics
- Combinatorial Curvatures, Group Actions, and Colourings: Aspects of Topological Combinatorics
- Matoušek, Jiří (2003). Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry. Springer. ISBN 978-3540003625.
- Graham, Ronald L., Grötschel, Martin, and Lovász, László (1995). Handbook of Combinatorics Volume 2. The MIT press. ISBN 978-0262071710.
{{cite book}}: CS1 maint: multiple names: authors list (link) - Kozlov, Dmitry (2007). Combinatorial Algebraic Topology. Springer. ISBN 978-3540719618.