Combinatoire topologique

La combinatoire topologique est un domaine mathématique de la combinatoire qui applique des méthodes topologiques et algébrico-topologiques à la résolution de problèmes en combinatoire.

Description

La topologie combinatoire a utilisé des concepts combinatoires en topologie ; au début du 20^e siècle, elle est devenue progressivement le domaine de la topologie algébrique.

En 1978, la situation s'est inversée, et des méthodes de topologie algébrique ont été utilisées pour résoudre un problème en combinatoire, lorsque László Lovász a prouvé la conjecture de Kneser, initiant ainsi une nouvelle forme de la combinatoire topologique. La preuve de Lovász a utilisé le théorème de Borsuk-Ulam et ce théorème continue à conserver un rôle de premier plan dans ce nouveau domaine. Ce théorème a de nombreuses versions équivalentes et des énoncés analogues et a été utilisé dans l'étude des problèmes de partage équitable .

La démarche de la combinatoire topologique peut être caractérisée par un schéma que de nombreuses preuves dans ce domaine utilisent : pour prouver un problème combinatoire par des moyens topologiques, on effectue les étapes suivantes :

1. Associer une fonction continue d'un espace topologique dans la structure discrète donnée, comme un homomorphisme de graphes.
2. Établir une relation entre les invariants topologiques appropriés de l'espace, par exemple la dimension, la k-connectivité, les groupes d'homologie, et les caractéristiques combinatoires souhaitées de la structure d'origine.
3. Montrer que l'espace ou la fonction associée possède les propriétés topologiques souhaitées.

Applications

Dans une autre application des méthodes homologiques à la théorie des graphes, Lovász a prouvé les versions non orientées et orientées d'une conjecture d'András Frank : Étant donné un graphe k-connexe G à n sommets, k sommets distingués $v_{1},\ldots ,v_{k}$, et k entiers positifs $n_{1},n_{2},\ldots ,n_{k}$ de somme n, il existe une partition $\{V_{1},\ldots ,V_{k}\}$ des sommets de $G$ telle que $v_{i}\in V_{i}$, $|V_{i}|=n_{i}$, et $V_{i}$ couvre un sous-graphe connexe.

En 1987, le problème du partage d'un collier a été résolu par Noga Alon en utilisant le théorème de Borsuk-Ulam. Il a également été utilisé pour étudier les problèmes de complexité dans les algorithmes d'arbres de décision linéaires et la conjecture d'Aanderaa-Karp-Rosenberg. D'autres domaines incluent la topologie des ensembles partiellement ordonnés et des ordres de Bruhat.

De plus, les méthodes de topologie différentielle ont maintenant un analogue combinatoire dans la théorie Morse discrète.

Depuis que des théorèmes combinatoires ont été prouvés par des méthodes topologiques, la question naturelle qui se pose est de chercher à remplacer l'argument topologique par un argument combinatoire. Une première percée dans ce sens a été faite par Jiří Matoušek en 2000 avec une preuve combinatoire de la conjecture de Kneser, article paru en 2004

Notes et références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Topological combinatorics » (voir la liste des auteurs).

Bibliographie

• Anders Björner, « Topological Methods », dans Ronald L. Graham, Martin Grötschel, László Lovász (éditeurs), Handbook of Combinatorics (vol. 2), The MIT press, 1995 (ISBN 978-0-262-07171-0)
• Dmitri Kozlov, Combinatorial Algebraic Topology, Springer-Verlag, 2007 (ISBN 978-3-540-71961-8)
• Jiří Matoušek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry, Springer-Verlag, 2003 (ISBN 978-3-540-00362-5)
• Jonathan Barmak, Algebraic Topology of Finite Topological Spaces and Applications, Springer-Verlag, 2011 (ISBN 978-3-642-22002-9)
• Mark de Longueville, A Course in Topological Combinatorics, Springer-Verlag, 2011 (ISBN 978-1-4419-7909-4)

Articles liés

• Lemme de Sperner
• Théorie topologique des graphes
• Topologie combinatoire
• Espace topologique fini