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. La topologie combinatoire a utilisé des concepts combinatoires en topologie ; au début du , 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 : Associer une fonction continue d'un espace topologique dans la structure discrète donnée, comme un homomorphisme de graphes. É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. Montrer que l'espace ou la fonction associée possède les propriétés topologiques souhaitées. 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 , et k entiers positifs de somme n, il existe une partition des sommets de telle que , , et 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.