Introduction

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.

References

Anyone who has studied matroid theory has seen graphic and linear matroids, and probably has a decent intuition for how the concepts in matroid theory relate to graph theory and linear algebra. Algebraic matroids are far less popular and many fundamental questions about them remain unanswered. The goal of this blog post is to introduce algebraic matroids, and give the reader a sense of where the subtlety lies when trying to understand them.

The definition

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}$.

An example and a theorem

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}$.

Relationship with linear matroids

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.

The big open question

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.

Guest Post by

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, Percolation, Springer, 1989, p. vii), and the same can certainly be said of Dominic.

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).


Second phase: matroid theory

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 Matroid Theory was published. This period was one of intense activity and quickly established him as one of the worldwide leaders in the field.

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, Matroid Theory, by Academic Press in 1976. This quickly became the standard reference for the field. It covered a much wider set of topics, and reached a much wider audience, than previous books in the field. Gian-Carlo Rota described it as “beautifully written and exceptionally thorough” (Advances in Mathematics 47 (1983) 231). Its style is compact and concise, exemplifying his own direct advice to students who wrote too verbosely: “cut the chat!”, “if in doubt, cut it out!”. At the same time, it is accessible and inviting. Its influence has been enormous.

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 Algebraic Graph Theory (1974). These works helped to broaden the interest in polynomial invariants for graphs and matroids.

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.


Third phase: computational complexity

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 Operations Research (1965-1966) discussing computational aspects. In 1967, with Oxford colleague Martin Powell, he published an important sequential graph-colouring algorithm, giving an algorithmic refinement of Brooks’s Theorem. This is known as the Welsh-Powell algorithm and has been widely studied and implemented. In a paper at the 5th BCC in 1975, his serious interest in complexity is evident in discussing the Aanderaa-Rosenberg Conjecture (as it was then) about how much of a graph’s adjacency matrix needs to be read in order to determine if the graph has some hereditary property. With Gordon Robinson (MSc, 1979), he proved early results on the computational complexity of matroid properties in a framework where a matroid is specified by an oracle for one of five common axiomatisations, namely via independent sets, bases, circuits, rank or closure.

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, Gödel’s Lost Letter and P=NP.

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, Codes and Cryptography (OUP, 1988), and supervision of some Masters students including Arun P. Mani (2004) and Douglas Stebila (2004). Many years later, he would publish another textbook, with John Talbot: Complexity and Cryptography (Cambridge University Press, 2010). Dominic’s attraction to complexity theory and cryptography was in spite of his recognition of the inherent difficulty of both subjects.

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.


Fourth phase: Tutte-Whitney polynomials and their complexity

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, Complexity: Knots, Colourings and Counting (CUP, 1993), which for many years was the leading reference on Tutte polynomials, their complexity and their links with other areas, and is still widely used.

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 Advances in Applied Mathematics in 2004, which he co-edited. The workshop was a milestone in the building of a strong community of researchers on the topic.

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.


The complete mathematician

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 mathematics; he was a complete mathematician.

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.


Acknowledgements

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.