Permutation Tutte polynomial (Q6568865)

The activities expansion of the Tutte polynomial of a graph or matroid is well-known. Given a fixed ordering \(\pi\) of the edges of a graph \(G\), we may express its Tutte polynomial as\N\[\NT(G;x,y) = \sum_{T\in \mathcal T(G)} x^{\operatorname{ia}(T)}y^{\operatorname{ea}(T)},\N\]\Nwhere the sum is over the maximal spanning forests of \(G\) (trees when \(G\) is connected), and \(\mathop{\operatorname{ia}}(T)\) and \(\mathop{\operatorname{ea}}(T)\) denote the internal and external activity of \(T\) with respect to the ordering \(\pi\). Despite being well-known, it is still surprising that the sum is independent of the choice of \(\pi\).\N\NBy averaging over all possibilities for \(\pi\) and then interchanging the order of summation, we obtain the following.\N\[\N\frac{1}{m!} \sum_{\pi} T(G;x,y) = \frac{1}{m!} \sum_{\pi}\sum_{T\in \mathcal T(G)} x^{\operatorname{ia}(T)}y^{\operatorname{ea}(T)} = \sum_{T\in \mathcal T(G)}\frac{1}{m!}\sum_{\pi} x^{\operatorname{ia}(T)}y^{\operatorname{ea}(T)},\N\]\Nwhere \(\pi\) runs over all orderings of the edges of \(G\) and \(m\) is the number of edges of \(G\). This motivates the study of \(\frac{1}{m!}\sum_{\pi} x^{\operatorname{ia}(T)}y^{\operatorname{ea}(T)}\) for a maximal spanning forest \(T\).\N\NIn the present paper, the authors introduce and study the permutation Tutte polynomial \(\tilde T(H;x,y)\) of a bipartite graph \(H=(A,B,E)\). Given an ordering \(\pi\) of the vertices of \(H\), a vertex in \(A\) is internally active with respect to \(\pi\) if it comes after all its neighbours in the ordering \(\pi\), and a vertex in \(B\) is externally active with respect to \(\pi\) if it comes after all its neighbours in the ordering \(\pi\). Then the permutation Tutte polynomial is given by\N\[\N\tilde T(H;x,y) = \sum_{\pi}x^{\operatorname{ia}(\pi)}y^{\operatorname{ea}(\pi)},\N\]\Nwhere \(\operatorname{ia}(\pi)\) and \(\operatorname{ea}(\pi)\) denote the number of internally and externally active vertices with respect to \(\pi\) and the sum is over all orderings of the vertices of \(H\).\N\NThe link with the previous discussion is that if a maximal spanning forest \(T\) of a graph \(G\) is fixed, then the external and internal activities with respect to \(T\) (in the conventional sense) are equal to the external and internal activities in the bipartite graph \(H\) whose vertices correspond to the edges of \(G\) with one part being the edges in \(T\) and the other part being the remaining edges, and whose edges indicate membership in each of the fundamental circuits associated with \(T\).\N\NThe results in the paper can be roughly divided into two types. First, the authors study basic properties of the permutation Tutte polynomial and present some recursion results and the analogue of Brylawski's classical result giving affine relations between the coefficients of the Tutte polynomial. Second, there is a focus on results related to the Merino--Welsh conjecture. The authors proof a useful lemma showing that Conde-Merino-Welsh type inequalities for the (classical) Tutte polynomial can be deduced from the analogous results for the permutation Tutte polynomial. Most notably the authors show that if \(H\) does not contain isolated vertices, then\N\[\N\tilde T(H;3,0) \tilde T(H;3,0) \geq (\tilde T(H;1,1))^2,\N\]\Nwhich leads to a short proof of Jackson's inequality [\textit{B. Jackson}, Combinatorica 30, No. 1, 69--81 (2010; Zbl 1225.05135)],\N\[\NT(G;3,0)T(G;0,3) \geq (T(G;1,1))^2,\N\]\Nfor loopless, bridgeless graphs. They also show that the constant \(3\) may be replaced by \(2.9243\) in both inequalities.\N\NThe permutation Tutte polynomial is an impressive contribution to the theory of the Tutte polynomial and will surely be the source of further interesting results for the classical Tutte polynomial. Indeed, as the authors point out, their work on the permutation Tutte polynomial led to their discovery of a counterexample to the Merino-Welsh conjecture when generalized to matroids. The original conjecture for graphs remains open.