Permutation Tutte polynomial

2023/11/03 by Csongor Beke, Beke, Csongor, Gergely Csáji +5 · 1 citation
Mathematics · Agricultural and Biological Sciences · #Advanced Combinatorial Mathematics #Graph theory and applications #Botanical Research and Chemistry

paper · pdf · doi:10.48550/arxiv.2311.01936

Abstract

The classical Tutte polynomial is a two-variate polynomial T_G(x,y) associated to graphs or more generally, matroids. In this paper, we introduce a polynomial \widetildeT_H(x,y) associated to a bipartite graph H that we call the permutation Tutte polynomial of the graph H. It turns out that T_G(x,y) and \widetildeT_H(x,y) share many properties, and the permutation Tutte polynomial serves as a tool to study the classical Tutte polynomial. We discuss the analogs of Brylawsi's identities and Conde--Merino--Welsh type inequalities. In particular, we will show that if H does not contain isolated vertices, then \widetildeT_H(3,0)\widetildeT_H(0,3)≥ \widetildeT_H(1,1)², which gives a short proof to the analogous result of Jackson: T_G(3,0)T_G(0,3)≥ T_G(1,1)² for graphs without loops and bridges. We also improve on the constant 3 in this statement by showing that one can replace it with 2.9243.

Cited by

• On the irreducibility and monodromy of Tutte polynomials

Related

• Universal Tutte polynomial
• On the irreducibility and monodromy of Tutte polynomials
• The Tutte polynomial of some matroids
• Tutte Polynomials for Directed Graphs
• Tutte Polynomials of Symmetric Hyperplane Arrangements