DMTCS Proceedings, 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010)

Font Size:  Small  Medium  Large

Valuative invariants for polymatroids

Harm Derksen, Alex Fink


Many important invariants for matroids and polymatroids, such as the Tutte polynomial, the Billera-Jia-Reiner quasi-symmetric function, and the invariant &mathcal;G introduced by the first author, are valuative. In this paper we construct the ℤ-modules of all ℤ-valued valuative functions for labeled matroids and polymatroids on a fixed ground set, and their unlabeled counterparts, the ℤ-modules of valuative invariants. We give explicit bases for these modules and for their dual modules generated by indicator functions of polytopes, and explicit formulas for their ranks. Our results confirm a conjecture of the first author that &mathcal;G is universal for valuative invariants.
Résumé. Beaucoup des invariants importants des matroïdes et polymatroïdes, tels que le polynôme de Tutte, la fonction quasi-symmetrique de Billera-Jia-Reiner, et l'invariant &mathcal;G introduit par le premier auteur, sont valuatifs. Dans cet article nous construisons les ℤ-modules de fonctions valuatives aux valeurs entières des matroïdes et polymatroïdes étiquetés définis sur un ensemble fixe, et leurs équivalents pas étiquetés, les ℤ-modules des invariants valuatifs. Nous fournissons des bases des ces modules et leurs modules duels, engendrés par fonctions charactéristiques des polytopes, et des formules explicites donnants leurs rangs. Nos résultats confirment une conjecture du premier auteur, que &mathcal;G soit universel pour les invariants valuatifs.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional