Topological combinatorics

The discipline of combinatorial topology mainlh deals with the application of topology to combinatorics. Many of its applications lie in graph theory.

History

In the early 20th centuey, researchers used combinatorial concepts in topology, befinning the field of algebraic topology. In 1978, 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.

In another application of homological methods to graph theory Lovász proved both the undirected and directed versions of a conjecture of Frank: Given a k-connected graph G, k points v₁,...,v_k∈ V(G), and k positive integers n₁,n₂,...,n_k that sum up to |V(G)|, there exists a partition {V₁,...,V_k} of V(G) such that v_i∈ V_i, |V_i|=n_i and V_i spans a connected subgraph.

Applications

In 1987 the necklace splitting problem was solved by Noga Alon using the Borsuk-Ulam theorem. It has also been used to study complexity problems in linear decision tree algorithms and the Aanderaa–Karp–Rosenberg conjecture. Other areas include topology of partially ordered sets and bruhat orders.

Connection to other areas

Additionally, methods from differential topology now have a combinatorial analog in discrete Morse theory.

See also

• Sperner's lemma
• Discrete exterior calculus
• Topological graph theory
• Combinatorial topology
• Finite topological space

References

• de Longueville, Mark (2004). "EMS Newsletter". Southampton, Hampshire: European Mathematical Society: 16–19. Retrieved 2008-07-29. {{cite journal}}: |contribution= ignored (help); |format= requires |url= (help); Cite has empty unknown parameters: |coeditors= and |coauthors= (help); Cite journal requires |journal= (help).

Further reading

• Björner, Anders (1995), "Topological Methods", in Graham, Ronald L.; Grötschel, Martin; Lovász, László (eds.), Handbook of Combinatorics (PDF), vol. 2, The MIT press, ISBN 978-0-262-07171-0.
• Kozlov, Dmitry (2005), Trends in topological combinatorics, arXiv:math.AT/0507390.
• Kozlov, Dmitry (2007), Combinatorial Algebraic Topology, Springer, ISBN 978-3-540-71961-8.
• Lange, Carsten (2005), Combinatorial Curvatures, Group Actions, and Colourings: Aspects of Topological Combinatorics (PDF), Ph.D. thesis, Berlin Institute of Technology.
• Matoušek, Jiří (2003), Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer, ISBN 978-3-540-00362-5.
• Barmak, Jonathan (2011), Algebraic Topology of Finite Topological Spaces and Applications, Springer, ISBN 978-3-642-22002-9.
• de Longueville, Mark (2011), A Course in Topological Combinatorics, Springer, ISBN 978-1-4419-7909-4.