Problem of the Week
Hilton Memorial Lecture
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 M. The first step is to set up the universal module for weak Tutte functions and relate it to the universal algebra for multiplicative Tutte functions, which satisfy the additional multiplicative rule
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 TM(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 de, ce are independent indeterminates for all the possible points,
p = (de, ce)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 Z[p]M whose kernel contains all expressions M - de(M\e) - ce(M/e). The submodule generated by all these expressions is called Γ. Then a weak Tutte function is “really” a module homomorphism from the Tutte module, w(M) := Z[p]M / Γ .
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 M, has the form Z[p]D / Δ , where Δ is the part of Γ that lies in Z[p]D. We need to know the structure of Δ if we want to understand the Tutte module (and thus weak Tutte functions).