# 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: woodd@unimelb.edu.au