The discipline of
combinatorial topology used combinatorial concepts in topology and in the early 20th century this turned into the field of
algebraic topology. In 1978 the situation was reversed—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 field 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
András Frank: Given a
k-connected graph G,
k points v_1,\ldots,v_k \in V(G), and
k positive
integers n_1,n_2,\ldots,n_k that sum up to |V(G)|, there exists a partition \{V_1,\ldots,V_k\} of V(G) such that v_i \in V_i, |V_i|=n_i, and V_i spans a connected subgraph. 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. Additionally, methods from
differential topology now have a combinatorial analog in
discrete Morse theory. ==See also==