Combinatoire polyédrique - Polyhedral combinatorics

La combinatoire polyédrique est une branche des mathématiques , au sein de la combinatoire et de la géométrie discrète , qui étudie les problèmes de comptage et de description des faces des polyèdres convexes et des polytopes convexes de dimension supérieure .

La recherche en combinatoire polyédrique se divise en deux domaines distincts. Les mathématiciens de ce domaine étudient la combinatoire des polytopes ; par exemple, ils recherchent des inégalités qui décrivent les relations entre les nombres de sommets , d' arêtes et de faces de dimensions supérieures dans des polytopes arbitraires ou dans certaines sous-classes importantes de polytopes, et étudient d'autres propriétés combinatoires des polytopes telles que leur connectivité et leur diamètre (nombre de étapes nécessaires pour atteindre n'importe quel sommet à partir de n'importe quel autre sommet). De plus, de nombreux informaticiens utilisent l'expression «combinatoire polyédrique» pour décrire la recherche de descriptions précises des faces de certains polytopes spécifiques (en particulier les polytopes 0-1, dont les sommets sont des sous-ensembles d'un hypercube ) résultant de problèmes de programmation en nombres entiers .

Visages et vecteurs de comptage de visages

Une face d'un polytope convexe P peut être définie comme l'intersection de P et d'un demi-espace fermé H tel que le bord de H ne contienne aucun point intérieur de P . La dimension d'une face est la dimension de cette coque. Les faces à 0 dimension sont les sommets eux-mêmes, et les faces à 1 dimension (appelées arêtes ) sont des segments de ligne reliant des paires de sommets. Notez que cette définition inclut également comme faces l'ensemble vide et le polytope entier P . Si P a lui-même la dimension d , les faces de P de dimension d  − 1 sont appelées facettes de P et les faces de dimension d  − 2 sont appelées arêtes . Les faces de P peuvent être partiellement ordonnées par inclusion, formant un réseau de faces qui a pour élément supérieur P lui-même et pour élément inférieur l'ensemble vide.

Un outil clé en combinatoire polyédrique est le vecteur d'un polytope, le vecteur ( f ₀ , f ₁ , ..., f _{d  − 1} ) où f _i est le nombre de caractéristiques i- dimensionnelles du polytope. Par exemple, un cube a huit sommets, douze arêtes et six facettes, donc son vecteur ƒ est (8,12,6). Le polytope double a un vecteur avec les mêmes nombres dans l'ordre inverse ; ainsi, par exemple, l' octaèdre régulier , le dual d'un cube, a le vecteur (6,12,8). Les matrices de configuration incluent les vecteurs f des polytopes réguliers comme éléments diagonaux.

Le vecteur étendu est formé en concaténant le nombre un à chaque extrémité du vecteur , en comptant le nombre d'objets à tous les niveaux du réseau de faces ; du côté gauche du vecteur, f _-1  = 1 compte l'ensemble vide comme un visage, tandis que du côté droit, f _d  = 1 compte P lui-même. Pour le cube, le vecteur étendu est (1,8,12,6,1) et pour l'octaèdre, il est (1,6,12,8,1). Bien que les vecteurs de ces exemples de polyèdres soient unimodales (les coefficients, pris dans l'ordre de gauche à droite, augmentent jusqu'à un maximum puis diminuent), il existe des polytopes de dimension supérieure pour lesquels ce n'est pas vrai.

Pour les polytopes simpliciaux (polytopes dans lesquels chaque facette est un simplexe ), il est souvent pratique de transformer ces vecteurs, produisant un vecteur différent appelé le vecteur h . Si nous interprétons les termes du vecteur ƒ (en omettant le dernier 1) comme des coefficients d'un polynôme ƒ( x ) = Σ f _i x ^{d  −  i  − 1} (par exemple, pour l'octaèdre cela donne le polynôme ƒ( x ) =  x ³  + 6 x ²  + 12 x  + 8), alors le vecteur h liste les coefficients du polynôme h ( x ) = ƒ( x  − 1) (encore une fois, pour l'octaèdre, h ( x ) =  x ³  + 3 x ²  + 3 x  + 1). Comme l'écrit Ziegler, "pour divers problèmes concernant les polytopes simpliciaux, les vecteurs h sont un moyen beaucoup plus pratique et concis d'encoder les informations sur les numéros de visage que les vecteurs ".

Égalité et inégalités

La relation la plus importante entre les coefficients du vecteur d'un polytope est la formule d'Euler (−1) ⁱ f _i = 0, où les termes de la somme s'étendent sur les coefficients du vecteur étendu. En trois dimensions, déplacer les deux 1 aux extrémités gauche et droite du vecteur étendu (1, v , e , f , 1) vers le côté droit de l'équation transforme cette identité en la forme plus familière v − e + f = 2. Du fait que chaque facette d'un polyèdre tridimensionnel a au moins trois arêtes, il s'ensuit en comptant deux fois que 2 e 3 f , et en utilisant cette inégalité pour éliminer e et f de la formule d'Euler conduit à la autres inégalités e 3 v − 6 et f ≤ 2 v − 4. Par dualité, e 3 f − 6 et v ≤ 2 f − 4. Il résulte du théorème de Steinitz que tout vecteur entier de dimension 3 satisfaisant ces égalités et inégalités est le vecteur d'un polyèdre convexe.

Dans les dimensions supérieures, d'autres relations entre les nombres de faces d'un polytope deviennent également importantes, notamment les équations de Dehn-Sommerville qui, exprimées en termes de h -vecteurs de polytopes simpliciaux, prennent la forme simple h _k = h _{d − k} pour tout k . L'instance de ces équations avec k = 0 est équivalente à la formule d'Euler mais pour d > 3, les autres instances de ces équations sont linéairement indépendantes les unes des autres et contraignent les vecteurs h (et donc aussi les vecteurs ƒ) de manières supplémentaires.

Une autre inégalité importante sur le nombre de faces des polytopes est donnée par le théorème de la borne supérieure , prouvé pour la première fois par McMullen (1970) , qui stipule qu'un polytope de dimension d avec n sommets peut avoir au plus autant de faces de n'importe quelle autre dimension qu'un polytope voisin avec le même nombre de sommets :

${\displaystyle f_{k-1}\leq \sum _{i=0}^{d/2}{}^{*}\left({\binom {di}{ki}}+{\binom {i }{k-d+i}}\right){\binom {nd-1+i}{i}},}$

où l'astérisque signifie que le terme final de la somme doit être divisé par deux lorsque d est pair. Asymptotiquement, cela implique qu'il y a au plus des faces de toutes dimensions. ${\displaystyle \scriptstyle O(n^{\lfloor d/2\rfloor })}$

Même en quatre dimensions, l'ensemble des ƒ-vecteurs possibles de polytopes convexes ne forme pas un sous-ensemble convexe du réseau entier à quatre dimensions, et beaucoup reste inconnu sur les valeurs possibles de ces vecteurs.

Propriétés de la théorie des graphes

En plus d'étudier le nombre de faces des polytopes, les chercheurs ont étudié d'autres propriétés combinatoires de ceux-ci, telles que les descriptions des graphes obtenus à partir des sommets et des arêtes des polytopes (leur 1-squelette ).

Le théorème de Balinski indique que le graphe obtenu de cette manière de tout d de dimension convexe polytope est -à- d -vertex connecté . Dans le cas des polyèdres tridimensionnels, cette propriété et cette planéité peuvent être utilisées pour caractériser exactement les graphes de polyèdres : le théorème de Steinitz énonce que G est le squelette d'un polyèdre tridimensionnel si et seulement si G est un 3-sommet connecté graphique planaire.

Un théorème de Blind & Mani-Levitska (1987) (précédemment conjecturé par Micha Perles ) déclare que l'on peut reconstruire la structure de la face d'un polytope simple à partir de son graphe. C'est-à-dire que si un graphe non orienté donné est le squelette d'un polytope simple, il n'y a qu'un seul polytope (à équivalence combinatoire près) pour lequel cela est vrai. Ceci contraste fortement avec les polytopes voisins (non simples) dont le graphe est un graphe complet ; il peut y avoir plusieurs polytopes voisins différents pour le même graphe. Une autre preuve de ce théorème basée sur des orientations de puits uniques a été donnée par Kalai (1988) et Friedman (2009) a montré comment utiliser ce théorème pour dériver un algorithme en temps polynomial pour reconstruire les réseaux de faces de polytopes simples à partir de leurs graphes. Cependant, tester si un graphe ou un réseau donné peut être réalisé comme le réseau de faces d'un polytope simple est équivalent (par polarité) à la réalisation de polytopes simpliciaux , ce qui s'est avéré complet pour la théorie existentielle des réels par Adiprasito & Padrol ( 2014) .

Dans le contexte de la méthode du simplexe pour la programmation linéaire , il est important de comprendre le diamètre d'un polytope, le nombre minimum d'arêtes nécessaires pour atteindre n'importe quel sommet par un chemin à partir de n'importe quel autre sommet. Le système d' inéquations linéaires d'un programme linéaire définit les facettes d'un polytope représentant toutes les solutions réalisables du programme, et la méthode du simplexe trouve la solution optimale en suivant un chemin dans ce polytope. Ainsi, le diamètre fournit une limite inférieure sur le nombre d'étapes que cette méthode nécessite. La conjecture de Hirsch , maintenant réfutée, suggérait une forte limite sur la taille du diamètre. Des limites supérieures plus faibles (quasi-polynomiales) sur le diamètre sont connues, ainsi que des preuves de la conjecture de Hirsch pour des classes spéciales de polytopes.

Propriétés de calcul

Décider si le nombre de sommets d'un polytope donné est limité par un nombre naturel k est un problème de calcul difficile et complet pour la classe de complexité PP .

Facettes de 0-1 polytopes

Il est important dans le contexte des méthodes de plan de coupe pour la programmation en nombres entiers de pouvoir décrire avec précision les facettes des polytopes qui ont des sommets correspondant aux solutions des problèmes d'optimisation combinatoire. Souvent, ces problèmes ont des solutions qui peuvent être décrites par des vecteurs binaires , et les polytopes correspondants ont des coordonnées de sommet qui sont toutes égales à zéro ou à un.

A titre d'exemple, considérons le polytope de Birkhoff , l'ensemble de n  ×  n matrices qui peuvent être formées à partir de combinaisons convexes de matrices de permutation . De manière équivalente, ses sommets peuvent être considérés comme décrivant tous les appariements parfaits dans un graphe bipartite complet , et un problème d'optimisation linéaire sur ce polytope peut être interprété comme un problème d'appariement parfait bipartite de poids minimum. Le théorème de Birkhoff-von Neumann stipule que ce polytope peut être décrit par deux types d'inégalité ou d'égalité linéaire. Premièrement, pour chaque cellule de la matrice, il existe une contrainte selon laquelle cette cellule a une valeur non négative. Et deuxièmement, pour chaque ligne ou colonne de la matrice, il existe une contrainte selon laquelle la somme des cellules de cette ligne ou colonne est égale à un. Les contraintes de ligne et de colonne définissent un sous-espace linéaire de dimension n ²  − 2 n  + 1 dans lequel se trouve le polytope de Birkhoff, et les contraintes de non-négativité définissent les facettes du polytope de Birkhoff dans ce sous-espace.

Cependant, le polytope de Birkhoff est inhabituel dans la mesure où une description complète de ses facettes est disponible. Pour de nombreux autres polytopes 0-1, il existe un nombre exponentiel ou superexponentiel de facettes, et seules des descriptions partielles de leurs facettes sont disponibles.

Voir également

• Polytope abstrait
• Algèbre commutative combinatoire
• Polytope matroïde
• Commander polytope
• Sphère simplifiée
• Polytope assorti stable

Remarques

Les références

Liens externes

• Kalai, Gil (2008), Cinq problèmes ouverts concernant les polytopes convexes.