**Problem of the Week**

**Math Club**

**BUGCAT**

**Zassenhaus Conference**

**Hilton Memorial Lecture**

**BingAWM**

seminars:comb:abstract.200709zas

This is a reprise, with some advances, of my talk from two years ago. I will try to explain the philosophy of a universal algebraic structure underlying a type of function defined by identities, and suggest how it works out in the specific situation of *minor-closed* classes of matroids, where every deletion and contraction of a matroid in the class is also in the class. The work is difficult and far from finished but there are interesting results nonetheless.

A *weak Tutte function* (of matroids) is a function that satisfies a linearity relation of the form

f(M) = δ_{e} f(M\e) + γ_{e} f(M/e)

for “most” elements of a matroid M on ground set E. M\e and M/e are matroids on ground set E\e called, respectively, the deletion of e and the contraction of e. The quantities δ_{e} and γ_{e} (belonging to some commutative ring B) are called the *parameters*. Consider an arbitrary minor-closed class * M* of matroids. The problem is to find all weak Tutte functions defined on

f(M + M') = f(M) f(M').

This step is not yet complete.

This is joint work with Joanna Ellis-Monaghan.

Philosophy and history of Tutte functions, i.e., functions of matroids (or graphs, or whatever) that satisfy deletion-contraction. The function may be with parameters or without (i.e., all parameters = 1), it may be multiplicative, and it may be invariant (the value is the same for isomorphic matroids). If the function is multiplicative and invariant and has no parameters, it is the evaluation of a polynomial depending on M, the *Tutte polynomial* T_{M}(x,y). Abstracting to a ring, every matroid can be identified with its Tutte polynomial in **Z**[x,y]. Invariants F that satisfy deletion-contraction and multiplicativity are equivalent to homomorphisms from **Z**[x,y] to the ring of values of F. If not multiplicative, F is still a module map from **Z**[x,y] to the module of values of F.

Philosophy of the algebraic method. Think of the free **Z**[**p**]-module generated by **M**, where d_{e}, c_{e} are independent indeterminates for all the possible points,

**p** = (d_{e}, c_{e})_{e any possible point} ,

and **Z**[**p**] is the polynomial ring. A weak Tutte function F on * M* is equivalent to a module homomorphism from

Therefore, the problem is to understand the structure of the Tutte module. It is generated by discrete matroids because any nondiscrete matroid reduces by deletion-contraction. Multiple ways to reduce to discrete matroids lead to identities in the Tutte module that we don't yet understand well.

The Tutte module, which we can treat as generated by the family * D* of discrete matroids in

seminars/comb/abstract.200709zas.txt · Last modified: 2020/01/29 14:03 (external edit)

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 3.0 Unported