A Tutte polynomial inequality for lattice path matroids

DOI10.1016/J.AAM.2016.11.008zbMATH Open1377.05089arXiv1510.00600OpenAlexW2963671999MaRDI QIDQ679539FDOQ679539

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Transversals and matroid partition
• Lattice path matroids: structural properties
• Lattice path matroids: the excluded minors
• Title not available (Why is that?)
• Lattice path matroids: Enumerative aspects and Tutte polynomials

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
• Valuative invariants for large classes of matroids
• Some inequalities for the Tutte polynomial
• The Merino-Welsh conjecture for split matroids
• A note on some inequalities for the Tutte polynomial of a matroid
• The Merino-Welsh conjecture is false for matroids
• Lattice path matroids: Enumerative aspects and Tutte polynomials
• 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)