Toric Ideals of Flow Polytopes

Résumé : Nous démontrons que les idéaux toriques des polytopes de flot sont engendrés par un ensemble de degré $3$. Cela a été conjecturé par Diaconis et Eriksson pour le cas particulier du polytope de Birkhoff. Notre preuve utilise une méthode de subdivision par hyperplans, développée par Haase et Paffenholz. Il est bien connu que les bases de Gröbner revlex réduite du polytope de Birkhoff $B_n$ sont au plus de degré $n$. Nous démontrons que cette borne est optimale pour quelques ordres revlex. Pour les polytopes de transportation de dimension $(m \times n)$, il existe un résultat similaire : leurs bases de Gröbner sont au plus de degré $\lfloor mn/2 \rfloor$. Nous construisons une famille d'exemples pour lesquels cette borne est atteinte.
Type de document :
Communication dans un congrès
Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.889-896, 2010, DMTCS Proceedings
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01186265
Contributeur : Coordination Episciences Iam <>
Soumis le : lundi 24 août 2015 - 15:46:08
Dernière modification le : samedi 16 décembre 2017 - 07:18:04
Document(s) archivé(s) le : mercredi 25 novembre 2015 - 17:11:37

Fichier

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

Identifiants

  • HAL Id : hal-01186265, version 1

Collections

Citation

Matthias Lenz. Toric Ideals of Flow Polytopes. Billey, Sara and Reiner, Victor. 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), 2010, San Francisco, United States. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AN, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010), pp.889-896, 2010, DMTCS Proceedings. 〈hal-01186265〉

Partager

Métriques

Consultations de la notice

42

Téléchargements de fichiers

117