A lattice point counting generalisation of the Tutte polynomial
The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion- contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte po...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6331/pdf |
| _version_ | 1797270216579743744 |
|---|---|
| author | Amanda Cameron Alex Fink |
| author_facet | Amanda Cameron Alex Fink |
| author_sort | Amanda Cameron |
| collection | DOAJ |
| description | The Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion- contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This polynomial is constructed using lattice point counts in the Minkowski sum of the base polytope of a polymatroid and scaled copies of the standard simplex. We also show that, in the matroid case, our polynomial has coefficients of alternating sign, with a combinatorial interpretation closely tied to the Dawson partition. |
| first_indexed | 2024-04-25T02:00:45Z |
| format | Article |
| id | doaj.art-8e896cb764c84141acd0d043dc10aaa9 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:00:45Z |
| publishDate | 2020-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-8e896cb764c84141acd0d043dc10aaa92024-03-07T14:55:20ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-04-01DMTCS Proceedings, 28th...10.46298/dmtcs.63316331A lattice point counting generalisation of the Tutte polynomialAmanda Cameron0Alex Fink1Queen Mary University of LondonQueen Mary University of LondonThe Tutte polynomial for matroids is not directly applicable to polymatroids. For instance, deletion- contraction properties do not hold. We construct a polynomial for polymatroids which behaves similarly to the Tutte polynomial of a matroid, and in fact contains the same information as the Tutte polynomial when we restrict to matroids. This polynomial is constructed using lattice point counts in the Minkowski sum of the base polytope of a polymatroid and scaled copies of the standard simplex. We also show that, in the matroid case, our polynomial has coefficients of alternating sign, with a combinatorial interpretation closely tied to the Dawson partition.https://dmtcs.episciences.org/6331/pdf[math.math-co]mathematics [math]/combinatorics [math.co] |
| spellingShingle | Amanda Cameron Alex Fink A lattice point counting generalisation of the Tutte polynomial Discrete Mathematics & Theoretical Computer Science [math.math-co]mathematics [math]/combinatorics [math.co] |
| title | A lattice point counting generalisation of the Tutte polynomial |
| title_full | A lattice point counting generalisation of the Tutte polynomial |
| title_fullStr | A lattice point counting generalisation of the Tutte polynomial |
| title_full_unstemmed | A lattice point counting generalisation of the Tutte polynomial |
| title_short | A lattice point counting generalisation of the Tutte polynomial |
| title_sort | lattice point counting generalisation of the tutte polynomial |
| topic | [math.math-co]mathematics [math]/combinatorics [math.co] |
| url | https://dmtcs.episciences.org/6331/pdf |
| work_keys_str_mv | AT amandacameron alatticepointcountinggeneralisationofthetuttepolynomial AT alexfink alatticepointcountinggeneralisationofthetuttepolynomial AT amandacameron latticepointcountinggeneralisationofthetuttepolynomial AT alexfink latticepointcountinggeneralisationofthetuttepolynomial |