Topological combinatorics
Encyclopedia
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.
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 v1,...,vk∈ V(G), and k positive integers n1,n2,...,nk that sum up to |V(G)|, there exists a partition {V1,...,Vk} of V(G) such that vi∈ Vi, |Vi|=ni and Vi spans a connected subgraph.
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 Aanderaa–Karp–Rosenberg conjecture. Other areas include topology of partially ordered sets
and bruhat order
s.
Also methods from differential topology
now have a combinatorial analog in discrete Morse theory.
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
and in the early 20th century this gradually turned into the field of algebraic topology
Algebraic topology
Algebraic topology is a branch of mathematics which uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify up to homotopy equivalence.Although algebraic topology...
.
In 1978 the situation was reversed when methods from algebraic topology were used to solve a problem in combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
when László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
proved the Kneser conjecture
Kneser graph
In graph theory, the Kneser graph is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are connected if and only if the two corresponding sets are disjoint...
, 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
Fair division
Fair division, also known as the cake-cutting problem, is the problem of dividing a resource in such a way that all recipients believe that they have received a fair amount...
problems.
In another application of homological methods to graph theory Lovász proved both the undirected and directed versions of a conjecture of Frank
András Frank
András Frank is a Hungarian mathematician, working in combinatorics, especially in graph theory, and combinatorial optimisation...
: Given a k-connected graph G, k points v1,...,vk∈ V(G), and k positive integers n1,n2,...,nk that sum up to |V(G)|, there exists a partition {V1,...,Vk} of V(G) such that vi∈ Vi, |Vi|=ni and Vi spans a connected subgraph.
The most notable application of topological combinatorics has been to graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
problems.
Also in 1987 the necklace problem
Necklace problem
The necklace problem is a problem in recreational mathematics, solved in the early 21st century.- Formulation :Suppose that a person you are in contact with has a necklace of n beads, each of which is either black or white. You wish to identify the order in which the n beads go around the...
was solved by Noga Alon
Noga Alon
Noga Alon is an Israeli mathematician noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.- Academic background :...
. It has also been used to study complexity problems
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
in linear decision tree algorithms
Decision tree
A decision tree is a decision support tool that uses a tree-like graph or model of decisions and their possible consequences, including chance event outcomes, resource costs, and utility. It is one way to display an algorithm. Decision trees are commonly used in operations research, specifically...
and the Aanderaa–Karp–Rosenberg conjecture. Other areas include topology of partially ordered sets
Poset topology
In mathematics, the poset topology associated with a partially ordered set S is the Alexandrov topology on the poset of finite chains of S, ordered by inclusion.Let V be a set of vertices...
and bruhat order
Bruhat order
In mathematics, the Bruhat order is a partial order on the elements of a Coxeter group, that corresponds to the inclusion order on Schubert varieties.-History:The Bruhat order on the Schubert varieties of a flag manifold or Grassmannian...
s.
Also methods from differential topology
Differential topology
In mathematics, differential topology is the field dealing with differentiable functions on differentiable manifolds. It is closely related to differential geometry and together they make up the geometric theory of differentiable manifolds.- Description :...
now have a combinatorial analog in discrete Morse theory.
See also
- Sperner's lemmaSperner's lemmaIn mathematics, Sperner's lemma is a combinatorial analog of the Brouwer fixed point theorem, which follows from it. Sperner's lemma states that every Sperner coloring of a triangulation of an n-dimensional simplex contains a cell colored with a complete set of colors...
- Discrete exterior calculusDiscrete exterior calculusIn mathematics, the discrete exterior calculus is the extension of the exterior calculus to discrete spaces including graphs and finite element meshes. DEC methods have proved to be very powerful in improving and analyzing finite element methods: for instance, DEC-based methods allow the use of...
- Topological graph theoryTopological graph theoryIn mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, spatial embeddings of graphs, and graphs as topological spaces. It also studies immersions of graphs....
- Combinatorial topologyCombinatorial topologyIn mathematics, combinatorial topology was an older name for algebraic topology, dating from the time when topological invariants of spaces were regarded as derived from combinatorial decompositions such as simplicial complexes...
- Finite topological spaceFinite topological spaceIn mathematics, a finite topological space is a topological space for which the underlying point set is finite. That is, it is a topological space for which there are only finitely many points....