What if $G$ is infinite? In that case it is no longer sufficient that all degrees are even. Indeed, consider the two-way infinite ray; every vertex has degree 2, but there isn’t even a single cycle. So we need a stronger condition. Rather than considering individual vertices, we should consider cuts. Since any cycle meets any cut in an even number of edges, if $G$ is an edge-disjoint union of cycles then every cut of $G$ must be a disjoint union of finite sets of even size, so must itself be even or infinite. In 1960, Nash-Williams showed that this condition is sufficient [3].

**Theorem 1:** Let $G$ be any graph. Then $G$ is an edge-disjoint union of cycles if and only if $G$ has no finite cuts of odd size.

In this post we will examine various generalisations of this result, as well as some of the basic ideas used to prove them, and we will finish up by looking at some intriguing open problems which remain. However, we will not look at Nash-Williams’ original proof, since that was long and technical, and over the years more efficient proofs have emerged (see for example [4],[5]).

Roughly speaking, the modern proofs work in the following way. We want to prove the result by induction on the cardinality of $G$. As the base case, we suppose that $G$ is countable. In this case, we can use an argument like the one above to recursively pick a sequence of edge-disjoint cycles $C_1, C_2,\ldots$ covering all edges of $G$.

For the induction step, we want to break $G$ up into strictly smaller edge-disjoint subgraphs of smaller cardinality, which we will use to cover larger and larger chunks of $G$. We will make sure that each of these subgraphs $H$ has the following properties:

- Any finite cut of $H$ is also a cut of $G$
- Any finite cut of $G – E(H)$ is also a cut of $G$

The first of these properties is obviously useful, since it ensures in particular that $H$ has no finite odd cuts, so that we can apply the induction hypothesis to it. It is also easy to extend any infinite subgraph $X$ of $G$ to a subgraph $H$ of the same cardinality satisfying (1), by repeatedly taking each finite cut of $X$ which isn’t a cut of $G$ and either adding all edges of the corresponding cut of $G$ (if that cut is finite) or infinitely many edges of the corresponding cut of $G$ (if that cut is infinite). So by closing under this operation we can easily extend any subgraph of $G$ to one satisfying (1).

The second property is used in a recursive construction of our partition of $G$ into subgraphs, to ensure that after we have taken $H$ as a partition class we still have no odd-sized cuts in the remainder and so we can continue finding more partition classes in the same way. Rather surprisingly, there is another operation, akin to that in the previous paragraph but more technical, such that by closing under that operation we can turn any subgraph of $G$ into another of the same cardinality satisfying (2). Even more surprisingly, the exact details of that operation need not be specified for the proof.

Why not? There is a very useful trick, often applicable in such situations, called the Elementary Submodel Method. It allows us to define a kind of universal closure operation, which when applied to a subgraph closes it under almost anything we might have wanted. That seems miraculous. How could it possibly work? The idea is to make use of a result from logic called the Löwenheim-Skolem Theorem, which states that if we have some theory expressed using first-order logic, some model $M$ of that theory and some infinite subset $X$ of $M$ then we can find a submodel $N$ of $M$ including $X$ and of the same cardinality as $X$, such that any first order statement which holds (in $N$) for some elements of $N$ still holds for those same elements in $M$. $N$ is then called an *elementary submodel* of $M$.

A first idea about how to apply this might be to take $M$ to be the graph $G$, considered as a model of the theory of graphs, and define $H$ to be the subgraph corresponding to $N$. Then for any construction we can express in the language of graphs, $H$ will be closed as a subgraph of $G$ under that construction. This is already fairly powerful, but unfortunately the operations under which we want to close subgraphs are often too complicated to be expressible using first-order logic in the language of graphs. So we need a more powerful idea.

What we do instead is to take $M$ to be the whole set-theoretic mathematical universe (considered as a model of the axioms of set theory). Given an infinite subgraph $X$ of $G$ we can now find an elementary submodel $N$ of $M$ including $X$ and containing $G$. If we define $H$ to be the intersection of $N$ with $G$ then it will really be closed under any operation we might think of. Any readers who are logicians might now be worried about whether it is really ok to step outside the set-theoretic universe and treat that whole universe as a mathematical object in this way. Would it then be contained in itself? This is a valid worry, but it can be circumvented by instead taking $M$ to be a large enough fragment of the set-theoretic universe, rather than the whole thing.

For those reading about the Elementary Submodel Method for the first time, I understand that it can be a little mind-blowing the first time you see it. I remember that it took me a while to wrap my head around it. For the purposes of this post, all you need to remember is that it gives you a kind of universal closure operation, which (with a little more work) lets us push through the proof outlined above.

However, if at some point in life you find yourself working with some recursive construction where you would like to close some infinite graphs (or indeed matroids) under some very technical operations, and perhaps it isn’t easy to see exactly what those operations should be, do consider whether the Elementary Submodel Method might be a helpful tool for you. A good introduction can be found in [4].

What we want to focus on for now is how the same method allows us to extend Nash-Williams’ results to infinite matroids. The obvious question to ask is when we can express the ground set of a matroid as a disjoint union of circuits. In the discussion above, we relied on the fact that every cycle in a graph meets every cut in an even number of edges. The corresponding property in the language of matroids would be that every circuit-cocircuit intersection is even, or to put it another way, that the matroids we are working with are binary. And indeed we do get a corresponding result for infinite binary matroids, with a very similar proof:

**Theorem 2:** Let $M$ be a finitary binary matroid such that no finite cocircuit of $M$ has odd size. Then the ground set of $M$ is a disjoint union of circuits.

Note that this theorem is only for finitary matroids, which means that all circuits are finite, not for infinite matroids in general. We will return to this point later. However, it turns out that the theorem above can be generalised slightly beyond binary matroids. It turns out that what we need to do is to make precise exactly what it is that is used about circuits in binary matroids for the base case of an argument of the kind outlined above.

Remember that the base case was that in which $M$ is countable. Our plan there was to recursively define a sequence of disjoint circuits $C_1, C_2, \ldots$ covering the ground set. To define $C_n$, we need that even after we have deleted the circuits $C_1, \ldots, C_{n-1}$ there is still at least one more circuit to choose as $C_n$. To ensure that we ultimately cover the whole ground set, we also need that we can choose this new circuit to contain our favourite edge $e$ of $M$. We can formalise all of this as follows:

**Definition:** A matroid $M$ is *finite matching extendable* if for any finite list $C_1, \ldots C_{n-1}$ of disjoint circuits of $M$ and any edge $e$ of $M$ not in any $C_i$ there is some circuit $C_n$ of $M$ containing $e$ and disjoint from all the other $C_i$.

So what we are using to prove the base case in our argument for finitary binary matroids is the fact that they are finite matching extendable. Komjáth, Milner and Polat showed [2] that this property also suffices for the general case.

**Theorem 3:** Let $M$ be any finitary matroid which is finite matching extendable. Then the ground set of $M$ is a disjoint union of circuits.

Once again, Komjáth, Milner and Polat’s proof was tricky and technical. However, using the Elementary Submodel Method, Attila Joó and I were able to give a much shorter alternative proof.

Instead of generalising Theorem 1 to matroids, a natural question to ask is what happens for directed graphs. More precisely, a natural question to ask in this context is which directed graphs can be expressed as a disjoint union of directed cycles. After a little thought, it is clear that the following statement is the analog of Theorem 1 for directed graphs:

**Theorem 4: **Let $D$ be any directed graph such that every for every cut $K$ of $D$ the sets of edges crossing $K$ in each direction have the same cardinality. Then $D$ is a disjoint union of directed cycles.

The history of this statement is a little peculiar. After proving Theorem 1 in 1960, Nash-Williams claimed that his methods could also be extended to give Theorem 4. However, he did not explain how to do so, and over the decades nobody else was able to reconstruct such a proof. Finally, in 2017 Thomassen gave Theorem 4 as a conjecture in [5], and a few years later this conjecture was finally proved by Attila Joó [1] using the Elementary Submodel Method.

Since we could generalise Theorem 1 to matroids, it is natural to ask whether we can also generalise Theorem 4 to matroids. And indeed we can, namely to regular matroids. To understand the statement, we need to understand what the analog of a directed cycle in a regular matroid might be. A quick way to express the concept we need is by using an alternative characterisation of regular matroids due to White [6].

**Definition****:** A *signing* of a matroid $M$ consists of a choice, for each circuit $C$ of $M$, of a function $f_C \colon C \to \{-1, 1\}$ and a choice, for each cocircuit $D$ of $M$, of a function $g_D \colon D \to \{-1, 1\}$, such that for any circuit $C$ and cocircuit $D$ we have $$\sum_{e \in C \cap D} f_C(e)g_D(e) = 0\,.$$ A signed matroid is a matroid together with a signing of that matroid.

**Fact:** A matroid $M$ is regular if and only if it has a signing.

For example we can find a signing of the matroid associated to any graph $G$ by directing the edges of $G$ arbitrarily, defining each $f_C$ to be 1 on the edges directed in one sense around $C$ and -1 for the edges directed in the opposite sense, and defining each $g_D$ to be 1 on the edges crosssing $D$ in one direction and -1 on the edges crossing $D$ in the opposite direction. The desired equation holds since each cycle crosses each cut the same number of times in each direction.

In this context, it is clear what the analog of a directed cycle should be. We say that a circuit $C$ (or cocircuit $D$) of a signed matroid is *directed* if $f_C$ (or $g_D$) is constant. Attila and I were able to extend Theorem 4 to regular matroids as follows:

**Theorem 5:** Let $M$ be a finitary signed matroid such that for any cocircuit $D$ of $M$ the sets $g_D^{-1}(-1)$ and $g_D^{-1}(1)$ have the same cardinality. Then the ground set of $M$ is a disjoint union of directed circuits.

All of the matroidal statements we have considered here were for finitary matroids. The reason for this, however, is not that they are known to be false for infinitary matroids. Indeed, there are no known counterexamples even for general infinite matroids. I would be very interested in any ideas for how to prove or refute the corresponding statements for arbitrary infinite matroids.

However there is an even more basic statement from which the countable case of Theorem 5 quickly follows, which is also open for general infinite matroids. It is an analog of the Farkas Lemma for signed matroids. It would probably be needed for any proof of Theorem 5 for general infinite matroids. So I would be extremely interested in any ideas on how to approach this problem.

**Conjecture:** Let $M$ be a (possibly infinite) signed matroid and $e$ an edge of $M$. Then $e$ is either contained in a directed circuit or a directed cocircuit.

**References:**

[2] Péter Komjáth, Eric Charles Milner, and Norbert Polat. “A compactness theorem for perfect matchings in matroids”. In: Journal of Combinatorial Theory, Series B 44.3 (1988), pp. 253–262.

[3] C. St. J. A. Nash-Williams. “Decomposition of graphs into closed and endless chains”. In: Proceedings of the London Mathematical Society 3.1 (1960), pp. 221–238.

[4] Lajos Soukup. “Elementary submodels in infinite combinatorics”. In: Discrete Math- ematics 311.15 (2011), pp. 1585–1598.

[5] Carsten Thomassen. “Nash-Williams’ cycle-decomposition theorem”. In: Combina- torica 37.5 (2017), pp. 1027–1037.

[6] Neil White. Matroid applications. 40. Cambridge University Press, 1992.

Given the importance of this problem, I’m surprised that I haven’t seen more work on it from the matroid theory community. So this blog post aims to publicize the area, share some questions I have been wondering about, and ask the community for pointers to more work in this direction.

We consider classes of binary matroids which are closed under minors. For which such classes is the sparsity at most linear in the rank? Parallel edges cause silly problems, so we only consider the simple matroids in the class. If the number of elements is not linear in the rank, then neither is the sparsity. So a necessary condition is that the class forbids the cycle matroid of some clique. Is this obvious necessary condition also sufficient? Surely not, right?!

**Problem 1:** Is it true that for each integer $t$, there exists an integer $c=c(t)$ so that if $M$ is a simple rank-$r$ binary matroid without a minor isomorphic to the cycle matroid of a $t$-vertex clique, then $M$ has a representation with at most $c r$ many $1$’s?

Such a matroid $M$ has at most linearly many elements by the Growth Rate Theorem. Problem 1 asks if we can additionally bound the average number of $1$’s per column. This is possible for graphic classes since we can just take the incidence matrix. However, I would guess that the answer is no in general, even for matroids of bounded branch-width.

What if we only consider representations which are in reduced row echelon form? This added restriction probably makes it much harder to sparsify. For a graph $G$ from a minor-closed class, this means that we want to bound the minimum, over all spanning trees $T$, of the average length of a fundamental cycle. (For each edge $e \in E(G) \setminus E(T)$ , its *fundamental *cycle is the unique cycle of $T+e$.) The best candidate I have found for a graph that is not sparsifiable in this sense is a big grid.

**Problem 2:** Is it true that for each integer $k$, there exists an integer $n=n(k)$ so that if $T$ is any spanning tree of the $n \times n$ grid, then the average length of a fundamental cycle with respect to $T$ is at least $k$?

Pablo Blanco’s undergraduate thesis [1] at Princeton considered another notion of sparsity which is typically harder to obtain. From the matrix perspective, we want to find a matrix which is in reduced row echelon form and, additionally, avoids an all $1$’s submatrix of fixed size. He proposed a conjecture about graphs which suggests that the main obstructions are the following (planar) graph and its dual. The $k$-banana is the graph which is obtained from $k$ paths of length $k$ by identifying all of their starting vertices into one vertex $s$, and all of their ending vertices into one vertex $t$.

Let me also point out that Kristýna Pekárková has a really nice master’s thesis [2] which takes care of the bounded branch-depth case of sparsification quite nicely.

[1] Pablo Blanco, Graphs with Large Overlap in Their Spanning Trees, click here for info

[2] Kristýna Pekárková, Matroid Based Approach to Matrix Sparsification, click here for pdf

]]>A fundamental problem in integer programming is to solve the following Integer Linear Program (ILP): find $\textrm{max}\{c^Tx \mid Ax \le b \textrm{ and } x \in \mathbb Z^n\}$ where $A \in \mathbb Z^{m \times n}$, $b \in \mathbb Z^m$, and $c \in \mathbb Z^n$. This problem is $\mathcal N\mathcal P$-hard, but we can hope for better efficiency if the matrix $A$ has special structure. Given a positive integer $\Delta$, an integer matrix $A$ is *$\Delta$-modular* if the absolute value of every $\textrm{rank}(A) \times \textrm{rank}(A)$ submatrix of $A$ is at most $\Delta$. A classic result of Hoffman and Kruskal [HK56] implies that ILPs over 1-modular (or *unimodular*) matrices can be solved in strongly polynomial time. After about 60 years with little progress, a breakthrough result of Artmann, Weismantel, and Zenklusen showed that ILPs over 2-modular (or *bimodular*) matrices can be solved in strongly polynomial time [AWZ17]. Determining the complexity for solving ILPs over $\Delta$-modular matrices with $\Delta \ge 3$ is a major open problem in the theory integer programming.

The proof of Artmann, Weismantel, and Zenklusen heavily relies on structural properties of 2-modular matrices. This is where matroids come in! For each positive integer $\Delta$ we say that a matroid is *$\Delta$-modular* if it has a representation over $\mathbb Q$ as a $\Delta$-modular matrix, and we write $\mathcal M_{\Delta}$ for the class of $\Delta$-modular matroids. The hope is that studying $\mathcal M_{\Delta}$ via techniques from structural matroid theory will uncover new properties of $\Delta$-modular matrices that are relevant for integer programming. However, $\mathcal M_{\Delta}$ is also a very natural class of matroids, because $\mathcal M_1$ is precisely the class of regular matroids!

Even though $\mathcal M_{1}$ is fundamental in integer programming and matroid theory, little is known about $\Delta$-modular matroids when $\Delta \ge 2$. Below is a list of five properties that will likely be important for future work with these matroids.

**Property 1:** For all $\Delta \ge 1$, the class $\mathcal M_{\Delta}$ is closed under minors and duality.

Closure under minors was proved in [Proposition 8.6.1, GNW22] and closure under duality was proved by D’Adderio and Moci [Theorem 2.2, DM13] using arithmetic matroids, although a more direct proof due to Marcel Celaya can be found in [Theorem 4.2, OW22]. Of course, Property 1 is crucial for using techniques from structural matroid theory to study $\mathcal M_{\Delta}$.

**Property 2:** For all $\Delta \ge 1$, every matroid in $\mathcal M_{\Delta}$ is representable over every field with characteristic greater than $\Delta$.

This follows from the fact that if $A$ is a $\Delta$-modular matrix and $p$ is a prime greater than $\Delta$, then the set of all $\textrm{rank}(A)\times \textrm{rank}(A)$ submatrices of $A$ with non-zero determinant does not change if we perform all calculations modulo $p$. In particular, every matroid in $\mathcal M_2$ is dyadic, and every matroid in $\mathcal M_3$ is $\textrm{GF}(5)$-representable. Also, since there is a prime in the interval $(\Delta, 2\Delta]$ by Chebyshev’s Theorem, Property 2 implies that the uniform matroid $U_{2, 2\Delta + 2}$ is not in $\mathcal M_{\Delta}$. Again, Property 2 is crucial because it allows for the potential use of tools from the study of matroids representable over partial fields.

**Property 3:** When $\Delta \ge 2$, the class $\mathcal M_{\Delta}$ is not closed under direct sums.

This is where $\mathcal M_{\Delta}$ differs from matroid classes defined by representability over a partial field, which are always closed under direct sums. Intuitively, Property 3 is true because a block-diagonal matrix for which each block is $\Delta$-modular may not be $\Delta$-modular itself. As a particular example of Property 3, the uniform matroid $U_{2,4}$ is in $\mathcal M_2$, but $U_{2,4} \oplus U_{2,4}$ is not in $\mathcal M_2$ [Proposition 4.4, OW22].

**Property 4:** If $r$ is sufficiently large as a function of $\Delta$, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + 80\Delta^7 \cdot r$ elements [Theorem 1.3, PSWX24].

The problem of finding upper bounds on the number of columns of a rank-$r$ $\Delta$-modular matrix has received a lot of recent attention, because this also provides bounds for important parameters associated with ILPs over $\Delta$-modular matrices; see [LPSX23] for details. The bound in Property 4 was proved with techniques from matroid theory, and is currently the best known bound for fixed $\Delta$.

**Property 5:** $\mathcal M_{\Delta}$ contains no spikes with rank greater than $2\Delta$ [Proposition 2.1, PSWX24].

This was a key fact used in the proof of Property 4, and also differs from the typical situation for matroids over partial fields. Since spikes are notoriously `wild’, this is good news!

Since the study of $\Delta$-modular matroids is so new, there are many open problems.

**Problem 1:** Let $\mathcal M_{\Delta}^t$ be the class of matroids with a representation as a totally $\Delta$-modular matrix. Is $\mathcal M_{\Delta}^t = \mathcal M_{\Delta}$?

An integer matrix $A$ is *totally $\Delta$-modular* if the determinant of every square submatrix has absolute value at most $\Delta$. When $\Delta \le 2$, every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so Problem 1 has an affirmative answer when $\Delta \le 2$. However, when $\Delta \ge 3$ it is unclear whether every $\Delta$-modular matrix is projectively equivalent to a totally $\Delta$-modular matrix, so new ideas may be needed.

**Problem 2:** Find an absolute constant $C$ so that if $r$ is sufficiently large, then every simple rank-$r$ matroid in $\mathcal M_{\Delta}$ has at most $\binom{r+1}{2} + C\Delta\cdot r$ elements.

This is a natural next step from the bound in Property 4. There is a lower bound of $\binom{r+1}{2} + (\Delta – 1)(r – 1)$ that holds for all $\Delta \ge 1$ (see [Proposition 1, LPSX23]), so the bound in Problem 2 would be tight up to the constant $C$. While this lower bound is the correct answer for $\Delta = 1$ [Hel57] and $\Delta = 2$ [OW22, LPSX23], a recent construction of Averkov and Schymura [Theorem 1.3, AS22] does better for $\Delta \in \{4, 8, 16\}$, so there is no obvious choice for $C$ that is tight for all $\Delta$.

**Problem 3: **Find a class $\mathcal N$ of matroids so that ILPs with $\Delta$-modular constraint matrix $A$ with $M(A) \in \mathcal N$ can be solved in polynomial time.

This is in the spirit of a recent result showing that ILPs over $\Delta$-modular matrices for which each row has at most two nonzero entries can be solved in strongly polynomial time [FJWY22]. Perhaps the most interesting choice for $\mathcal N$ would be the class of projections of graphic matroids, because the matroids in $\mathcal M_{\Delta}$ providing the best known lower bound in Problem 2 are projections of graphic matroids.

**Problem 4: **Find the list of excluded minors for $\mathcal M_{2}$.

Since $\mathcal{ M}_{\Delta}$ is minor-closed and every matroid in $\mathcal M_{\Delta}$ is representable over finite fields by Property 2, Rota’s Conjecture says that $\mathcal M_{\Delta}$ has a finite list of excluded minors. Tutte showed that $\mathcal M_{1}$ has only three excluded minors: $U_{2,4}$, the Fano plane $F_7$, and its dual $F_7^*$ [Tut58]. It should be feasible (but difficult) to use existing techniques to find the list of excluded minors when $\Delta = 2$; there is a more detailed discussion in [OW22].

**Problem 5: **Find a decomposition theorem for $\mathcal M_{2}$.

Seymour’s celebrated decomposition theorem says that every internally $4$-connected matroid in $\mathcal M_1$ is graphic, cographic, or a specific $10$-element matroid $R_{10}$ [Sey80]. Do matroids in $\mathcal M_2$ satisfy a similar property? If a decomposition can be found efficiently for $\mathcal M_2$, it would have several interesting consequences. For example, it would likely give a new proof that ILPs over 2-modular matrices can be solved in polynomial time. It would also likely give a polynomial-time algorithm for determining if a given matrix is 2-modular; this recognition problem is open for $\Delta$-modular matrices when $\Delta \ge 2$. While Problem 5 is certain to be difficult, it would likely be worthwhile to use the approach of [MNvZ11] and [CMN15] to systematically study what such a decomposition would look like. Of course, this problem is also highly interesting for $\mathcal M_{\Delta}$ with $\Delta \ge 3$.

[AWZ17] S. Artmann, R. Weismantel, R. Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In *Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing*, pages 1206-1919, 2017.

[AS22] G. Averkov, M. Schymura. On the maximal number of columns of a Delta-modular matrix. In K. Aardal and Laura L. Sanità, editors, *Integer Programming and Combinatorial Optimization*, pages 29-42, Cham, 2022. Springer International Publishing.

[CMN15] C. Chun, D. Mayhew, M. Newman. Obstacles to decomposition theorems for sixth-root-of-unity matroids. *Ann. Combin.*, 19:79-93, 2015.

[DM13] M. D’Adderio, L. Moci. Arithmetic matroids, the Tutte polynomial, and toric arrangements. *Adv. in Math.*, 232:335-367, 2013.

[FJWY22] S. Fiorini, G. Joret, S. Weltge, Y. Yuditsky. Integer programs with bounded subdeterminants and two nonzeros per row. In *2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 13-24, 2022.

[GNW22] J. Geelen, P. Nelson, Z. Walsh. Excluding a line from complex-representable matroids. To appear in *Mem. Amer. Math. Soc.*

[Hel57] I. Heller. On linear systems with integral valued solutions. *Pac. J. Math.*, 7(3):1351-1364, 1957.

[HK56] A. Hoffman, J. Kruskal. Integral boundary points of convex polyhedra. *Linear Inequalities and Related Systems*, 24:223-246, 1956.

[LPSX23] J. Lee, J. Paat, I. Stallknecht, L. Xu. Polynomial upper bounds on the number of differing columns of Delta-modular integer programs. *Math. Oper. Res., *48(4):1811-2382, 2023.

[MWvZ11] D. Mayhew, G. Whittle, S. H. M. van Zwam. An obstacle to a decomposition theorem for near-regular matroids. *SIAM J. Disc. Math.*, 25(1):271-279, 2011.

[OW22] J. Oxley, Z. Walsh. 2-Modular matrices. *SIAM J. Disc. Math.*, 36:1231-1248, 2022.

[PSWX24] J. Paat, I. Stallknecht, Z. Walsh, L. Xu. On the column number and forbidden submatrices for Delta-modular matrices. *SIAM J. Disc. Math.*, 38:1-18, 2024.

[Sey80] P. D. Seymour. Decomposition of regular matroids. *J. Combin. Theory Ser. B*, 28:305-359, 1980.

[Tut58] W. T. Tutte. A homotopy theorem for matroids, I, II. *Trans. Amer. Math. Soc.*, 88, 144-174, 1958.

]]>

**Time:** Wednesday, April 24 at 3pm ET**Zoom: **https://gatech.zoom.us/j/8802082683

**Speaker:** James Oxley, Louisiana State University**Title:** The legacy of Dominic Welsh

**Abstract:** Dominic Welsh wrote the first comprehensive text on matroids. He supervised 28 doctoral theses and wrote over 100 papers and five books. As impressive as these numbers are, they fail to truly capture the spirit of the man who inspired generations of students and imbued them with not only a love of mathematical beauty but with a deep and abiding affection for the man himself. Dominic died in November, 2023. The speaker will attempt to capture some of the key aspects of his legacy.

In this post, we are going to discuss a bit about the intersection between algebraic geometry and matroid theory. We are all aware that June Huh, in a series of three papers, along with Eric Katz and Karim Adiprasito, developed and extended tools that led to the proof of the Heron–Rota–Welsh unimodality conjecture as well as many other open conjectures [3, 2, 1]. I once asked Huh what type of mathematition he considered himself. I, coming from structural matroid theory, initially viewed his work as a subset of algebraic geometry, but he replied that he viewed himself as a combonatorialist. I have spoken to many other mathematitions who consider themselves matroid theorists, despite not doing structural matroid theory and not having attended the sorts of conferences that I attended as a graduate student doing structural matroid theory. While we will not discuss the tools used to prove the Heron–Rota–Welsh unimodality today, this post is intended to add a bridge to the wide world of matroid theory which makes use of algebraic tools. Of course, many other mathematitions have created tools to help structural matroid theorists understand the type of matroid theory that they do.

**A Combinatorial Description of (Minimal) Tropical Basis**

Imagine for a moment that you and a mathematical friend are captured by an scheming matroid theorist (**SMT**). The **SMT** explains that they are going to tell you a matroid, and your friend the ground est of the matroid. The two of you will be freed when your friend can reveal the matroid to the **SMT**. To communicate the matroid, you are allowed to tell your friend one circuit of the matroid a day, and allowed to tell your friend when you are done telling them circuits. Your objective is to come up with a strategy that will define a matroid by a subset of the circuits. Of course, we could list every circuit, but we would like to get out of imprisonment sooner, and hence list less than every circuit.

We may be tempted, to make use of fact that binary matroids can be completely determined by listing all fundamental circuits with respect to a particular basis. But this requires, not only that we have a binary matroid, but also requires that we have a promise that our matroid is binary.

For instance, consider the graphic matroid $M(K_4)$, as labeled below. Knowing the fundamental circuits associated with the basis $\{1, 2, 3\}$, isn’t enough information to determine if $\{4, 5, 6\}$ is a circuit or not. To see this, note that both the wheel and the whirl associated with this graph have circuits $\{1,2,6\}$, $\{1,3,5\}$, and $\{2,3,4\}$.

Our strategy will involve giving our friend enough information to determine which subsets of the ground set of $M$ are flats of $M$. Note that knowing that a set $C$ is a circuit of a matroid communicates a number of sets which are not flats of a matroid. For a circuit $C$ of $M$, and a subset $X\subseteq E(M)$, we say that $C$ * excludes* $X$ when $|C-X|=1$. For instance, the circuit ${0,1,2}$ of $U_2,4$ excludes the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$. That is, we know that the subsets $\{\{0,1\}, \{0,2\}, \{1,2\}, \{0,1,3\}, \{0,2,3\}, \{1,2,3\}\}$ are non-flats of a matroid $M$, just by knowing that $\{0,1,2\}$ is a circuit of $M$.

**Example: $U_{2,4}$**

Suppose, that the **SMT** gives us the matroid $M=U_2,4$ on the ground set

$\{0,1,2,3\}$. Then the flats and non-flats of $M$ are:

Flats: $\emptyset$, $\{0\}$, $\{1\}$, $\{2\}$, $\{3\}$, $\{0,1,2,3\}$

Non-Flats: $\{1,2\}$, $\{1,2\}$, $\{1,3\}$, $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, $\{2,3\}$, $\{0,1,2\}$, $\{0,1,3\}$, $\{1,2,3\}$

The circuit $\{0,1,2\}$ excludes 6 of the 10 non-flats.

The circuit $\{0, 1, 3 \}$ will exclude an additional 3 non-flats, namely the flats $\{\{0, 3 \}, \{1, 3 \}, \{0, 1, 2 \} \}$. Finally, the circuit $\{0, 2, 3\}$ will exclude the set $\{2, 3,\}$.

Since the collection $\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 2, 3\} \}$ collectively excludes all the non-flats of $U_{2,4}$, we can give just these three circuits to our friend, and they will be able to determine the matroid.

**Combinatorial Definition and Some Intuition**

It is often useful for us to think of subsets of $[n]$ as 0-1 vectors where a vector is identified with its support. That is, a 0-1 vector $(a_0, a_2, \ldots, a_{n-1}$ represents the subset $\{x\in[n]: a_x=1\}$. For instance, $(1,0,1,0)$ represents the subset ${0,2}$ of $[4]$ because the non-zero entries of $(1,0,1,0)$ occur in the 0th and 2nd entries.

Let $M$ be a matroid on $\{0,1,\ldots, n-1\}$. We say a circuit $C$ of $M$ **excludes** a vector $x=(x_0, x_2, \ldots, x_{n-1})\in\{0,1\}^n$ if for exactly one $e\in C$, the entry $x_e=0$.

A collection $\mathscr{C}’\subset\mathscr{C}(M)$ is a * tropical basis* of $M$ if for every non-flat $S$ of $M$, there is a circuit in $\mathscr{C}’$ that excludes $S$. This was not the original definition of a tropical basis, but rather was due to Josephine Yu and Debbie S. Yuster [5].

To test if they understand the definition of a tropical basis, the reader can ask themselves why $\mathscr{C}$ is always a tropical basis of $M$.

If $e$ is a loop, then $\{e\}$ is in every tropical basis of $M$. To see this, note that

if $e$ is a loop, then $E(M)-e$ is a non-flat of $M$. The only circuit $C$ with $|C-(E-e)|=1$ is $\{e\}$.

For a tropical basis $\mathscr{C}’$ of $M$,

we say that $\mathscr{C}’$ is * minimal* if

for all $C\in\mathscr{C}’$,

the collection $\mathscr{C}’-C$ is not a tropical basis of $M$.

We might imagine that all minimal tropical bases of a matroid $M$ would have the same cardinality, but this in not the case. To see this, we will consider different tropical bases on $U_{2,5}$. This example is from Yu and Yuster’s paper [5].

**Example: Minimal Tropical Bases for $U_{2,5}$**

The nonflats of $M=U_{2,5}$ consist of all subsets of $\{0,1,2,3,4\}$ of size two, three, or four. Let $\mathscr{C}_1=\{C\in\mathscr{C}: 0\in C\}$, and let $\mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \}, \{2, 3, 4\} \}$. Note that $\mathscr{C}_1\cap \mathscr{C}_2=\{ \{0, 1, 2\}, \{0, 1, 3\}, \{0, 1, 4\}, \{0, 2, 3 \} \}$. To see that $\mathscr{C}_1$ and $\mathscr{C}_2$ are tropical basis, we first note that every non-flat of $M$ besides $\{2,4\}$ and $\{3,4\}$ is excluded by a circuit in $\mathscr{C}_1\cap \mathscr{C}_2$. Both of these non-flats are excluded by $\{2,3,4\}$, so $\mathscr{C}_2$ is a tropical basis of $M$. Lastly, $\{2,4\}$ is excluded by $\{0,2,3\}$ but not by $\{0,3,4\}$, and $\{3,4\}$ is excluded by $\{0,3,4\}$ but not by $\{0,2,3\}$. So $\mathscr{C}_1$ is a tropical basis of $M$.

To see that these Tropical bases are minimal, we note that the set $\{a,b\}\in\{ \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}\}$ is excluded by the circuit $\{0,a,b\}$, but not by any other circuit in in $\mathscr{C}_1\cup\mathscr{C}_2$.

**Origional Definiton of Tropical Basis**

To give the original definition, we must first understand some basic definitions in algebraic geometry. A reader who has no interest in algebraic geometry can safely skip this section.

A set is a * variety* if it is the solution set to some system of polynomials. For instance, the types of graphs that we drew in pre-algebra would be varieties over $\mathbb{R}^2$.

From these examples, one might guess that the union or intersection of two varieties is itself a variety. This turns out to be true.

The * Tropical Semi Ring* is defined by:

$$\mathbb{T}=\{\mathbb{R}\cup\infty,\oplus,\odot\}$$

$$x\oplus y=min\{x,y\}\quad\quad\quad x\odot y=x+y$$

For example, $2\oplus 7=2$ and $2\odot 7=9$.

Note that $\infty$ is the additive identity, and $0$ is the multiplicative identity.

When working with tropical numbers, generally, $(x-a)=0$ has no solution. Instead, we define a * Tropical Variety* as the set of points when a polynomial obtains its minimum at least twice.

For example, consider the linear polynomial

$$f(x,y)=2\odot x\oplus 1\odot y\oplus 4.$$

The variety of $f$ is equal to the set when $\min\{2+x, 1+y, 4\}$ occurs twice in the set $\{2+x, 1+y, 4\}$. When drawing tropical varieties, it can help to begin by drawing in dotted lines when any two monomials have the same value, and then fill in the parts of those dotted lines, when that value achieves the value of the polynomial. In this case, that gives us:

**For a linear polynomial $f$, we call the tropical variety associated with $f$ a *** tropical hyperplane*.

Now, for a circuit $C$ of a matroid $M$, define

$f_C(\vec{v})=\bigoplus_{e\in E} c_e\odot x_e$, where

$c_e=

\begin{cases}

0 & e\in C \\

1 & e\not\in C

\end{cases}.

$

For example, if we take $M=U_{2,5}$ and $C=\{1,2,3\}$, then

$$f_C=(0\odot x_1)\oplus (0\odot x_2)\oplus (0\odot x_3)\oplus (\infty\odot x_4)\oplus (\infty\odot x_5).$$

Consider the non-flat $\{1,2,4\}$ as an indicator vector $(1,1,0,1,0)$.

We compute $f_C(1,1,0,1,0)=(0\odot 1)\oplus (0\odot 1)\oplus (0\odot 0)\oplus (\infty\odot 1)\oplus (\infty\odot 0).$

The $min\{0+1,0+1,0+0,\infty + 1, \infty +0\}$ achieves it’s minimum only once, so $(1,1,0,1,0)$ is not in the tropical hyperplane associated with $\{1,2,4\}$.

We denote the tropical hyperplane associated with $f_C$ as $T(C)$. That is, $T(C)$ is the space of all vectors $v$ where $f_C(v)$ achieves it’s minimum twice.

For $\mathscr{C}’\subseteq\mathscr{C}(M)$, we define $T(\mathscr{C}’)$ as $\bigcap_{C\in\mathscr{C}}’T(C)$.

A set $\mathscr{C}’\subseteq\mathscr{C}$ is a * tropical basis* for $M$ if $T(\mathscr{C}’)=T(\mathscr{C})$.

**Lemma**[5]

For any $\mathscr{C}’\subseteq \mathscr{C}$,

$$T(\mathscr{C}’)\cap\{0,1\}^n=T(\mathscr{C})\cap\{0,1\}^n$$ if and only if $$T(\mathscr{C}’)=T(\mathscr{C}).$$

Before we give the proof of this lemma, it is important to note that this lemma is the essential reason why we are able to use the combinatorial definition of a tropical basis. Intersecting spaces with indicator vectors allows us to only consider the vectors which can be viewed as as subsets of the ground set of a matroid.

**Proof**

Of course $T(\mathscr{C})\subseteq T(\mathscr{C}’)$. So suppose that $x \in T(\mathscr{C}’)-T(\mathscr{C})$. We need to find an $\tilde{x}\in (T(\mathscr{C}’)\cap\{0,1\}^n)-(T(\mathscr{C})\cap\{0,1\}^n)$.

Since $x\not\in T(\mathscr{C})$, there is some circuit $C_x\in \mathscr{C}$, that excludes $x$, that is $\{x_i:i\in C_x\}$ has a unique minimum $m$.

\[\tilde{x}= \begin{cases}

1 & \text{if } x_i>m\\

0 & \text{if } x_i \leq m.

\end{cases}

\]

$\tilde{x}$ is excluded by $C_x$ because $\{\tilde{x}_i:i\in C_x\}$ achieves it’s minimum exactly when $\{x_i:i\in C_x\}$ has its unique minimum. So $\tilde{x}$ is not in $T(\mathscr{C})$. For any circuit $D$ where $\{x_i:i\in D\}$ achieves its minimum twice, so does $\{\tilde{x}_i:i\in D\}$. So no circuit of $\mathscr{C}’$ excludes $\tilde{x}$.

**Open Questions**

People have been interested in finding canonical minimal tropical bases for common classes of matroids. In particular, Yu and Yuster [5] asked as an open question to find a minimal tropical basis for an arbitrary transversal matroid. They gave a rather nice description o a canonical minimal tropical basis for uniform matroids.

Yu and Yuster [5] also showed that graphic matroids, cographic matroids, and $R_{10}$ have unique minimal tropical basis. They hypothesised that all regular matroids would have a unique minimal tropical basis. In fact, Yasuhito Nakajima [4] showed that all binary matroids have a unique minimal tropical basis.

Nakajima [4] also showed that having a unique minimal tropical basis was not closed under taking minors. The example that they gave also shows that some non-binary matroids have a unique minimal tropical basis.

It would be nice to have a characterization of which matroids had a unique minimal tropical basis.

[1] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Annals of Mathematics 188 (2018), 381–452.

[2] June Huh, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs,Journal of the American Mathematical Society 25 (2012), 907–927.

[3] June Huh and Eric Katz, Log-concavity of characteristic polynomials and the Bergman fan of matroids, Mathematische Annalen 354 (2012), 1103–1116.

[4] Yasuhito Nakajima, Minimal tropical basis for Bergman fan of matroid, arXiv

preprint arXiv:1901.06893 (2019), https://arxiv.org/abs/1901.06893, doi:

10.48550/arXiv.1901.06893, Submitted on 21 Jan 2019 (v1), last revised 21 Feb 2019 (this

version, v2).

[5] Josephine Yu (UC Berkeley) and Debbie S. Yuster (Columbia University), Representing trop-

ical linear spaces by circuits, arXiv:math/0611579 [math.CO], https://arxiv.org/abs/math/

0611579, doi: 10.48550/arXiv.math/0611579.

]]>

We plan to bring together 50-70 researchers from all over the world. We are enthusiastic about making this workshop an opportunity for graduate students and postdoctoral fellows, especially those who have had limited opportunities for research collaborations and in-person meetings. If you or your students who would like to attend, please send an email to the address below. We may be able to offer some funding to support graduate students and postdocs, so please let us know if this could be helpful.

More information is posted on the conference website: https://indico.ibs.re.kr/e/wmm2024

You can contact us using the address matroids@proton.me.

Organizers: Spencer Backman, Rutger Campbell, Dillon Mayhew, Sang-il Oum.

Dates: August 19 – 23, 2024. We start Monday morning and finish Friday at the end of the afternoon. We expect most people to arrive on Sunday, August 18 and leave on Saturday, August 24.

The workshop is by invitation only.

The organizers have contacted the following nearby hotels for discounts for the participants.

- ICC Hotel: A 2-star hotel within a short walking distance (about 800m). Please fill out this form and send it to the ICC hotel email address to secure a reservation at a discounted rate. Expect to pay around 100 USD per night. Free breakfast.
- I-Hotel: Formerly a guest house for visitors to research institutions in Daejeon. It is in the same neighbourhood as the ICC Hotel and next to the famous bakery cafe (Sungsimdang) of Daejeon. Visit the iHotel website, fill out the form, and send it. You can pay the accommodation fee upon check-in. After the IBS discount, expect to pay about 35 USD per night for a single one-person room or 46 USD for a two-person room.

Let $\mathbb{F} \subseteq \mathbb{K}$ be fields. Let $E$ be a finite subset of $\mathbb{K}$ and let $\{Y_e: e \in E\}$ be a set of indeterminates indexed by $E$. A subset $S \subseteq E$ is *algebraically independent over $\mathbb{F}$* if whenever $F \in \mathbb{F}[Y_e: e \in E]$ is a polynomial that only includes the variables $\{x_e : e \in S\}$, then $F$ vanishes when plugging in $e$ for $Y_e$ if and only if $F$ is identically zero. The subsets of $E$ that are algebraically independent over $\mathbb{F}$ are the independent subsets of a matroid, called the *algebraic matroid of *$E$. A matroid $M$ that can be realized in this way is said to be *algebraic over *$\mathbb{F}$.

Let $\mathbb{F}$ be any field and define $\mathbb{K} := \mathbb{F}(x,y,z,w)$, the field of rational functions in four variables over $\mathbb{F}$. Then define

$E := \{xy^{-1},xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1}\} \subseteq \mathbb{F}(x,y,z,w)$

The subset $I = \{xw^{-1},yw^{-1},zw^{-1}\}$ is algebraically independent over $\mathbb{F}$, whereas $xy^{-1},yz^{-1},xz^{-1}$ is not because if

$F(Y_{xy^{-1}},Y_{,xz^{-1}},Y_{xw^{-1}},Y_{yz^{-1}},Y_{yw^{-1}},Y_{zw^{-1}}) := Y_{xy^{-1}}Y_{yz^{-1}}-Y_{xz^{-1}}$

then $F(xy^{-1},,xz^{-1},xw^{-1},yz^{-1},yw^{-1},zw^{-1})= 0$.

The algebraic matroid of $E$ is the $\mathbb{Q}$-representable matroid defined by the following matrix over $\mathbb{Q}$

$A:=\begin{pmatrix} 1 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & -1 & 0 & -1 & 0 & 1 \\ 0 &0 & -1 & 0 & -1 & -1\end{pmatrix}$.

To see this, let $v \in \mathbb{Z}^6$ be such that $Av = 0$ and define

$v^+ = \left({\rm max}\{v_i,0\}\right)$ and $v^- = \left({\rm max}\{-v_i,0\}\right)$

so that $v = v^+-v^-$ and $v^+$ and $v^-$ are nonnegative with disjoint supports. Then the binomial

$Y_1^{v_1^+}Y_2^{v_2^+}Y_3^{v_3^+}Y_4^{v_4^+}Y_5^{v_5^+}Y_6^{v_6^+} \ – \ Y_1^{v_1^-}Y_2^{v_2^-}Y_3^{v_3^-}Y_4^{v_4^-}Y_5^{v_5^-}Y_6^{v_6^-}$

vanishes by plugging in $(Y_1,\dots,Y_6) = (xy^{-1},\dots,zw^{-1})$. For example, if $v = (1,-1,0,1,0,0)$ then $v^+ = (1,0,0,1,0,0)$ and $v^- = (0,1,0,0,0,0)$ and the corresponding binomial is $Y_1Y_4-Y_2$.

This procedure gives us a map $\phi$ from the set of integer vectors in the kernel of $A$ to the set of irreducible binomial differences that vanish on $E$. In fact, this map $\phi$ is a bijection and any irreducible polynomial relation among the elements of $E$ will be an irreducible binomial difference and so $\phi$ can be used to show that dependent sets in the algebraic matroid of $E$ correspond to dependent sets in the column matroid of $A$.

The above example generalizes. In particular, if $E \subseteq \mathbb{F}(x_1,\dots,x_r)$ is a set of monomials, then the algebraic matroid of $E$ is isomorphic to the algebraic matroid of the rational matrix $A$ whose column vectors are the exponent vectors of $E$. Since $\mathbb{F}$ was an arbitrary field, this proves the following.

**Theorem.** If $M$ is representable over $\mathbb{Q}$, then $M$ is algebraic over every field.

The converse of the above statement is false – the non-Pappus matroid is algebraic over every field, but not representable over $\mathbb{Q}$.

Every matroid that is linear over a field $\mathbb{F}$ is algebraic over that same field. In particular, the matroid of some $A \in \mathbb{F}^{r \times n}$ is the algebraic matroid of the entries of

$(x_1 \ \cdots \ x_r) A$

as elements of $\mathbb{F}(x_1,\dots,x_r)$. So every $\mathbb{F}$-linear matroid is also $\mathbb{F}$-algebraic. When $\mathbb{F}$ has characteristic zero, the converse is *almost* true. Namely, we have the following.

**Theorem.** Let $\mathbb{F}$ be a field of characteristic zero, let $\mathbb{K}$ be a field containing $\mathbb{F}$ and let $E$ be a finite subset of $\mathbb{K}$. Then the algebraic matroid of $E$ is linearly representable over $\mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate.

Here is a proof sketch for the special case where $\mathbb{K} = \mathbb{F}(t_1,\dots,t_r)$ where each $t_i$ is an indeterminate. Let $M$ denote the algebraic matroid of $E$. For each $e \in E$, let $v_e \in \mathbb{F}(t_1,\dots,t_r)$ be the formal gradient vector of $e$ (note that each $e$ is a polynomial in the $t_i$ variables). Then $\{v_e\}_{e \in E}$ is an $\mathbb{F}(t_1,\dots,t_r)$-linear representation of $M$. Indeed, if there is a polynomial relation among some subset $S \subseteq E$, then the gradient of that polynomial relation is a linear relation among $\{v_e : e \in S\}$. Conversely, each linear relation among a subset of $\{v_e: e \in E\}$ can be made into a polynomial relations among the corresponding subset of $E$.

The general case is proven using essentially the same idea, i.e. take derivatives to reduce to the linear case. Doing this without making assumptions on $\mathbb{K}$ requires the theory of *derivations* from commutative algebra

What fails in positive characteristic is that not every linear relation among the gradient vectors lifts to an algebraic relation among the corresponding polynomials. Consider for example the following set of monomials in $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,xy,xz,yz,xyz\} \subset \mathbb{F}_2(x,y,z)$

The corresponding matrix of exponent vectors is the following

$A = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 &1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1\end{pmatrix}$.

Since $A$ lives in $\mathbb{Q}^{3 \times 7}$, its matroid is the non-Fano matroid, and since this matroid is isomorphic to the algebraic matroid of $E$, this gives us an $\mathbb{F}_2$-algebraic representation of the non-Fano matroid. Since this is not representable over $\mathbb{F}_2$, we know that the above proof sketch should fail on this example. And it does. The matrix of gradient vectors for $E$, which lives in $\mathbb{F}_2(x,y,z)^{3 \times 7}$, is the following

$Gr = \begin{pmatrix} 1 & 0 & 0 & y & z & 0 & yz \\ 0 & 1 & 0 & x & 0 &z & xz \\ 0 & 0 & 1 & 0 & x & y & xy\end{pmatrix}$

The 3rd, 4th, and 5th columns are the gradients of $xy,xz$, and $yz$. Since this matrix has entries in a field of characteristic two, this 3×3 matrix has zero determinant. But $\{xy,xz,yz\}$ is an algebraically independent subset of $E$. To see this, look at the corresponding columns of the exponent vector matrix $A$:

$\begin{pmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{pmatrix}$.

The determinant of this matrix (which has entries in $\mathbb{Q}$, not $\mathbb{F}_2$) is $-2$, which is non zero in this field.

It is unknown if the dual of an algebraic matroid is algebraic. I see no reason for this to be the case, and I think we lack a counterexample showing this for two reasons. The first is that any such counterexample would have to be algebraic but non-linear. Over characteristic zero, the class of algebraic and linear matroids are the same, so this counterexample would have to come from a field of positive characteristic, where geometric interpretations of the algebraic picture are often misleading. The second reason is a lack of ways to certify that a matroid is not algebraic – the methods from the literature are specific to the examples they work on.

One example of a matroid that is algebraic but not linear is the algebraic matroid of the following subset of $\mathbb{F}_2(x,y,z)$

$E := \{x,y,z,x+y,x+z,y+z,x+y+z,xy,xz,yz,xyz\}$.

The matroid on the subset $\{x,y,z,x+y,x+z,y+z,x+y+z\}$ is the Fano matroid (which is only linear over characteristic 2) and the matroid on $\{x,y,z,xy,xz,yz,xyz\}$ is the non-Fano matroid (which is only representable over characteristics other than 2). So this matroid cannot be linear. I conjecture, perhaps a little too boldly, that the dual of this matroid is *not* algebraic.

**Update:**

Since publishing this blog post, Winfried Hochstättler reached out to me to share an example of a matroid of rank five on nine elements whose dual is known to be non-algebraic. It is unknown whether the matroid itself is algebraic. Click here to download a pdf describing this matroid.

]]>Graham Farr (Faculty of IT, Monash University, Clayton, VIC 3800, Australia; Graham.Farr@monash.edu),

Dillon Mayhew (School of Computing, University of Leeds, Leeds, LS2 9JT, UK; d.mayhew@leeds.ac.uk) and

James Oxley (Mathematics Department, Louisiana State University, Baton Rouge, LA 70803-4918, USA; oxley@math.lsu.edu)

The Matroid Theory community has lost one of its greatest leaders and most treasured members with the death of Dominic Welsh on 30 November 2023.

*Dominic Welsh at home in Oxford, mid- to late 1980s; photo by James Oxley*

Dominic had wide-ranging interests and many collaborators (57 listed in MathSciNet). Most of his research was in at least one of three main themes: discrete probability, matroids and graphs, and computational complexity. These themes are captured well in the title *Combinatorics, Complexity and Chance* of the tribute volume (edited by Geoffrey Grimmett and Colin McDiarmid) published by Oxford University Press in 2007, soon after he retired. That book is an excellent source of reflections on Dominic’s work. It includes Oxley’s chapter on “The contributions of Dominic Welsh to matroid theory” which is a source of further information and reflections on that theme in Dominic’s work. Here we will try to give an overview of his career, emphasising his work on matroids but also putting it in the context of his range of interests and attempting to trace some of the sources of his remarkable influence. We have divided his research career into four phases: probability, matroids, complexity, and Tutte polynomials. The boundaries between these phases are not sharp, and each phase contained some seeds of later phases.**First phase: discrete probability**

Dominic’s doctoral research (DPhil, 1964) was about probabilistic processes on discrete structures. One important example was percolation on square-lattice graphs, in which information spreads out from the origin according to some local randomness on the edges or vertices. Questions concern the probability of spreading to a particular extent and the time taken to do so. This topic had been pioneered in the late 1950s by Dominic’s doctoral supervisor, John Hammersley (1920–2004), an eminent probability theorist. Hammersley did not have a PhD/DPhil, though he was awarded Doctor of Science degrees later in his career by Cambridge and Oxford Universities.

Dominic recalled that Hammersley had a plain-speaking, direct manner in research supervision which worked well for him. On one occasion, Dominic turned up to one of their meetings and confessed that he hadn’t done anything since their previous meeting. Hammersley ended the meeting immediately and told him to come back when he’d done some work! Geoffrey Grimmett writes of Hammersley that “his unashamed love of a good problem has been an inspiration to many” (Grimmett,

Dominic’s early work in probability included some graph theory, typically in the context of lattice graphs on which percolation was studied. He took up Hammersley’s interest in self-avoiding walks (paths starting at the origin) and statistical-mechanical models on these graphs, and remained interested in discrete probability throughout his career. His two research students who followed most closely in these footsteps were Geoffrey Grimmett (DPhil, 1974) and Peter Donnelly (DPhil, 1983), both of whom have since become Fellows of the Royal Society. But, throughout his career, there were many other points of contact with his early interest in probability. These included a 96-page survey (1970), a textbook with Grimmett (1986; 2nd edn. 2006), papers on generalisations of percolation (with Oxley, 1979), randomised algorithms (from the 1980s) including Markov Chain Monte Carlo methods (from the 1990s), and especially in his work on the Tutte polynomial through its connections to statistical mechanics (via partition functions and the random-cluster model).

Dominic was first attracted to matroid theory by a seminar on the topic by C.St.J.A. Nash-Williams in 1966. It was only ten years later that his classic book

The most obvious signs of this activity were Dominic’s publications on matroids. In an early paper, he generalised to binary matroids the classical duality between Eulerian and bipartite planar graphs (1969). He proved new lower bounds on the number of non-isomorphic matroids (1969, and with Piff in 1971). Dominic attributed the rapid growth of interest in matroids from the mid-1960s to the discovery of transversal matroids and he made important contributions to that topic. One of the most significant of these was a generalisation, using submodular functions, of theorems on transversals by Hall, Rado, Perfect and Ore. He also pinned down the essential role played by submodularity in that theorem (1971). He introduced matroids based on generalised transversals (1969) and showed that every binary transversal matroid is graphic (with de Sousa, 1972).

Like the eminent Bill Tutte before him, when Dominic worked with matroids, he was heavily influenced by what had earlier been proved for graphs. The stated purpose of his paper “Matroids versus graphs” (with Harary, 1969) was to help graph theorists “to appreciate the important link between graph theory and matroids”. This marks the beginning of Dominic’s use of survey papers to both develop a field and to build connections to other areas of mathematics.

In July 1969 Dominic ran an influential combinatorics conference at Oxford that is now recognised as the first British Combinatorial Conference (BCC). So, only three years after first meeting matroids, he was bringing combinatorics researchers together to advance the field. In 1972, Dominic organised another combinatorics meeting in Oxford; it is now viewed as the 3rd BCC.

Dominic edited the proceedings of the 1969 Oxford conference. It contains his paper “Combinatorial problems in matroid theory”. This provides a fascinating window into the state of discrete mathematics in the late 1960s, and clearly shows Dominic’s taste for attractive and challenging conjectures, as well as his long-lasting influence on mathematical research. Several of the problems he proposed have been resolved, while many are still open. Some have developed into important areas of research. Dominic lists four problems concerning the enumeration of matroids, two of which have been settled. The asymptotic behaviour of the number of binary matroids has been established by Wild (2005). Crapo and Schmitt (2005) and, independently, Lemos (2004) solved another problem by showing that the number of non-isomorphic matroids on m+n elements is at least the product of the numbers of non-isomorphic matroids on m and on n elements. Other problems in enumeration remain open and seem very difficult, despite significant advances by Rudi Pendavingh, Jorn van der Pol, Remco van der Hofstad, and Nikhil Bansal.

The climax of Dominic’s first ten years in matroid theory was the publication of his book,

Given the way Dominic’s interests developed later, it is worth noting his book’s importance in promoting the Whitney rank generating function and the Tutte polynomial in Chapter 15. This chapter was one of the earliest surveys of that topic, along with the treatment in Norman Biggs’s book

When Dominic was approached by Oxford University Press in the late 1980s about updating his book, he declined and recommended James Oxley to the OUP editor. Oxley’s book was published in 1992 (2nd edn. 2011). Dominic’s book was reprinted, with some corrections, by Dover in 2010 and continues to be a valuable resource. Dominic’s generosity of spirit led to him expressing concern that the Dover reprint of his 1976 book would hurt sales of Oxley’s book.

Two of Dominic’s enumerative problems concerning unimodal sequences lie at the heart of a new and rapidly expanding effort to use techniques from algebraic geometry in discrete mathematics. A unimodal sequence can have only one local maximum (which might be a single peak or a plateau). In his 1969 Oxford conference paper, Dominic looked at two sequences of numbers that can be derived from any matroid, namely the number of flats of rank r and the number of independent sets of size r, where r ranges from 0 to the rank of the matroid. Harper and Rota had conjectured that the first sequence is unimodal; this remains open. Dominic conjectured that the same is true for the second sequence.

The characteristic polynomial of a matroid is a natural generalisation of the chromatic polynomial of a graph. Brylawski and, independently, Lenz showed that the coefficients of the characteristic polynomial of a matroid can be related to the sequence of numbers of independent sets of some matroid. In Chapter 15 of Dominic’s book, he conjectured that the absolute values of these coefficients are log-concave, thereby strengthening earlier unimodal conjectures of Rota and of Heron. (Andrew Heron’s 1972 DPhil was supervised by Dominic.) In a tour de force of convex geometry and commutative algebra, Adiprasito, Huh, and Katz (2018) proved Dominic’s log-concavity conjecture. Indeed, the proof of the Heron-Rota-Welsh Conjecture is prominently noted in the citation for June Huh’s 2022 Fields Medal.

A major part of Dominic’s influence was through his supervision of research students. His first doctoral student was Adrian Bondy (DPhil, 1969) with whom he wrote a paper on transversal matroids and who became a leading graph theorist. Dominic recalled with self-effacing mirth that one of the first problems he gave Bondy was nothing less than the famous, notoriously difficult and still-open Reconstruction Conjecture! After Bondy, then Andrew Heron, came DPhils by Michael Piff (1972), Joan de Sousa, Geoffrey Grimmett (both 1974), Colin McDiarmid, Frank Dunstan (both 1975), Lawrence Matthews (1977), James Oxley (1978), and Paul Walton (1982), all in matroid theory except for Grimmett. Many of these students ranged over a variety of topics within the field. Heron’s paper on matroid polynomials in the 3rd BCC (1972) included his celebrated unimodal conjecture. This paper seems to have been the first appearance of matroid polynomials in the work of one of Dominic’s students. McDiarmid made many contributions over his time as a student, with emphasis on transversal matroids, their duals, and links with Menger’s Theorem; some ten of his papers are cited in Dominic’s book. Two of Dominic’s papers with Oxley (1979) were his first focusing on the Tutte polynomial and linked it to his early interest in percolation. Results in the first of these papers included a type of `Recipe Theorem’ that generalised a theorem of Brylawski and gave conditions under which an invariant is essentially an evaluation of a Tutte polynomial. The second paper contained a characterisation of Tutte invariants at the very general level of arbitrary clutters (Sperner systems) using a generalisation of percolation probability.

Dominic also developed a close collaboration with Paul Seymour whose DPhil (1975) at Oxford was supervised by the prominent matroid theorist Aubrey Ingleton. Some of the work with Seymour established new links, in both directions, between Dominic’s interests in probability and combinatorics: using the Fortuin-Kasteleyn-Ginibre (FKG) inequality from statistical mechanics to prove new results in combinatorics (1975), and using insights on planar-graph duality to shed light on the critical probability for bond percolation on the square lattice (1978). This latter work was built on in Kesten’s celebrated determination of that critical probability (1980).

Dominic continued to work in matroid theory throughout his career. But he was a voracious learner who was always searching for new challenges and for ways to tie together areas that may have initially seemed disparate.

Around the early 1980s, the emphasis of Dominic’s research and supervision shifted from matroid theory to computational complexity. While this may seem like a big change, his interest in computation went back a long way. During a spell at Bell Labs in around 1961 (part of one of Hammersley’s visits there), he did some programming using punched cards as was normal in that era. Later, while doing his doctorate at Oxford and working on the spread of infection through a two-dimensional lattice graph, he supplemented some of his theoretical results with computational experiments using Monte Carlo methods on an Elliott 803 computer (a type that was then common in British universities and was often programmed using Algol). He discussed the link between the percolation problems he worked on and critical-path problems for Program Evaluation and Review Technique (PERT) networks, an important topic in project management and operations research, and wrote two short Letters to the Editor in the journal

His DPhil students on computational complexity in the early to mid-1980s were Tony Mansfield (1982), Ken Regan (1986), Graham Farr (1986) and Keith Edwards (1986). Tony Mansfield proved that determining the thickness of a graph is NP-hard, solving a significant open problem in NP-completeness. Keith Edwards gave an impressive set of algorithms and hardness results for some fundamental existence and enumeration problems for colouring graphs of bounded genus or minimum density. As these examples illustrate, most of Dominic’s students in that era worked on specific graph-theoretic problems and classified their complexity (P versus NP-complete/hard etc). Ken Regan was the exception; he took the much more difficult path of proving new results about the complexity classes themselves and delving into the P-versus-NP problem. He remains active in that field and writes about it with Dick Lipton in their blog,

Dominic’s interest in computational complexity led naturally to an interest in cryptography, where complexity issues had come to the fore after the birth of public-key cryptography in the 1970s. This led to a textbook,

Dominic retained his earlier interests, supervising Peter Donnelly (1983) on discrete probability models on graphs and Manoel Lemos (1988) on matroid theory. His work with Donnelly on antivoter models — in which the vertices of a graph are each given a colour Black or White, with the colour on a vertex randomly chosen to be biased away from whichever colour is more frequent on neighbouring vertices — inspired a randomised 3-colouring algorithm which he studied with astrophysicist David Petford (1989). Some of Keith Edwards’s work also harked back to Dominic’s early interest in self-avoiding walks on square-lattice graphs.

This was an exceptionally busy period for Dominic, as he served variously as Chairman of the Board of the Faculty of Mathematics, Sub-Warden of Merton College and Chairman of the British Combinatorial Committee, holding all three roles simultaneously for a time. Somehow he also found the time to write two of his previously mentioned books.

In the late 1980s, Dominic combined his interests in matroid theory and complexity to investigate the complexity of evaluating the Tutte polynomial at specific points. Work with Dirk Vertigan (DPhil, 1991) and François Jaeger resulted in a complete classification of points $(x,y)$ according to whether computation of $T(G;x,y)$ was polynomial time or #P-hard (a stronger form of NP-hardness for counting problems). This paper was published in 1990 and yielded new complexity results for some other combinatorial polynomials that can be obtained from the Tutte polynomial by algebraic substitutions, including the Jones polynomial from knot theory and the partition functions of the Ising and Potts models from statistical physics.

This work opened up a rich new vein of research in which complexity results were proved for various properties (including evaluations and coefficients) of various polynomials for various classes of graphs and matroids. Some of these results pertained to exact computation of the polynomials, others to approximating or bounding them. The main tool for approximation was a type of efficient randomised algorithm — a fully polynomial randomised approximation scheme (FPRAS) — and the main approach was to develop a Markov Chain Monte Carlo (MCMC) algorithm, which uses a Markov chain among the structures of interest to sample from them and hence estimate their numbers. A key technical challenge is to ensure that the Markov chain converges quickly enough (is “rapidly mixing”), and issues of this type led Dominic to some significant combinatorial problems and conjectures.

He wrote a book,

This stream of research also includes the MSc of Laura Chávez Lomelí (1994) and the DPhils of James Annan (1994), Steve Noble (1997), Eric Bartels (1997) and Magnus Bordewich (2003). Annan proved that computing any specific coefficient of the Tutte polynomial is #P-complete and gave, for dense graphs, an FPRAS for the value of the Tutte polynomial at $(x,1)$ where $x \geq 1$, which includes counting forests $(x=2)$. Dominic later collaborated with Alon and Frieze to extend this result to evaluations at any $(x,y)$ with $x,y \geq 1$ (1995). Whether a randomised approximation of this type can be found for all graphs remains an open question, though Bordewich was able to find such approximations for certain types of sparse graphs. Noble proved that the Tutte polynomial can be evaluated in polynomial time for graphs of bounded tree-width, and provided a Jaeger-Vertigan-Welsh-style complexity classification for evaluations of an analogue of the Tutte polynomial for 2-polymatroids introduced by Oxley and Whittle. Dominic collaborated with Bordewich, Freedman and Lovász on an important paper (2005) showing that an additive approximation (which is weaker than an FPRAS) to a certain Tutte polynomial evaluation (related to the Jones polynomial) is sufficient to capture the power of quantum computation, extending earlier work of Freedman, Kitaev, Larson and Wang (2002).

Dominic used MCMC algorithms in some other novel ways. He developed a Markov chain method for choosing a planar graph uniformly at random amongst those with a fixed vertex set of size n (with Denise and Vasconcellos, 1996). He later used this idea with McDiarmid and Steger (2005) and discovered the surprising fact that the probability of the random planar graph being connected tends to neither 0 nor 1 as n tends to infinity.

Dominic also explored some purely combinatorial properties of Tutte-Whitney polynomials and found interesting generalisations, evaluations and relationships. For example, he proved that the expected values of Tutte polynomial evaluations for a random subgraph of a graph are themselves evaluations of the Tutte polynomial of the given graph (1996). He took a particular interest in the way the polynomials linked different fields of mathematics: combinatorics, statistical physics, network reliability, coding theory and knot theory, and wrote often on these links. He fostered connections with researchers in these diverse fields.

In a 1995 paper, Dominic and his then-student Eric Bartels defined the mean colour number of an n-vertex graph to be the expected number of colours actually used in a random proper n-colouring of the graph, and conjectured that it achieves its minimum when the graph is empty. Dominic called this the Shameful Conjecture because so many researchers had tried but failed to prove it in spite of it seeming so obvious. It finally succumbed to Fengming Dong (2000). For an account of its history, see a post by Gordon Royle here. The Bartels-Welsh paper also proposed a stronger conjecture, that the mean colour number never decreases when an edge is added to a graph, but this was disproved by Michele Mosca (1998) who later completed a DPhil (1999) in quantum computing under the joint supervision of Dominic and his colleague Artur Ekert. These conjectures have the character of correlation inequalities and share their combination of plausibility and difficulty. They were not the last correlation inequalities to be conjectured by Dominic and acquire fame (or notoriety!).

His work on other aspects of the Tutte polynomial included supervision of the DPhils of Criel Merino (2000), Koko Kayibi (2002) and Andrew Goodall (2004). Merino linked certain evaluations of the Tutte polynomial to numbers of critical configurations in a chip-firing game on graphs. He also did a computational study of the asymptotic behaviour of the number of acyclic orientations in square-lattice graphs (another link to some of Dominic’s earliest interests), and this led him and Dominic to conjecture that the number of spanning trees of a graph is bounded above by whichever is larger of the number of acyclic orientations and the number of totally cyclic orientations. This too may be viewed as a correlation inequality. This conjecture is known as the Merino-Welsh Conjecture and remains open. It has proved to be very attractive and very difficult. Gordon Royle has posted a good introduction here. For general matroids, counterexamples have recently been given by Beke, Csáji, Csikvári and Pituks.

Dominic co-organised the first workshop on the Tutte polynomial, at Barcelona in 2001. It became the basis of a special issue of

He retained his early interest in the complexity of matroid computations in general, and his last DPhil student, Dillon Mayhew (2005), took up this theme, this time considering matroids to be represented (for input purposes) not by an oracle (as Robinson and Welsh had done) but by a complete list of all the sets required for one of the axiomatisations, that is, all independent sets, or all bases, or all circuits, and so on.

Research on other matroid topics continued through this fourth phase, including through his supervision of Irasema Sarmiento (DPhil, 1998) and (with Colin McDiarmid) Rhiannon Hall (2005). Once Dominic retired in 2005, he seemed to spend more time on matroid theory, for example in studying matroid enumeration and properties of random matroids with several collaborators in papers published in the period 2010-2013.

Dominic made lasting contributions to mathematics, especially to matroid theory and to Tutte-Whitney polynomials. His research style was characterised by a deep sense of mathematical beauty and astute judgement as to what problems or topics were worth pursuing. In framing theorems and writing about them, he was good at drawing out and highlighting what was really important. Dominic had a natural gift for linking disparate fields, a real sense of intellectual adventure, and a youthful readiness to move into new territory. He seemed impelled by a kind of level-headed urgency to make the most of opportunities and push our field forward.

Dominic’s influence goes well beyond what can be accounted for by his formal contributions to building the intellectual structure of mathematics — his definitions, theorems and proofs. He also advanced mathematics by his development of its people, community and culture. Not only was he eminently successful at

This is evident firstly in his writing, through his many survey papers and textbooks, and in fact many of his research articles contain valuable expositions of the state of particular research topics and their relationships with other fields. These played a significant and easily underestimated role in the development of the fields he worked in. His writings also show an interest in history, an awareness of emerging unpublished work, and liberal acknowledgements of the contributions of others.

A striking characteristic of Dominic’s expository power — in writing, presenting, and conversation — was his extraordinary ability to move rapidly from introducing an area to stating enticing research problems in that area. Mathematical depth was made accessible and shared. His diagrams of the Tutte plane and of the world of complexity theory were ubiquitous in his talks and they were memorable for the compact way they encapsulated so much information.

His advancement of the human side of mathematics was aided greatly by his character and social attributes. He had a remarkable ability to get on well with people, indeed his personality had a magnetic quality. He was equal to any social situation and always pleasant, considerate and courteous, often smiling or laughing. He was very hospitable and together with his wife Bridget he would welcome students and colleagues to the home he shared with her and their sons. He was a fine athlete and was fiercely competitive, challenging all comers variously in real tennis, table tennis, squash, croquet, boules and speed chess. All such contests had laughter associated with them, though sometimes this occurred long after the event.

Dominic was at once outgoing and sensitive, confident and careful, firm and gentle, purposeful and relaxed, serious and light-hearted, dignified and informal. These somewhat-contrasting qualities would often play out together as he talked. He was quick to find humour in situations and freely shared anecdotes and observations. Anyone interacting with him would be confident of his attention and goodwill. He built strong and enduring connections. These days, one might say that he was a central node in the social network of his field. He used that position generously in sharing news, ideas and problems. His informal interactions with other researchers were very influential and have helped shape the areas he worked in.

Dominic led a strong combinatorics group at the Mathematical Institute in Oxford, with colleagues Peter Cameron (who recently reflected on his influence on his blog), Aubrey Ingleton, Colin McDiarmid and their students. He was a popular and effective teacher of undergraduates. Under the Oxford tutorial system, he worked most closely with undergraduates at Merton College where he was a major contributor to his College’s very strong results in mathematics over many years. Undergraduates taught by Dominic at Merton included, chronologically, Andrew Wiles, Dugald Macpherson, Peter Kronheimer, and Dominic Joyce, who between them have gone on to win more than twenty major mathematical awards including the Abel Prize to Wiles.

He was very efficient and well organised, with a deep sense of duty. So it is not surprising that he took on leadership roles. He edited several journals, organised some pivotal conferences, led the British Combinatorial Committee, and held senior positions at Oxford, to the great benefit of all his academic communities. In 1985, as second chair of the British Combinatorial Committee, Dominic gave a memorable after-dinner address at a reception hosted by the Lord Provost of Glasgow at the Glasgow City Chambers. Dominic’s theme was the attraction of doing mathematics and, echoing G.H. Hardy, he said that, for him, the joy came from discovering beautiful patterns. All who are acquainted with Dominic’s work, even superficially, will recognise how this search for such discoveries permeates his research.

Dominic was a very effective supervisor of research students. This drew not only on his mathematical knowledge, taste, judgement and connections, but also on his personality, character and people skills. He was flexible in his approach and adept at finding a productive mix of patience, firmness, encouragement, plain speaking, and inspiration. He was generous in the freedom he gave his students while being as supportive as needed. Time and again he brought out the best in his diverse range of students, inspiring enduring appreciation and affection. An academic family tree for Dominic, listing his DPhil graduates (28 as main supervisor) and many of his academic descendants, is maintained by David Wood (Graham Farr’s first PhD graduate, 2000) here. This is much more comprehensive than the one at the Mathematics Genealogy Project. David also maintains the academic family tree of John Hammersley of which Dominic’s tree is the dominant subtree.

Dominic Welsh’s enduring legacy includes a significant and eclectic body of research, a rich library of influential expository writing, and a large and notable community of students, collaborators and colleagues. He will be remembered with admiration, affection and deep gratitude. He has greatly enriched discrete mathematics as both a research field and a human endeavour.

We are grateful for comments and suggestions from Peter Cameron, Keith Edwards, Colin McDiarmid, Steven Noble, Ken Regan, Charles Semple, Geoff Whittle and David Wood.

As has been mentioned on this blog before, an *idée fixe* of the late Henry Crapo was to naturally define a matroid $\delta M$ whose ground set is the collection $\mathcal{C}(M)$ of circuits (or the collection $\mathcal{C}(M^*)$ of cocircuits) of an underlying matroid $M$. Similar questions have also been asked by Gian-Carlo Rota. We will call such a construction a *derived matroid* of $M$, partly in analogy with the construction of *derived codes* in coding theory. Throughout this blogpost, $n$ will denote the size and $k$ will denote the rank of $M$.

The derived matroid could be seen as a combinatorialization of the notion of syzygies and resolutions in commutative algebra, regarding circuits as combinatorial “relations”, which generate a space in which we can again study “relations”, and so on. From this viewpoint, it is natural to try to define a matroid structure on the set of circuits. On the other hand, it seems like a desirable feature that the nullity of $M$ would give, or at least bound, the number of “independent” circuits (*i.e.* relations) in $M$, or in other words that the number of independent *cocircuits* would equal (or be bounded by) the nullity of $M^*$, which is the rank of $M$. In this light studying the sequence of repeated derivations of a matroids $M$ would be more natural if $\delta M$ had as its ground set the cocircuits of $M$. Since the cocircuits are in natural bijection with the hyperplanes of $M$, a derived matroid with ground set $\mathcal{C}(M^*)$ would model the hyperplane arrangement described by the point set in the representable case. There are thus good arguments both in favour of grounding the derived matroid on $\mathcal{C}(M)$ and on $\mathcal{C}(M^*)$. In our paper, we choose the first alternative, but the last word has hardly been said in this debate, and of course, one definition can be obtained from the other by dualizing.

Let us first consider the case for represented matroids, and let $G$ be a $k\times n$ matrix of full rank representing $M$ over a field $\mathbb{F}$. Then, every circuit $C\in\mathcal{C}(M)$ is the inclusion-minimal support of a vector $q_C\in\mathbb{F}^n$ such that $G q_C=\mathbf{0}$, and this vector is unique up to scalar multiple. The collection of vectors $\{q_C\}_{C\in\mathcal{C}(M)}$ represent some matroid with ground set $\mathcal{C}(M)$, and we will denote this matroid by $\delta_{OW}(G)$, where the subscript refers to the authors Oxley and Wang, who studied this construction [OW19].

It is not difficult to see that $\delta_{OW}(G)$ has rank $n-k$, because the circuit vectors together generate the null space of the matrix $G$. While this is certainly a desirable feature, it is an unfortunate fact that the construction $\delta_{OW}$ depends on $G$ rather than only on $M$. The geometrically easiest illustration of this feature may be when $M$ is the uniform matroid $U_{3,6}$, represented by a configuration $P$ of six points in general position in the projective plane. Then, the hyperplane arrangement of the $\binom{6}{2}=15$ lines (through pairs of $P$) can be of two different kinds, as shown in the picture below (not all lines are drawn):

Indeed, in addition the five lines intersecting in each point of $P$, it will *generically* be the case that all other intersections of lines are distinct. However, it is also possible that three of the lines, that do not share a point in $P$, might meet in a point in the projective plane. In this latter case, the cocircuits corresponding to the three lines will be “dependent”; in the former case they will be “independent” in $\delta_{OW}(Q^*)$.

It is fair to say that the dependence between the three lines in the previous example is “accidental”, in that it is not forced by the matroid structure of $U_{3,6}$ itself. If we are to define “the” derived matroid of the matroid $U_{3,6}$ combinatorially, we in particular want the complements of these lines to be independent. Following this line of thought, we consider independence to be the generic state of things, while dependence is forced by constraints coming from the underlying matroid. Our construction of $\delta M$ is thus twofold. First we identify which collections of circuits “have to” be dependent in any “reasonably defined” derived matroid of $M$. After this, we add just enough other dependent sets, to guarantee that $\delta M$ is indeed a matroid, and we do it in such a way as to not introduce unnecessary dependent sets, and in particular not in low rank.

Let us illustrate this procedure with the infamously non-representable Vámos matroid $M$. All sets of three or fewer elements are independent and among the sets of four elements only the five depicted as grey rectangles in the figure are circuits. All sets of five or more elements are dependent.

The ground set of the derived matroid $\delta M$ has 41 elements, the circuits of $M$. If we consider the three planes $abcd$, $adef$ and $bcef$, we intuitively want this to be a dependent set in $\delta M$, because it “looks like” these planes make a “circuit”. To make this mathematically more precise, we can say that this set of circuits is dependent because its size (3) is larger than the nullity in $M$ of the union of all its elements (these six elements have nullity 2 in $M$). That is to say, we want that a set of circuits is dependent in $M$ if it belongs to the family

$$\mathcal{A}_0:=\{A\subseteq\mathcal{C}:|A|>n(\cup_{C\in A}C)\}.$$

It is readily checked that in the previous example of $U_{6,3}$, the three discussed lines are not in this family, because $3\not>3$.

The above family $\mathcal{A}_0$ gives us a precise description of which collections of circuits “have to” be dependent in $\delta M$. Note that this is a combinatorial description: it does not depend on a representation of the matroid. What we want to do now, is make sure that we find all dependent sets of the derived matroid. To see how to get to this, consider the axioms for the collection $\mathcal{D}$ of dependent sets of a matroid.

- $\emptyset\notin\mathcal{D}$;
- if $D\in\mathcal{D}$ and $D\subseteq D’$ then $D’\in\mathcal{D}$;
- if $D_1,D_2\in\mathcal{D}$ and $D_1\cap D_2\notin\mathcal{D}$, then $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.

Our collection $\mathcal{A}_0$ satisfies the first two axioms, but in general, it does not satisfy the third. So we want to add extra elements in order to get a collection that does satisfy (D3). There are two ways to do this, as we see from a logical rewriting of the axiom:

- If $D_1, D_2\in\mathcal{D}$, then $D_1\cap D_2\in\mathcal{D}$ or $(D_1\cup D_2)\setminus\{e\}\in\mathcal{D}$ for all $e\in D_1\cap D_2$.

This means that for any $A_1,A_2\in\mathcal{A}_0$, we can either decide that $A_1\cap A_2$ is dependent, or that $(A_1\cup A_2)\setminus{C}$ is dependent for all $C\in A_1\cap A_2$ (or both). If we decide on the first, we will get a lot of small dependent sets, and often this leads to a derived matroid of rank 0. We therefore decide to define the following operations.

**Definition.** Let $\mathcal{C}$ be the set of circuits of some matroid, and let $\mathcal{A}\subseteq \mathcal{C}$. Then we define the collections

$$\epsilon(\mathcal{A})=\mathcal{A}\cup\left\{(A_1 \cup A_2) \setminus {C} : A_1, A_2\in \mathcal{A}, A_1\cap A_2\not\in\mathcal{A}, C\in A_1\cap A_2\right\}$$ and $${\uparrow}\mathcal{A}=\{A\subseteq \mathcal{C}: \exists A’\in\mathcal{A}: A’\subseteq A\}.$$

Observe that, by definition, $\mathcal{A}\subseteq {{\uparrow} \mathcal{A}}$ and $\mathcal{A}\subseteq \epsilon(\mathcal{A})$ for every $\mathcal{A}\subseteq2^\mathcal{C}$. The operations ${\uparrow}$ and $\epsilon$ are designed to guarantee properties (D2) and (D3) in the matroid axioms.

**Definition.** Let $M$ be a matroid, and $\mathcal{C}=\mathcal{C}(M)$ its collection of circuits. Define the collection

$$ \mathcal{A}_0:=\{A \subseteq \mathcal{C}: |A|> n(\cup_{C\in A} C)\}. $$

Inductively, we let $\mathcal{A}_{i+1}={\uparrow}\epsilon(\mathcal{A}_i)$ for $i\geq 1$, and

$$\mathcal{A}=\bigcup_{i\geq 0} \mathcal{A}_i.$$

Note that the sequence $\mathcal{A}_i$ is both increasing and contained in the finite set $2^\mathcal{C}$. Hence, we have that $\mathcal{A}_0\subseteq\mathcal{A}$ and $\mathcal{A}=\mathcal{A}_n$ for some $n\geq 0$.

**Definition (combinatorial derived matroid).** Let $M$ be a matroid with circuits $\mathcal{C}$. Then the *combinatorial derived matroid* $\delta M$ is a matroid with ground set $\mathcal{C}(M)$ and dependent sets $\mathcal{A}$.

By carefully checking the dependent axioms, we can prove that this definition gives indeed a matroid. In fact, we can prove two more ways to construct this derived matroid, by means of its circuits: we refer the interested reader to the full paper [FJK23].

**Theorem.** For any matroid $M=(E,\mathcal{C})$ the collection $\mathcal{A}$ is the collection of dependent sets of some matroid with ground set $\mathcal{C}$.

This is good news! We now have a definition of a derived matroid that is purely combinatorial: it does not depend on a representation, and hence it exists for any matroid. As far as we know, this is the first definition of this kind. We also managed to show that there is more good news: this definition behaves well with connectedness. That is, the derived matroid of a direct sum is the direct sum of the derived matroids of the connected components.

Unfortunately, it is not all good news. It is not difficult to show that the rank of $\delta M$ is bounded by $n-k$, as desired, but equality does not always hold. Computer calculations by Knutsen [Knu23] show that the rank of the derived Vámos matroid is 3, and not 4. However, this news is not as bad as it sounds, since the Vámos matroid was shown to not have an adjoint by Cheung [Che74]. The construction of the adjoint of a matroid is, in some sense, the dual of that of the derived matroid: it has the set of cocircuits of $M$ as its ground set.

Many questions are still open regarding this construction of $\delta M$. Most prominently: how does this construction relate to earlier constructions of the derived matroid? In particularly, that of Oxley and Wang, but also to the adjoint of a matroid. For more questions, we refer to the full paper [FJK23]. We hope this post inspired you to think more about derived matroids!

[Che74] Cheung, A.L.C. (1974). *Adjoints of a geometry.* Canadian Mathematical Bulletin, 17(3), 363-365.

[FJK23] Freij-Hollanti, R. & Jurrius, R.P.M.J. & Kuznetsova, O. (2023). *Combinatorial Derived Matroids.* Electronic Journal of Combinatorics, 30(2), P2.8.

[Knu23] Knutsen, T.D. (2023). *Codes, matroids and derived matroids.* Master thesis, UiT Arctic University of Norway.

[OW19] Oxley, J & Wang, S. (2019). *Dependencies among dependencies in matroids.* Electronic Journal of Combinatorics, 26(3), P3.46.

Please advertise this talk at your home institution. Anyone is welcome to attend!

**Time:** Wednesday, Jan 24 at 3pm ET**Zoom: **https://gatech.zoom.us/j/8802082683

**Speaker:** James Davies, University of Cambridge**Title:** Odd distances in colourings of the plane

**Abstract:** We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integer distance from each other. The proof uses a spectral method.

Decomposition of objects into smaller or simpler objects is a central theme in combinatorics. Think about decomposing a graph into its connected components or blocks, or into forests. In today’s post, I discuss decomposing finite projective geometries into projective geometries of smaller rank.

**Definition:** Let $q$ be prime power, let $n \ge t \ge 1$ be integers and let $M = \text{PG}(n-1,q)$ be the projective geometry over the field with $q$ elements. A $t$-spread of $G$ is a collection of rank-$t$ flats of $M$ that partition the points of $M$—that is, these flats are pairwise disjoint and their union is the set of all points of $M$.

(Geometers often use dimension instead of rank; the dimension of a projective geometry is one less than its rank. Their $t$-spreads are collections of $t$-dimensional subspaces of an $n$-dimensional space. We will however stick to the terminology that is more familiar in the matroid theory setting.)

Every projective geometry has a 1-spread: the flats making up the spread are simply the points of the geometry. It is much more interesting to look into the existence of $t$-spreads when $t \ge 2$.

The Fano plane $F_7 = \text{PG}(2,2)$ does not admit a decomposition into triangles. The quickest argument to see this is based on counting the number of points: any matroid that can be decomposed into triangles necessarily has a number of points that is a multiple of 3, but the Fano plane has seven points. By contrast, the projective geometry $\text{PG}(3,2)$, which has fifteen points, can be partitioned into five triangles (as encoded using different colours in the following representation:

The counting argument above can be generalised. In order for $M = \text{PG}(n-1,q)$ to have any hope of admitting a $t$-spread, the number of points in a projective geometry of rank $t$ should evenly divide the number of points in $M$, or $\frac{q^t-1}{q-1} \bigg| \frac{q^n-1}{q-1}$. It is a nice exercise to show that the latter happens precisely when $n$ is a multiple of $t$. So, if $\text{PG}(n-1,q)$ can be decomposed into rank-$t$ subgeometries, we must have $t|n$.

It turns out that this divisibility criterion is not only necessary—it is sufficient as well. We end this blog post with a slick proof of this fact. The proof can be found in many introductory texts on projective geometry.

**Theorem:** The projective geometry $M=\text{PG}(n-1,q)$ admits a $t$-spread if and only if $t|n$.

*Proof:* We already proved the implication from left to right. The implication in the other direction follows from a construction.

Suppose that $n = kt$ for some integer $k$. The points of $M$ can be identified with the 1-dimensional subspaces of the vector space $\mathbb{F}_q^n$. We will show that $\mathbb{F}_q^n$ can be decomposed into $t$-dimensional subpspaces that are pairwise disjoint (except that they all contain the zero-vector). As the 1-dimensional subspaces of $\mathbb{F}_q^t$ can be identified with the points of a $\text{PG}(t-1,q)$, this immediately implies the theorem.

Consider the $k$-dimensional $\mathbb{F}_{q^t}$-vector space $\mathbb{F}_{q^t}^k$. Its 1-dimensional subspaces intersect only in the zero-vector. These 1-dimensional subspaces give us our spread, as each such subspace can alternatively be viewed as a $t$-dimensional $\mathbb{F}_q$-vector space. $\Box$

]]>The obvious thing to try is to just define representability of infinite matroids the same way we define it for finite matroids: take a set $E$ of vectors in some vector space $V$ over $k$, and say that a subset of $E$ is independent if it is linearly independent in $V$. If $E$ is infinite then we have an infinite matroid, and such matroids should certainly count as representable over $k$.

Unfortunately this definition doesn’t cover all the examples of matroids which ought to be representable. For example, in this post we saw a bunch of examples that look like infinite graphic matroids, and graphic matroids should be representable over every field. But these examples are not covered by the definition above. Nor are the examples from this post. Why not? A set of vectors is linearly independent as soon as all of its finite subsets are, so all the circuits of these matroids will necessarily be finite. In other words, all these matroids are *finitary*.

This might remind of you of the issues which got this whole series of posts started, here and here. It is easy to find axioms for the collection of finitary infinite matroids, but that doesn’t include all the examples of things that look like infinite matroids, and in particular the collection of finitary matroids is not closed under duality. Finding natural axioms for a class of infinite matroids closed under duality was a much trickier problem. Now we are running into exactly the same problem with representability. Not only have we failed to cover the important examples, this definition of representability is not even closed under duality.

Still, we have made some progress. We have identified which finitary matroids should count as representable over $k$, and so whatever our definition turns out to be it should give this collection of matroids as the finitary representable matroids. Since cofinitary matroids are just the duals of finitary matroids, we have also identified which cofinitary matroids should count as representable over $k$, namely the duals of these finitary representable matroids. Taking the union of these two classes would give a class of matroids closed under duality, but this is pretty crude and still doesn’t cover some of the interesting examples.

We need a way to allow infinite linear combinations of our vectors. One natural idea, which quickly turns out to be a dead end, is to use the infinite sums defined in Hilbert spaces (the notion of independence given this way does not give rise to a matroid). A more fertile approach was found by Bruhn and Georgakopoulos [4]. You can understand the basic idea by considering the following list of vectors in $\mathbb{R}^{\mathbb{N}}$:

$$\begin{array}{rrrrrrrrr}(&1,&0,&0,&0,&0,&0,&\ldots&)\\(&-1,&1,&0,&0,&0,&0,&\ldots&)\\(&0,&-1,&1,&0,&0,&0,&\ldots&)\\(&0,&0,&-1,&1,&0,&0,&\ldots&)\\(&0,&0,&0,&-1,&1,&0,&\ldots&)\\&&&\vdots&&&&&\end{array}$$

Although this list is infinite, if we pick any particular column and take the sum of the entries in that column it evaluates to 0. So there is a sense in which this infinite list of vectors sums to 0. More precisely, given a set $I$, we can consider the vector space $k^I$ of functions from $I$ to $k$. Then we say that a set $U$ of vectors in $k^I$ is *thinly dependent* if we can find coefficients $\lambda_u \in k$ for each $u \in U$, not all zero, such that for any $i \in I$ we have $$\sum_{u \in U} \lambda_u u(i) = 0\,.$$ There is of course the problem that some of these sums might not be defined, in that they might have infinitely many nonzero summands. We say that $U$ is *thin* if such sums are necessarily well-defined, that is, if for each $i \in I$ there are only finitely many $u \in U$ with $u(i) \neq 0$.

This suggests a new idea for how to define representable matroids. We take the ground set $E$ to be a thin set of vectors in $k^I$, and as dependent sets we take the thinly dependent subsets of $E$. The matroids we get this way need not be finitary, but now we have some new problems. A typical set of vectors in $k^I$ will not be thin, so it isn’t clear that all of the finitary representable matroids we saw above can be presented in this way. And in fact they cannot! Together with Afzali, I showed in [1] that all such matroids are cofinitary, and in fact they are exactly the duals of the finitary representable matroids.

So now we understand representability for finitary and for cofinitary matroids. To make any more progress we need to find a way to squeeze more juice out of the idea of thin dependency. The reason we took $E$ to be a thin family above was to ensure that thin dependency would always be defined for subsets of $E$, but we could drop that requirement if we take more care in our notion of dependency. More precisely, we take as our ground set $E$ any set of vectors in $k^I$, and we say that a subset $X$ of $E$ is dependent if it has a subset $Y$ which is thinly dependent (here $Y$ must be thin, even if $X$ need not be). Matroids arising in this way are called *thin sums matroids*.

This now includes all the cofinitary representable matroids, and it also includes all the finitary representable matroids (that’s less obvious, but it was shown in [1]). What’s more, it includes all the examples of things we wanted to be representable matroids. But there are some new problems. The systems of dependent sets defined in this way are not always matroids [1]. Even if they are matroids, their duals are not always thin sums representable [2]. Closure under duality is one of the main things we should hope for from a definition of representability. It seems we have hit a dead end.

However, there is a way forward. All of the examples that we cared about, and wanted to cover with our definition of representable matroids, had the property that they were *tame*, meaning that any intersection of a circuit with a cocircuit is finite. On the other hand, the bad examples where duality breaks down are not tame, but *wild*. This distinction was already discussed in an earlier post of the series. So we should restrict our attention to tame matroids.

And there we have it: we say that a matroid is *representable* over $k$ if it is tame and is a thin sums matroid over $k$. Suddenly, magically, everything works. This class is closed under duality [1]. All of the motivating examples are covered. Even better, all the usual theory of representable matroids can be extended to infinite representable matroids. For example, the various standard characterisations of binary and ternary matroids still work in this setting, including the characterisations via excluded minors [3].

Indeed, there is a very general principle which allows the lifting of excluded minor characterisations from finite to infinite matroids. For any finite field $k$, a tame infinite matroid $M$ is representable over $k$ precisely when all of its finite minors are [3]. This principle allows us to lift all kinds of other statements easily from finite to infinite matroids. For example, an infinite matroid which is representable over both $GF(3)$ and $GF(5)$ is necessarily representable over $GF(p)$ for all primes $p$ (since all its finite minors are).

For those readers who have come across partial fields and tracts, that last statement might have got you wondering whether we can define representations of infinite matroids over those objects, in the spirit of this post. For example, what might it mean for an infinite matroid to be orientable? This is a thorny problem, which will have to wait for a future post.

Although we now have a good definition of representability, there is one open problem in this area that has been nagging at me for years. Binary matroids can be defined as tame matroids with no $U_{2,4}$-minor. But do we really need to impose the condition of tameness here? To put it another way, must every wild matroid have a $U_{2,4}$-minor? All the examples we know of do.

[1] S. Hadi Afzali Borujeni and Nathan Bowler, Thin sums matroids and duality, Advances in Mathematics, Volume 271, 2015, Pages 1-29.

[2] Nathan Bowler and Johannes Carmesin, Matroids with an infinite circuit–cocircuit intersection, Journal of Combinatorial Theory, Series B, Volume 107, 2014, Pages 78-91.

[3] Nathan Bowler and Johannes Carmesin, An excluded minors method for infinite matroids, Journal of Combinatorial Theory, Series B, Volume 128, 2018, Pages 104-113

[4] Henning Bruhn and Agelos Georgakopoulos, Bases and closures under infinite sums, Linear Algebra and its Applications, Volume 435, Issue 8, 2011, Pages 2007-2018.

URL: https://dimag.ibs.re.kr/hiring/

DIMAG is a research group that was established on December 1, 2018 at the Institute for Basic Science (IBS), led by Prof. Sang-il Oum. DIMAG is located at the headquarters of the Institute for Basic Science (IBS) in Daejeon, South Korea, a city of 1.5 million people.

Currently, DIMAG consists of researchers from various countries such as Korea, the USA, Germany, Canada, and Australia, and the work is done in English. DIMAG is co-located with the IBS Extremal Combinatorics and Probability Group (ECOPRO).

Successful candidates for research fellowship positions will be new or recent Ph.D.’s with outstanding research potential in all fields of **discrete mathematics** with emphasis on **structural graph theory**, **combinatorial optimization**, **matroid theory**, and **algorithms**.

These appointments are for about two years, and the starting salary is no less than KRW 59,000,000. The appointment is one-time renewable **up to 5 years in total** contingent upon the outstanding performance of the researcher. The expected appointment date is September 1, 2024, but it is negotiable within the same calendar year.

These are purely research positions and will have no teaching duties.

A complete application packet should include:

- AMS standard cover sheet (preferred) or cover letter (PDF format)
- Curriculum vitae including a publication list (PDF format)
- Research statement (PDF format)
- Application for the IBS & Consent to Collection and Use of Personal Information (PDF file)
- At least 3 recommendation letters

For full consideration, applicants should email items 1, 2, 3, and 4 and arrange their recommendation letters emailed to dimag@ibs.re.kr by December 3, 2023, Sunday. (Anywhere on Earth)

Recommendation letters forwarded by an applicant will not be considered.

DIMAG encourages applications from individuals of diverse backgrounds.

*For Korean citizens who have not yet completed their military duty: *전문연구요원 종사를 희망하는 경우에는 지원 의사와 병역 관계를 cover letter 및 이메일 등에 표시하여 제출 필요. 다만 현역입영대상자의 전문연구요원 신규 편입은 불가하며, 보충역 대상자 및 타 기관에서 전직해서 오는 경우에 한하여 지원 가능(반드시 타 기관에서 전직 요건이 충족되는 등 전직 요건이 충족 되어야만 함)

**YouTube recording: **https://www.youtube.com/watch?v=aOpvWW1lBH8

**Time:** Wednesday, Nov 15 at 3pm ET**Zoom: **https://gatech.zoom.us/j/8802082683

**Speaker: **Jim Geelen, University of Waterloo**Title:** Average plane-size

**Abstract:** In 1941, Eberhard Melchior proved that the average line-length of a simple rank-3 real-representable matroid is less than three. We discuss a long-overdue analogue of Melchior’s result that the average plane-size of a simple rank-4 real-representable matroid is bounded above by an absolute constant, unless the matroid is the direct-sum of two lines. This is joint work with Rutger Campbell and Matthew Kroeker.

A new diamond open access journal has recently launched called *Innovations in Graph Theory*. The journal has an excellent editorial board and will be completely free for both authors and readers.

*Innovations in Graph Theory* has informed us that matroid theory submissions are very welcome. All Matroid Union editors are strong proponents of open access publishing, and so we encourage our readers to consider sending their matroid theory papers to *Innovations in Graph Theory. *Other topics related to graph theory are also within the new journal’s scope. Please see the new journal website for more information about how the new journal will function. The first issue of the journal is expected to appear in 2024.

We also would like to point out some other open access journals that accept submissions in matroid theory. These include the Electronic Journal of Combinatorics, Discrete Mathematics & Theoretical Computer Science, Advances in Combinatorics, Combinatorial Theory, and Discrete Analysis. Please feel free to point out other matroid theory friendly journals that are open access in the comments.

]]>