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.