A Tutte polynomial inequality for lattice path matroids. (English) Zbl 1377.05089

Summary: Let \(M\) be a matroid without loops or coloops and let \(T(M; x, y)\) be its Tutte polynomial. C. Merino and D. J. A. Welsh [Ann. Comb. 3, No. 2–4, 417–429 (1999; Zbl 0936.05043)] conjectured that \[ \max(T(M;2,0),T(M;0,2))\geq T(M;1,1) \] holds for graphic matroids. Ten years later, R. Conde and C. Merino [Int. J. Math. Comb. 2, 79–89 (2009; Zbl 1198.05015)] proposed a multiplicative version of the conjecture which implies the original one. In this paper we prove the multiplicative conjecture for the family of lattice path matroids (generalizing earlier results on uniform and Catalan matroids). In order to do this, we introduce and study particular lattice path matroids, called snakes, used as building bricks to indeed establish a strengthening of the multiplicative conjecture as well as a complete characterization of the cases in which equality holds.


05C31 Graph polynomials
05B35 Combinatorial aspects of matroids and geometric lattices
05C30 Enumeration in graph theory
05C15 Coloring of graphs and hypergraphs
52B40 Matroids in convex geometry (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.)
Full Text: DOI arXiv


[1] Bonin, J. E., Lattice path matroids: the excluded minors, J. Combin. Theory Ser. B, 100, 585-599 (2010) · Zbl 1231.05054
[2] Bonin, J. E.; de Mier, A., Lattice path matroids: structural properties, European J. Combin., 27, 701-738 (2006) · Zbl 1087.05014
[3] Bonin, J. E.; de Mier, A.; Noy, M., Lattice path matroids: enumerative aspects and Tutte polynomials, J. Combin. Theory Ser. A, 104, 63-94 (2003) · Zbl 1031.05031
[4] Edmonds, J.; Fulkerson, D. R., Transversal and matroids partition, J. Res. Natl. Bur. Stand., Sect. B, 69, 147-153 (1965) · Zbl 0141.21801
[5] Welsh, D. J.A., Matroid Theory, L.M.S. Monographs, vol. 8 (1976), Academic Press, a Subsidiary of Harcourt Brace Jovanovich, Publishers: Academic Press, a Subsidiary of Harcourt Brace Jovanovich, Publishers London-New York-San Francisco · Zbl 0343.05002
[6] Welsh, D. J.A., The Tutte polynomial, Random Structures Algorithms, 15, 210-228 (1999) · Zbl 0934.05057
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.