Aspects of the Tutte polynomial

This thesis studies various aspects of the Tutte polynomial, especially focusing on the Merino-Welsh conjecture. We write T(G;x,y) for the Tutte polynomial of a graph G with variables x and y. In 1999, Merino and Welsh conjectured that if G is a loopless 2-connected graph, then T(G;1,1) ≤ max{T(G;2,0), T(G;0,2)}.

The three numbers, T(G;1,1), T(G;2,0) and T(G;0,2) are respectively the numbers of spanning trees, acyclic orientations and totally cyclic orientations of G. First, I extend Negami's splitting formula to the multivariate Tutte polynomial. Using the splitting formula, Thomassen and I found a lower bound for the number of spanning trees in a k-edge-connected graph.

Our bound is tight for k even, but for k odd we give a slightly better lower bound which we believe is not tight. We prove that the minimum number of spanning trees in a 3-edge-connected graph with n vertices is, not surprisingly, significantly smaller than the minimum number of spanning trees in a 4-edge-connected graph.

However, we conjecture that the minimum number of spanning trees of a 5-edge-connected graph is actually obtained by a 6-edge-connected graph asymptotically. Thomassen proved the following partial result for the Merino-Welsh conjecture. Assume the graph G is loopless, bridgeless and has n vertices and m edges.

If m ≤ 1.066 n then T(G;1,1) ≤ T(G;2,0). If m ≥ 4(n-1) then T(G;1,1) ≤ T(G;0,2). I improve in this thesis Thomassen's result as follows: If m ≤ 1.29(n-1) then T(G;1,1) ≤ T(G;2,0). If m ≥ 3.58(n-1) and G is 3-edge-connected then T(G;1,1) ≤ T(G;0,2). Strengthening Thomassen's idea that acyclic orientations dominate spanning trees in sparse graphs, I conjecture that the ratio T(G;2,0)/T(G;1,1) increases as G gets sparser.

To support this conjecture, I prove a variant of the conjecture for series-parallel graphs. The Merino-Welsh conjecture has a stronger version claiming that the Tutte polynomial is convex on the line segment between (2,0) and (0,2) for loopless 2-connected graphs. Chavez-Lomeli et al. proved that this holds for coloopless paving matroids, and I provide a shorter proof of their theorem.

I also prove it for minimally 2-edge-connected graphs. As a general statement for the convexity of the Tutte polynomials, I show that the Tutte polynomial of a sparse paving matroid is almost surely convex in the first quadrant. In contrast, I conjecture that the Tutte polynomial of a sparse paving matroid with fixed rank is almost never convex in the first quadrant.

The following multiplicative version of the Merino-Welsh conjecture was considered by Noble and Royle: T(G;1,1)2 ≤ T(G;2,0) T(G;0,2). Noble and Royle proved that this multiplicative version holds for series-parallel graphs, using a computer algorithm that they designed. Using a property of the splitting formula which I found, I improve their algorithm so that it is applicable to the class of graphs with bounded treewidth (or pathwidth).

As an application, I verify that the multiplicative version holds for graphs with pathwidth at most 3.