Abstract | ||
---|---|---|
A new isomorphism invariant of matroids is introduced, in the form of a quasisymmetric function. This invariant: *defines a Hopf morphism from the Hopf algebra of matroids to the quasisymmetric functions, which is surjective if one uses rational coefficients; *is a multivariate generating function for integer weight vectors that give minimum total weight to a unique base of the matroid; *is equivalent, via the Hopf antipode, to a generating function for integer weight vectors which keeps track of how many bases minimize the total weight; *behaves simply under matroid duality; *has a simple expansion in terms of P-partition enumerators; *is a valuation on decompositions of matroid base polytopes. This last property leads to an interesting application: it can sometimes be used to prove that a matroid base polytope has no decompositions into smaller matroid base polytopes. Existence of such decompositions is a subtle issue arising from the work of Lafforgue, where lack of such a decomposition implies that the matroid has only a finite number of realizations up to scalings of vectors and overall change-of-basis. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.ejc.2008.12.007 | Eur. J. Comb. |
Keywords | Field | DocType |
unique base,matroid base polytopes,matroid base polytope,greedy algorithm,matroid polytope,. matroid,minimum total weight,fine schubert cell.,matroid duality,valuation,smaller matroid base polytopes,hopf algebra,quasisymmetric function,quasisymmetric func- tion,total weight,integer weight vector,generating function | Matroid,Discrete mathematics,Combinatorics,Oriented matroid,Matroid partitioning,Polytope,Graphic matroid,Invariant (mathematics),Weighted matroid,Hopf algebra,Mathematics | Journal |
Volume | Issue | ISSN |
30 | 8 | 0195-6698 |
Citations | PageRank | References |
9 | 1.39 | 7 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Louis J. Billera | 1 | 279 | 57.41 |
Ning Jia | 2 | 9 | 1.39 |
Victor Reiner | 3 | 64 | 15.80 |