A Tutte polynomial inequality for lattice path matroids

DOI10.1016/J.AAM.2016.11.008MaRDI QIDQ679539zbMATH OpenOpenAlexFDO

Authors Kolja Knauer, L. Martínez-Sandoval, Jorge Luis Ramírez Alfonsín

Publication date 11 January 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.00600

zbMATH Keywords

Tutte polynomiallattice path matroidsMerino-Welsh conjecture

Mathematics Subject Classification ID

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

Abstract: Let $M$ be a matroid without loops or coloops and let $T(M;x,y)$ be its Tutte polynomial. In 1999 Merino and Welsh conjectured that ${\displaystyle }$max(T(M;2,0), T(M;0,2))geq T(M;1,1)${\displaystyle }$ holds for graphic matroids. Ten years later, Conde and Merino 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.

Recommendations

• Lattice path matroids: Enumerative aspects and Tutte polynomials
• A note on some inequalities for the Tutte polynomial of a matroid
• Computing the Tutte polynomial of lattice path matroids using determinantal circuits
• The Tutte polynomial of some matroids
• The Tutte Polynomial for Matroids of Bounded Branch-Width
• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• Parametrized Tutte Polynomials of Graphs and Matroids
• Some inequalities for the Tutte polynomial
• An inequality for Tutte polynomials
• Toric ideals of lattice path matroids and polymatroids

Cites work

• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 1369835 (Why is no real title available?)
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• Lattice path matroids: structural properties
• Lattice path matroids: the excluded minors
• Transversals and matroid partition

Cited in

(14)

• An inequality for Tutte polynomials
• Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs
• On the Ehrhart polynomial of minimal matroids
• On lattice path matroid polytopes: integer points and Ehrhart polynomial
• Facial structures of lattice path matroid polytopes
• Some inequalities for the Tutte polynomial
• Valuative invariants for large classes of matroids
• The Merino-Welsh conjecture for split matroids
• A note on some inequalities for the Tutte polynomial of a matroid
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• The Merino-Welsh conjecture is false for matroids
• Study of exponential growth constants of directed heteropolygonal Archimedean lattices
• Delta-matroids as subsystems of sequences of Higgs lifts
• Lattice path matroids and quotients

This page was built for publication: A Tutte polynomial inequality for lattice path matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q679539)