Guest post by Daniel Slilaty.

In a series of three posts by Irene Pivotto (on 08-26-13, 10-07-13, and 10-28-13) subscribers to The Matroid Union blog were introduced to biased graphs and their matroids. Again, a biased graph is a pair $(G,B)$ in which $G$ is a graph and $B$ is a collection of cycles in $G$ (called balanced) for which any theta subgraph of $G$ contains 0, 1, or 3 balanced cycles, i.e. not exactly two balanced cycles. (A theta subgraph is the union of a pair of cycles that intersect along a path.)

Biased graphs were first defined by Zaslavsky [Za91] and they are primarily used to characterize two types of matroids: single-element coextensions of graphic matroids and frame matroids [Za94]. Frame matroids contain the very important class of Dowling Geometries whose centrality within matroid theory was first displayed by Kahn and Kung [KK82] and more recently by Geelen, Gerards, and Whittle [GGW14]. Given a biased graph $(G,B)$, denote the frame matroid by $F(G,B)$ and the complete lift matroid by $L_0(G,B)$ (i.e., the single-element coextension of $M(G)$ defined by $B$).

The canonical examples of biased graphs are given by gains over a group. Formally, this is a function $\varphi\colon\vec E(G)\to\Gamma$ where $\vec E(G)$ is the collection of oriented edges of a graph (if $e$ is an oriented edge, then $-e$ is the same underlying edge oriented in the opposite direction) and $\Gamma$ is a group such that $-\varphi(e)=\varphi(-e)$ for additive groups and $\varphi(e)^{-1}=\varphi(-e)$ for multiplicative groups. In this post we will only consider abelian groups. One advantage of abelian groups over nonabelian ones is that gain functions, up to a certain type of equivalence, gives rise to and can be specified by homomorphisms $\hat\varphi\colon Z_1(G)\to\Gamma$ in which $Z_1(G)$ is the integer cycle space of the graph. Given $\varphi$, let $B_\varphi$ be the collection of cycles in $G$ for which $\hat\varphi(\vec C)$ is the identity element of $\Gamma$ (0 when $\Gamma$ is additive, 1 when $\Gamma$ is multiplicative). Now $(G,B_\varphi)$ is a biased graph.

Given a biased graph $(G,B)$, a homomorphism $\hat\varphi\colon Z_1(G)\to\Gamma$ such that $B_\varphi=B$ is called a $\Gamma$-realization of $(G,B)$. The following proposition by Zaslavsky can be stated for skew fields as well as ordinary fields.

Proposition 1 (Zaslavsky [Za03]) Let $(G,B)$ be a biased graph and $\mathbb F$ a field.

1. If $(G,B)$ is realizable over the multiplicative subgroup of $\mathbb F$, then $F(G,B)$ is $\mathbb F$-representable.
2. If $(G,B)$ is realizable over the additive subgroup of $\mathbb F$, then $L_0(G,B)$ is $\mathbb F$-representable.

Partial fields have become a central and popular topic in modern matroid theory. (See Stefan van Zwam’s blog post from 09-16-13 for an introduction to partial fields.) Briefly a partial field is a pair $\mathbb P=(R,U)$ in which $R$ is a commutative ring and $U$ is a subgroup of the multiplicative group of units of $R$ such that $-1\in U$.

Proposition 2 (van Zwam [vZ09]) Let $\mathbb P=(R,U)$ be a partial field and $(G,B)$ a biased graph.

1. Let $\varphi\colon\vec E(G)\to U$ be a $U$-realization of $(G,B)$. If $\varphi(\vec C)$ is a fundamental element of $\mathbb P$ for each cycle $C$ of $G$, then the frame matroid $F(G,B)$ is $\mathbb P$-representable.
2. Let $\varphi\colon\vec E(G)\to R_+$ be an $R_+$-realization of $(G,B)$. If $\varphi(\vec C)\in U$ for every unbalanced cycle $C$ of $(G,B)$, then $L_0(G,B)$ is $\mathbb P$-representable.

“Well-connected” examples of matroids representable over various partial fields can sometimes be hard to come by. The largest possible simple $\mathbb P$-matroids of a given rank are known for various partial fields, but not every $\mathbb P$-matroid of a given rank must be contained within a $\mathbb P$-matroid of maximum size. Sometimes biased graphs defined by embeddings in surfaces can provide interesting examples of $\mathbb P$-matroids as well. Given a graph $G$ embedded in a closed surface $S$, invariance of homology gives us a natural homomorphism $\natural\colon Z_1(G)\to H_1(S)$ where $H_1(S)$ is the first homology group of the surface calculated with integer coefficients. Now given a partial field $\mathbb P=(R,U)$ there may be some choice of $\sigma\colon H_1(S)\to\mathbb P$ such that the biased graph $(G,B_{\sigma\natural})$ satisfies the conditions of Proposition 2.

Two of my favorite examples come from graphs embedded in the Klein Bottle. The Klein bottle is the surface obtained by identifying two Möbius bands along their circular boundary. In the figure below we have the lighter and darker Möbius bands. The first homology group $H_1(K)$ of the Klein bottle is $\mathbb Z\times\mathbb Z_2$. Of particular usefulness for us is the fact that any cycle $C$ embedded in the Klein bottle now has $\pm\natural(\vec C)\in\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$.

Now let $G$ be a nice large graph embedded in the Klein bottle with high face width e.g., a square grid.

• The dyadic partial field $\mathbb D=(\mathbb Q,U)$ has $U=\{\pm 2^i:i\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to\mathbb Q_+$ by $(1,0)\mapsto 1$ and $(0,1)\mapsto 0$. This yields $\sigma(a,b)\in\{0,\pm 1,\pm 2\}\subset U$ and so $L_0(G,B_{\sigma\natural})$ is $\mathbb D$-representable by
  Proposition 2 (2).
• The 2-cyclotomic partial field $\mathbb K_2=(\mathbb Q(x),U)$ has $U=\{\pm x^i(1-x)^j(1+x)^k:i,j,k\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to U$ by $(1,0)\mapsto x$ and $(0,1)\mapsto \pm1$. Either choice for $\sigma(0,1)$ yields $\sigma(a,b)\in\{1,x,-x,x^{-1},-x^{-1},x^2,x^{-2}\}$ and each element of this set is a fundamental element of $\mathbb K_2$ [vZ09]. Thus $F(G,B_{\sigma\natural})$ is $\mathbb K_2$-representable by Proposition 2(1). Representations of matroids over $\mathbb K_2$ have homomorphic images over other interesting partial fields as well, e.g., the golden-mean and Gersonides partial fields.

These are two very nice examples, but are there more? Do other surfaces yield interesting partial fields to work with? Other surfaces have restrictions on the homology classes of cycles embedded on their surface although these restrictions are not as tight as those for the Klein bottle. The first homology group for the torus is $\mathbb Z\times\mathbb Z$ and cycles must be in homology class $(a,b)$ where the greatest common divisor of $a$ and $b$ is 1. The first homology group of Dyck’s surface (i.e., the connected sum of the torus and the projective plane) is $\mathbb Z\times\mathbb Z\times \mathbb Z_2$ and cycles must be in homology classes $(a,b,0)$, $(a,b,1)$, or $(2a,2b,0)$ where the greatest common divisor of $a$ and $b$ is 1. Then again, is it necessary to restrict ones attention to graphs embedded in surfaces? There are other interesting topological spaces that could be explored as well: dunce hats and connected sums of surfaces with dunce hats, for example.

References

[KK82] J. Kahn, J. Kung, Varieties of combinatorial geometries, Trans. Amer. Math. Soc. 271 (1982) 485–499.

[GGW14] J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014) 736–743.

[vZ09] S. van Zwam, Partial Fields in Matroid Theory, Doctoral dissertation, Technische Universiteit Eindhoven, Netherlands, 2009.

[Za89] T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989) 32–52.

[Za91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991) 46–72.

[Za94] T. Zaslavsky, Frame matroids and biased graphs, European J. Combin. 15 (1994) 303–307.

[Za03] T. Zaslavsky, Biasedgraphs IV: Geometrical realizations, J. Combin. Theory Ser. B 89 (2003) 231–297.

Guest post by Reinhard Diestel.

This is the first of what might become an irregular series of posts on infinite matroids, written on the invitation of Irene Pivotto for the Union. This first piece tells the story of how finite matroids and infinite graphs conspired to get us to think about how to axiomatize infinite matroids. How we ended up solving an old problem we had not even known about – and how it came to be that infinite matroid theory is suddenly exploding. It is meant to be light reading, with some deeper hints to ponder. Future posts, to be written by Nathan Bowler, are likely to be more mathematical and less anecdotal, as they follow up the various open ends of the emerging theory.

Back in 1966, Rado [6] asked whether there was a way to axiomatize matroids in such a way that infinite matroids, too, would have duals. A big challenge, given what was known. But we knew none of this.

What we did know was graphs. In particular, infinite graphs [5]. And these were luring us – towards matroids.

It had all begun with a dream, many years earlier. As an undergraduate studying with Halin, I had heard of the ends of an infinite graph: limit points at infinity such as the three red dots in this graph:

There is a combinatorial definition of ends that divorces the notion of convergence appealed to in this example from the topology of the plane: an end is taken to be an equivalence class of rays, that is, 1-way infinite paths, where two rays are considered as equivalent if no finite set of vertices separates them. As is easy to check, the graph above has three such classes each of which corresponds to one of the red dots, in that its rays converge to that dot in the plane.

Now here was my dream, inspired by this picture. There are a number of theorems about cycles in finite graphs that do not readily generalize to infinite graphs; Hamilton cycles are an obvious example. Might `infinite cycles’ such as the perimeter circle of the above graph come to the rescue and give us infinite analogues of finite cycle theorems? In our example, the perimeter circle would be an infinite Hamilton cycle. And the formal definition of an infinite cycle would be: a cyclic sequence of alternately double rays and ends, with `is an element of’ as incidence. What fun!

But when I tried this in earnest several years later, with my student Daniela Kühn, we soon got bogged down. It turned out that infinite cycles such as the above did not always
work: we had to iterate to allow cycles like

Then for the same reasons we had to iterate again, iterate transfinitely – and ultimately failed. The end of the story [4] was that topology, of all things, came to the rescue.
Even for graphs with abstract ends, not necessarily planar, there is a natural topology in which rays converge to `their’ ends. And it was the edge sets of circles in this topology that turned out to be the right notion of infinite cycle in locally finite infinite graphs, in the sense of allowing us to generalize those finite graph theorems. But these circles could be wild: containing infinitely many double rays arranged like the rationals, and continuum many ends! The perimiter circle of the planar graph below is an example:

And now matroids began to call. One of the finite graph theorems that wouldn’t generalize to infinite graphs naively was the tree packing theorem of Nash-Williams and Tutte. But we were able to prove an infinite tree packing theorem for the naturally adapted topological notion of tree: a set of edges that connects all the vertices but whose topological closure does not contain a circle. Shouldn’t there be a notion of infinite matroid hiding behind this, one in which these topological trees would be the bases, and edge sets of topological circles the circuits?

The usual matroid axioms, together with

(I4) An infinite set is independent as soon as all its finite subsets are independent

as known from vector spaces, do not cover such matroids: a circuit, with all its proper subsets independent, can obviously not be infinite. So we looked for new axioms: axioms for infinite matroids that would default to the known finite ones for finite structures, but which would also allow for infinite circuits such as those topological ones.

It was fun trying – slowly, experimenting as much as thinking, and unaware that others had tried before us. Eventually, we came up with five sets of infinite matroid axioms [2] – in terms of independent sets, bases, circuits, closure and rank – that worked in the way I had hoped: they made the edge sets of topological circles of a locally finite infinite graph into the circuits of a matroid, and our topological spanning trees into the bases of that matroid. (In due course, even a base packing theorem emerged that implied our topological tree packing theorem, as hoped for [1]. But that was much later.) Thus, for an infinite graph there were now two different cycle matroids: one whose circuits were the finite cycles, and another whose circuits were the edge sets of topological circles, finite or infinite. And each of these had a dual: the cocircuits of the first were all the bonds (finite or infinite), those of the latter precisely the finite bonds [3].

In particular: it turned out, with hindsight, that those `infinite cycles’ which had given us such pain to find, and which we were able to nail down only with the help of topology, had a combinatorial description after all: as the minimal non-empty sets of edges not meeting any finite bond in just a single edge. It was thus the matroids lurking in the background which – once found – provided that much-sought combinatorial description of infinite cycles that would make theorems about cycles in finite graphs generalize to infinite graphs!

To top it all, it turned out that we had solved that ancient problem of Rado’s. Or more precisely: that we discovered that Higgs and Oxley had solved it long before us. But this is a story for a later blog, in which we shall look at the infinite axioms more explicitly and give more concrete examples of infinite matroids.

To wind up this one, let me say a little about that traditional axiom (I4): why it was a natural one to suggest at the time matroids were invented, but also why it is – from a modern perspective – a somewhat simple-minded one.

Axiom (I4) makes independence into a property of an infinite combinatorial structure that depends only on its finite substructures. Such properties can typically be verified by an application of Zorn’s Lemma, or by a so-called compactness argument: one that uses the compactness of an infinite product of compact spaces, typically finite, as proved by Tychonoff in the 1930s. Compactness was en vogue at the time and emerged in various guises, and so it must have been natural then to specify the infinite independent sets of a matroid as determined by the finite ones as in (I4).

But let’s look at this problem again now, even put in this way: given the collection of finite subsets of some given set that we wish to call independent, which infinite subsets should we grant the same status?

Axiom (I4) gives a straightforward answer: take them all. All, that is, that have a chance of complying with that other intended axiom, that subsets of independent sets shall be independent. And Rado, one of the champions of compactness and other equivalents of the axiom of choice, saw that this was too crude: in order for infinite matroids to allow for duality as we know it from finite ones, we have to choose as the infinite independent sets a carefully balanced subclass of all those allowed by (I4). To find this subclass, and to describe it by axioms both subtle and simple enough to yield an interesting theory of infinite matroids with duality, was his 1966 challenge.

It now seems that we are finally there. With those newly found axioms, infinite matroid theory can at last be developed in line with its finite counterpart that has raced so successfully ahead. The train is already gaining momentum, inviting you to jump on – but this, too, will be a story for later posts.

[1] E. Aigner-Horev, J.-O. Fröhlich and J. Carmesin, Infinite matroid union, arXiv:1111.0602.

[2] H. Bruhn, R. Diestel, M. Kriesell, R. Pendavingh and P. Wollan, Axioms for infinite matroids, Adv. Math 239 (2013), 18–46.

[3] H. Bruhn and R. Diestel, Infinite matroids in graphs, in the Infinite Graph Theory special volume of Discrete Math. 311 (2011), 1461–1471.

[4] R. Diestel, The cycle space of an infinite graph, Comb. Probab. Computing 14 (2005), 59–79.

[5] R. Diestel, Locally finite graphs with ends: a topological approach I–III, Discrete Math 311–312 (2010–11).

[6] R. Rado, Abstract linear dependence, Colloq. Math. 14 (1966), 257–64.

Guest post by Gary Gordon

Those with memories of Neil White are invited to share them in the comments below.

Neil White passed away on Aug. 11, 2014. Neil was an inspiring teacher and one of the key contributors to the revitalization of matroid theory in the 1970’s and 80’s. He published on a variety of topics, but most of his work was characterized by the way it combined different areas of mathematics, especially combinatorial geometry and algebra. His co-authored book Oriented Matroids (with A. Bjorner, M. Las Vergnas, B. Sturmfels and G. Ziegler) from 1993, with a 2nd edition published in 1999, is the standard reference for this topic. His book Coxeter Matroids (co-authored with A. Borovik and I. Gelfand) and several papers he wrote on this topic are typical of his breadth: these objects draw on classical results in algebra, geometry and combinatorics.

Neil, a Michigan native, received his undergraduate degree from Michigan State University and his PhD from Harvard. Neil wrote his dissertation under the direction of G.-C. Rota in 1972. Neil’s doctoral thesis examined the bracket ring defined by a matroid, and this algebraic approach influenced much of his future work. Neil was one of several young PhDs in Cambridge in the early 1970’s, and this group (including Ken Baclawski, Tom Brylawski, Curtis Greene, Richard Stanley, Walter Whiteley, and Tom Zaslavsky, among others) contributed significantly to a resurgence of interest in matroids.

Neil is best remembered in the matroid community for editing the seminal series of books in the Cambridge Encyclopedia of Mathematics series: Theory of Matroids (1986), Combinatorial Geometries (1987) and Matroid Applications (1992). The wide range of topics and clear organization is a testament to Neil’s vision. Neil also wrote three chapters for these volumes that remain essential references today.

In addition to his work as an editor and expositor, Neil made significant contributions to invariant theory, the combinatorics of bar-and-body frameworks and oriented matroids. MathSciNet lists nearly 600 citations for his 53 publications, and this list does not include citations to the Encyclopedia of Mathematics series he edited. Reading through his list of published work gives an indication of the depth and breadth of his contributions.

Neil spent his career at the University of Florida, retiring in 2008. He was a dedicated and very inspiring teacher, teaching combinatorics, algebra and a variety of other subjects to both undergraduates and graduates. His courses were challenging, but he gave students the tools to solve difficult problems. He was also in charge of the Putnam team preparation for a time. He was always an excellent problem solver, finishing in the top 20 nationally on the Putnam while he was an undergraduate.

From a personal standpoint, Neil was a good friend and a calm, positive presence. He was my teacher for some 10 courses from 1975 – 1977 at the University of Florida, and his approach to mathematics and problem solving had a strong influence on me. His teaching notes were exceptionally clear; I have used his notes on ordinary and exponential generating functions and the Mobius function in my own classes. I do not believe I would be a mathematician if it were not for Neil.

Neil had wide interests outside of mathematics. He was an early advocate of the analytic approach to baseball, and he played a version of simulation baseball for 30 years. He played bridge, read widely, and volunteered his time for local organizations. He also had a good sense of humor: after starting my first job in the 1980’s, he wrote to me, evidently at my request. The “letter” consisted on one word: “Regularly.”

Neil White was a first-rate mathematician, a clear expositor, an inspiring teacher and a genuinely decent and humane person. I will miss him.

Neil White’s obituary appears in The Gainesville Sun.

Guest post by Joseph Kung.

We will give a short account of the $\mathcal{G}$-invariant from the point of view of a classical matroid theorist. The $\mathcal{G}$-invariant is a universal valuation on matroid base polytopes. Much of the theory holds for polymatroids and even more general submodular functions, but we will focus on matroids. This account is based on the work of H. Derksen and A. Fink (singly and jointly). My version differs in details and emphases from theirs. Also, I try to explain how bases of quasi-symmetric functions are used, as far as I can. I may be seriously misrepresenting the work of Derksen and Fink and I apologize in advance if I have done so.

For a finite set $E$, let $\mathbb{R}^E$ be the $|E|$-dimensional real vector space with coordinates labeled by the set $E$, so that the standard basis vectors $e_i,\, i \in E$ form a basis. The (matroid) base polytope $Q(M)$ of the matroid $M(E)$ is the convex polytope in $\mathbb{R}^E$ obtained by taking the convex closure of indicator vectors of bases of $M$, that is,
\[
Q(M) = \mathrm{conv}\left\{ \sum_{b \in B} e_b: B \,\,\text{is a basis of}\,\,M \right\}.
\]
A (base polytope) decomposition is a decomposition $Q(M) = Q(M_1) \cup Q(M_2)$ where (a) both $Q(M_1)$ and $Q(M_2)$ are base polytopes for matroids $M_1$ and $M_2$, and (b) the intersection $Q(M_1) \cap Q(M_2)$ is a base polytope and a face of the polytopes $Q(M_i)$ and $Q(M_j)$.

A function $v$ defined on base polytopes is a (matroid base polytope) valuation if
\[
v(Q(M)) = v(Q(M_1)) + v(Q(M_2)) – v(Q(M_1) \cap Q(M_2))
\]
when $Q(M) = Q(M_1) \cup Q(M_2)$ is a base polytope decomposition.

As a base polytope is the convex closure of indicator vectors of bases, any reasonable function defined on matroids which is a sum over bases should be a valuation. In particular the Tutte polynomial (as a sum of monomials defined by internal and external activities over all bases) is a valuation. (See the paper of Ardila, Fink, and Rincon.) In this sense, valuations are generalizations of Tutte polynomials. Derksen defined a valuation, the $\mathcal{G}$-invariant, in the following way: Let $M(E)$ be a rank-$r$ matroid on the set $E$, labeled as $\{1,2,\ldots,d\}$, where $d =|E|$. A permutation $\pi = x_1x_2 \ldots x_d$ of $E$ defines the sequence of non-negative integers
\[
(r_1, r_2 – r_1, r_3 – r_2, \ldots, r_d-r_{d-1}),
\]
where
\[
r_j = r(\{x_1,x_2,\ldots,x_{j}\}).
\]
This sequence is called the rank sequence $r(\pi)$ of the permutation $\pi$. The $\mathcal{G}$-invariant, is defined by
\[
\mathcal{G}(M) = \sum_{\pi} b_{r(\pi)},
\]
where the sum ranges over all $d!$ permutations of $E$ and $b_{r(\pi)}$ is a basis for quasi-symmetric functions.

We must digress here and explain what quasi-symmetric functions are. A formal power series $f(\underline{x})$ in the variables $x_1,x_2, \ldots$ is quasi-symmetric if $f$ has bounded degree and for a given (finite) sequence of non-negative integers $(\alpha_1, \alpha_2, \ldots, \alpha_k)$, the coefficients of the monomials $x^{\alpha_1}_{i_1} x^{\alpha_2}_{i_2} \cdots x^{\alpha_k}_{i_k}$, where $i_1 < i_2 < \cdots < i_k,$ are the same. Put another way, $f$ is quasi-symmetric if and only if it is a finite linear combination of monomial symmetric functions
\[
m_{(\alpha_1, \alpha_2, \ldots, \alpha_k)} := \sum_{i_1 < i_2 < \cdots < i_k} x_{i_1}^{\alpha_1} x^{\alpha_2}_{i_2} \cdots x^{\alpha_k}_{i_k}.
\]
In particular, a quasi-symmetric function is determined by an array of coefficients indexed by sequences of non-negative integers and one may choose any convenient basis for quasi-symmetric functions to define the $\mathcal{G}$-invariant. Each basis gives a different function $f(\underline{x})$ but all of them contain the same information about the matroid $M$. Thus, the $\mathcal{G}$-invariant is really an equivalence class of power series, defined up to a choice of basis of quasi-symmetric functions. Alternatively, we can simply think of the $\mathcal{G}$-invariant as an array of coefficients indexed by sequences of non-negative integers which may be transformed by certain change-of-basis matrices.

For matroids, rank sequences are sequences of $0$’s and $1$s with exactly $r$ $1$’s, where $r$ is the rank of the matroid. Using the formula for the rank function of the dual $M^*$, it is immediate that for a given permutation $\pi$ of $E$, the rank sequence of $\pi$ in $M^*$ is the complementary sequence (the sequence obtained by switching $0$’s with $1$’s and conversely) to the rank sequence in $M$. Thus, $\mathcal{G}(M^*)$ can be obtained from $\mathcal{G}(M)$ by a change of basis of quasi-symmetric functions.

The elements of the permutation where the $1$’s occur form a basis of $M$. Thus we can assign a (unique) basis to each rank sequence and the $\mathcal{G}$-invariant is a sum over bases. It is not surprising that it is a base polytope valuation.

Theorem (Derksen and Fink).The $\mathcal{G}$-invariant is a “universal” valuation on matroid base polytopes, in the sense that every base polytope valuation is an “evaluation” of the $\mathcal{G}$-invariant. In particular, the Tutte polynomial is an “evaluation” of the $\mathcal{G}$-invariant.

The proof is complicated. See the paper of Derksen and Fink cited at the end of this note.

As an example, consider the uniform matroid $U_{3,6}$ on the set $\{1,2,3,4,5,6\}$. All $3$-subsets are bases. The permutation $123456$ gives the composition $(1,1,1,0,0,0)$ and so does any other permutation. Hence, using the basis of monomial symmetric functions,
\[
\mathcal{G}(U_{3,6})=720m_{(1,1,1,0,0,0)}=720\sum_{i_1 < i_2 < i_3} x_{i_1}x_{i_2}x_{i_3}.
\]
For comparison,
\begin{multline*}
T(U_{3,6};x,y) = (x-1)^3+ 6 (x-1)^2 +15 (x-1) + 20 + 15(y-1) + 6(y-1)^2 + (y-1)^3
\\
= x^3 + 3x^2 + 6x + 6y + 3y^2 + y^3.
\end{multline*}
Here is where I might be totally wrong. The only way I can see of getting $T$ from $\mathcal{G}$ is to do a change of basis and assign different values to basis elements. So “evaluation” as used in the theorem means something more general.

What information does the $\mathcal{G}$-invariant contain? Since almost all matroids are paving matroids, a first-order answer might be obtained by calculating the $\mathcal{G}$-invariant for paving matroids. This is a simple calculation. I think R. T. Tugger is the first to do this.

Most of you would know what a paving matroid is, but I need to establish notation. Recall that a (Hartmanis) $k$-partition $\underline{H}$ of the set $E$ is a collection of subsets called blocks satisfying three conditions:

(a) the union of all the blocks equals $E$;

(b) every block has size at least $k$;

(c) every subset of size $k$ in $E$ is contained in exactly one block.

The blocks with more than $k$ elements are non-trivial and those with exactly $k$ elements are trivial. Let $\underline{H}$ be an $(r-1)$-partition. The paving matroid $\mathrm{Pav}(\mathcal{H})$ is the matroid of rank $r$ with the following flats: the entire set $E,$ the blocks of $\underline{H},$ and all subsets of size $r-2$ or less. Roughly speaking, all the dependencies occur at the top.

Proposition. The invariant $\mathcal{G}(\mathrm{Pav}(\underline{H}))$ can be computed from the multi set $\{ |H|: H \,\,\text{is a non-trivial block}\}$.

Proof. Let $|E|=d$ and $\pi = x_1,x_2, \ldots, x_d$ be a permutation of $E$. since every subset of size $r-1$ is independent, the rank sequence of $\pi$ starts with $r-1$ $1$’s. The remaining $1$ occurs in position $i, \, i \ge r.$ If $\{x_1, x_2, \ldots,x_{r-1}\}$ is a trivial block, then $i = r$. If not, then $\{x_1, x_2, \ldots,x_{r-1}\}$ spans a non-trivial block $H$ and $i$ can vary from $r$ to $|H|$. Indeed, the index is $i$ if and only if $\{x_1,x_2, \ldots,x_{i-1}\} \subseteq H$. Hence, in the sum for the $\mathcal{G}$-invariant, a trivial block contributes
\[
(r-1)!(d-r+1)! m_{(1^r0^{d-r})}.
\]
On the other paw, a non-trivial block contributes
\[
\sum_{i=r}^{|H|} \frac {|H|!} {(|H| – i + 1)!} (|E| – |H|) (|E| – i)! m_{(1^{r-1 }0^{i-r}10^{d-i})}.
\]
Here $(1^{r-1 }0^{i-r}10^{d-i}) = (1,1,\ldots,1,0,0,\ldots,0,1,0,0,\ldots,0)$ is the $0$-$1$ sequence with $1$’s in the leading $r-1$st positions and the $i$th position. Note that the number of trivial blocks can be calculated from the sizes of the non-trivial blocks.

As an example, let $P$ be the paving matroid on $123456$ defined by the $ 2$-partition $\{1234,456, 15, 16, 25, 26, 35,36\}$. Geometrically, $\mathrm{P}$ is the rank-$3$ matroid consisting of a $4$-point line $1234$ and a $3$-point line $456$ intersecting at the common point $4$. Then
\[
\mathcal{G}(P) = 48 m_{(1,1,0,0,1,0)} +144 m_{1,1,0,1,0,0} + 540 m_{(1,1,1,0,0,0)}.
\]

The analog of the proposition holds for the Tutte polynomial. For a paving matroid, the $\mathcal{G}$-invariant contains exactly the same information about the matroid as the Tutte polynomial. In particular, the $\mathcal{G}$-invariant and the Tutte polynomial has the same asymptotic power to distinguish matroids. However, $\mathcal{G}$-invariant can distinguish pairs of matroids the Tutte polynomial cannot. For examples, see the paper of Billera, Jia, and Reiner.

R. T. Tugger conjectures that one can use the argument in the chapter of Brylawski and Oxley in “Matroid Applications” (Exercise 9, p.~198) to show that for any integer $N$, there are at least $N$ non-isomorphic matroids having the same $\mathcal{G}$-invariant.

Although it is a sum over a lot of permutations, calculating the $\mathcal{G}$-invariant feels somehow more elegant than calculating the Tutte polynomial. (Yes, I like the definition!) As an exercise, the reader might imagine calculating $\mathcal{G}(\mathrm{PG}(r-1,q))$. The bases of a projective geometry all behave in the same way, so one can easily write down the terms in the sum for the $\mathcal{G}$-invariant.

For each basis, the sum over the quasi-symmetric functions determined by its rank sequences summarizes in some way how the basis interacts with the other elements of the matroid. This includes its internal and external activity. It will be very interesting to derive directly internal and external activities from the quasi-symmetric function of the basis. I have no idea how to do this and will be happy if anyone tells me how to do this.

The $\mathcal{G}$-invariant has applications. I am not the person to write about them but I hope this initial attempt would motivate someone else to tell us about these applications.

Here are four papers out of many I could have cited:

F. Ardila, A. Fink, F. Rincon, Valuations for matroid polytope subdivisions, Canad. J. Math. 62 (2010) 1228-1245.

L.J. Billera, N. Jia, V. Reiner, A quasisymmetric function for matroids, European J. Combin. 30 (2009) 1727-1757.

H. Derksen, Symmetric and quasi-symmetric functions associated to polymatroids, arXiv: 0801.4393.

H. Derksen, A. Fink, Valuative invariants for polymatroids, Adv. Math. 225 (2010) 1840-1892.

An introduction to quasi-symmetric functions can be found in the book Enumerative Combinatorics II by Richard Stanley.