School Seminars and Colloquia

A combinatorial approach to Tutte polynomial inequalities

Discrete Structures and Algorithms (Seminar)

by Arun P Mani

Institution: Monash University
Date: Tue 8th September 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: The Tutte polynomial of a connected graph (and more generally, a
matroid) is a two-variable polynomial known to encode a wide variety
of combinatorially interesting information of the graph, including the
number of subgraphs that are acyclic (forests), number of spanning
trees and the number of subgraphs that are connected. This polynomial
can be defined using a non-negative integer function, the rank
function, r, which is defined on the subsets of the edge set of the
graph. A fundamental property of the rank function is its
submodularity. That is, for subsets A, B of E(G), r(A union B) +
r(A intersection B) <= r(A) + r(B).

In this talk, I'll define a property for graphs (and matroids) that
extends rank submodularity in a way that can be applied to prove some
inequalities for its Tutte polynomial in the positive quadrant. This
region includes all three of the above mentioned counting problems.
I'll then talk about what is known about the existence of this
extended submodular property in graphs and matroids. I'll finally
demonstrate with some simple examples how to apply all of this to get
some non-trivial bounds for Tutte polynomial evaluations in the
positive quadrant.

For More Information: contact: David Wood. email: