The brick polytope of a sorting network

Résumé : L'associaèdre est un polytope dont le graphe est le graphe des flips sur les triangulations d'un polygone convexe. Les pseudotriangulations et les multitriangulations généralisent les triangulations dans deux directions différentes, qui ont été unifiées par Pilaud et Pocchiola au travers de leur étude des arrangements de pseudodroites avec contacts couvrant un support donné. Nous construisons ici le "polytope de briques'' d'un support, obtenu comme l'enveloppe convexe des "vecteurs de briques'' associés à chaque arrangement de pseudodroites couvrant ce support. Nous caractérisons les sommets de ce polytope, décrivons ses faces et le décomposons en somme de Minkowski de polytopes élémentaires. Notre construction contient toutes les réalisations de l'associaèdre d'Hohlweg et Lange, qui apparaissent comme polytopes de briques de certains supports bien choisis.
Type de document :
Communication dans un congrès
Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.777-788, 2011, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01215072
Contributeur : Coordination Episciences Iam <>
Soumis le : mardi 13 octobre 2015 - 15:06:11
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44
Document(s) archivé(s) le : jeudi 27 avril 2017 - 00:26:08

Fichier

dmAO0168.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01215072, version 1

Collections

Citation

Vincent Pilaud, Francisco Santos. The brick polytope of a sorting network. Bousquet-Mélou, Mireille and Wachs, Michelle and Hultman, Axel. 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), 2011, Reykjavik, Iceland. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AO, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), pp.777-788, 2011, DMTCS Proceedings. 〈hal-01215072〉

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

55