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.

This post is co-authored by Ragnar Freij-Hollanti.

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.

1. $\emptyset\notin\mathcal{D}$;
2. if $D\in\mathcal{D}$ and $D\subseteq D’$ then $D’\in\mathcal{D}$;
3. 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:

3. 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!

References

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

Happy New Year from all of us at the Matroid Union!

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$