Projects per year
Abstract
This thesis studies various aspects of the Tutte polynomial, especially focusing on the MerinoWelsh 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 2connected 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 kedgeconnected 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 3edgeconnected graph with n vertices is, not surprisingly, significantly smaller than the minimum number of spanning trees in a 4edgeconnected graph. However, we conjecture that the minimum number of spanning trees of a 5edgeconnected graph is actually obtained by a 6edgeconnected graph asymptotically.
Thomassen proved the following partial result for the MerinoWelsh 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(n1) then T(G;1,1) ≤ T(G;0,2).
I improve in this thesis Thomassen's result as follows:
If m ≤ 1.29(n1) then T(G;1,1) ≤ T(G;2,0).
If m ≥ 3.58(n1) and G is 3edgeconnected 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 seriesparallel graphs.
The MerinoWelsh conjecture has a stronger version claiming that the Tutte polynomial is convex on the line segment between (2,0) and (0,2) for loopless 2connected graphs. ChavezLomeli 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 2edgeconnected 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 MerinoWelsh 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 seriesparallel 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.
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 2connected 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 kedgeconnected 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 3edgeconnected graph with n vertices is, not surprisingly, significantly smaller than the minimum number of spanning trees in a 4edgeconnected graph. However, we conjecture that the minimum number of spanning trees of a 5edgeconnected graph is actually obtained by a 6edgeconnected graph asymptotically.
Thomassen proved the following partial result for the MerinoWelsh 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(n1) then T(G;1,1) ≤ T(G;0,2).
I improve in this thesis Thomassen's result as follows:
If m ≤ 1.29(n1) then T(G;1,1) ≤ T(G;2,0).
If m ≥ 3.58(n1) and G is 3edgeconnected 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 seriesparallel graphs.
The MerinoWelsh conjecture has a stronger version claiming that the Tutte polynomial is convex on the line segment between (2,0) and (0,2) for loopless 2connected graphs. ChavezLomeli 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 2edgeconnected 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 MerinoWelsh 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 seriesparallel 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.
Original language  English 

Place of Publication  Kgs. Lyngby 

Publisher  Technical University of Denmark 
Number of pages  110 
Publication status  Published  2016 
Series  DTU Compute PHD2015 

Number  384 
ISSN  09093192 
Fingerprint
Dive into the research topics of 'Aspects of the Tutte polynomial'. Together they form a unique fingerprint.Projects
 1 Finished

Aspects of the Tutte Polynomial of a Graph
Ok, S., Thomassen, C., Fischer, P., Jackson, W. B. & BangJensen, J.
Technical University of Denmark
01/10/2012 → 30/09/2015
Project: PhD