An inequality for Tutte polynomials

DOI10.1007/S00493-010-2484-4MaRDI QIDQ532122zbMATH OpenOpenAlexFDO

Authors Bill Jackson

Publication date 26 April 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-010-2484-4

zbMATH Keywords

Tutte polynomial

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph polynomials (05C31)

Review text

The Tutte polynomial of the graph \(G=(V,E)\) can be defined by the closed formula \[ TG(x, y) =\sum_{A\subseteq E} (x - 1)^{r(E)-r(A)}(y - 1)^{| A| -r(A)} \] where \(r(A)=| V | -\omega (V,A)\), and \(\omega(V,A)\) denotes the number of components in the graph \((V,A)\). The author proves that, for a graph \(G\) without loops or bridges and \(a\), \(b\) positive real numbers with \(b\geq a(a+2)\), the following holds: The Tutte polynomial of \(G\) satisfies the inequality \(TG(b, 0)TG(0,b)\geq TG(a,a)^2\). This result is inspired by a conjecture of \textit{C. Merino} and \textit{D. J. A. Welsh} [``Forests, colorings and acyclic orientations of the square lattice, Ann. Comb. 3, No.~2--4, 417--429 (1999; Zbl 0936.05043)] which says that \(TG(1, 1)\leq \max\{TG(2, 0),TG(0, 2)\}\).

Recommendations

• A note on some inequalities for the Tutte polynomial of a matroid
• Some inequalities for the Tutte polynomial
• A Tutte polynomial inequality for lattice path matroids
• An inequality for chromatic polynomials
• On the Tutte polynomial of benzenoid chains

Cites work

• A Contribution to the Theory of Chromatic Polynomials
• A note on some inequalities for the Tutte polynomial of a matroid
• Acyclic and totally cyclic orientations of combinatorial geometries
• Acyclic orientations of graphs
• Forests, colorings and acyclic orientations of the square lattice
• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs

Cited in

(10)

• The coefficients of the Tutte polynomial are not unimodal
• The Tutte polynomial of some matroids
• The Merino-Welsh conjecture holds for series-parallel graphs
• A note on some inequalities for the Tutte polynomial of a matroid
• scientific article; zbMATH DE number 5941303 (Why is no real title available?)
• The Merino-Welsh conjecture for split matroids
• Some inequalities for the Tutte polynomial
• The Merino-Welsh conjecture is false for matroids
• Permutation Tutte polynomial
• A Tutte polynomial inequality for lattice path matroids

This page was built for publication: An inequality for Tutte polynomials

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