Hello everyone – MatroidUnion is back!

Rudi and Jorn wrote a nice post earlier this year about questions in asymptotic matroid theory, and beautiful new results they’ve obtained in this area. While reading one of their papers on this topic, I saw that they restated the conjecture that almost all matroids on $n$ elements are non-representable. This was first explicitly written down by Mayhew, Newman, Welsh and Whittle [1] but earlier alluded to by Brylawski and Kelly [2] (in fact, the latter authors claim that the problem is an ‘exercise in random matroids’ but give no clue how to complete it). Indeed I would argue that most of us would independently come up with the same conjecture after thinking about these questions for a few minutes; surely representable matroids are vanishingly rare among all matroids!

In any case, reading this conjecture reminded me that, like many ‘obvious’ statements in asymptotic matroid theory it was still open, and seemed somewhat hard to approach with existing techniques. I’m happy to say that this is no longer the case; as it happened, I discovered a short proof that I will now give in this post. The proof is also on the arXiv [3]; there, it is written with the bounds as tight as possible. Here, I will relax the calculations a little here to make the proof more accessible, as well as using more elementary bounds so the entire argument is self-contained. The theorem we prove is the following:

Theorem: For $n \ge 10$, the number of representable matroids with ground set $[n] = \{1,\dotsc,n\}$ is at most $2^{2n^3}$.

The number of matroids on $n$ elements is well-known to be doubly exponential in $n$, so the above gives the ‘almost all’ statement we need, in fact confirming the intuition that representable matroids are extremely rare among matroids in general. The bound in the proof can in fact be improved to something of the form $2^{n^3(1/4 + o(1))}$, and I believe the true count has this form; see [3] for more of a discussion.

Our path to the proof is indirect; we proceed by considering a more general question on `zero-patterns’ of polynomials, in the vein of [4]. Let $f_1, \dotsc, f_N$ be integer polynomials in variables $x_1, \dotsc, x_m$. Write $\|f\|$ for the absolute value of the largest coefficient of a polynomial $f$, which we call its height; it is fairly easy to prove that $\|f + g\| \le \|f\| + \|g\|$ and that $\|fg\| \le \binom{\deg(f) + \deg(g)}{\deg(f)} \|f\|\ \|g\|$ for all $f$ and $g$. We will map these polynomials to various fields; for a field $\mathbb{K}$ and a polynomial $f$, write $f^{\mathbb{K}}$ for the polynomial in $\mathbb{K}[x_1, \dotsc, x_m]$ obtained by mapping each coefficient of $f$ to an element of $\mathbb{K}$ using the natural homomorphism $\phi\colon \mathbb{Z} \to \mathbb{K}$.

Given a field $\mathbb{K}$ and some $u_1, \dotsc, u_m \in \mathbb{K}$, the polynomials $f_i^{\mathbb{K}}(u_1, \dotsc, u_m)$ all take values in $\mathbb{K}$, and in general some will be zero and some nonzero in $\mathbb{K}$. We are interested in the number of different ways this can happen, where we allow both the field $\mathbb{K}$ and the $u_j$ to be chosen arbitrarily; to this end, we say a set $S \subseteq [N]$ is \realisable with respect to the polynomials $f_1, \dotsc, f_N$ if there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that \[S = \{i \in [N]: f^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}.\] In other words, $S$ is realisable if and only if, after mapping to some field and substituting some values into the arguments, $S$ is the support of the list $f_1, \dotsc, f_N$. We will get to the matroid application in a minute; for now, we prove a lemma that bounds the number of different realisable sets:

Lemma: Let $c,d$ be integers and let $f_1, \dotsc, f_N$ be integer polynomials in $x_1, \dotsc, x_m$ with $\deg(f_i) \le d$ and $\|f_i\| \le c$ for all $i$. If an integer $k$ satisfies
\[ 2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}}, \] then there are at most $k$ realisable sets for $(f_1, \dotsc, f_N)$.

Proof: If not, then there are distinct realisable sets $S_1, \dotsc, S_k \subseteq [N]$. For each $i \in [k]$, define a polynomial $g_i$ by $g_i(x_1, \dotsc, x_m) = \prod_{j \in S_i}f_j(x)$. Clearly $\deg(g_i) \le Nd$, and since each $g_i$ is the product of at most $N$ different $f_i$, we use our upper bound on the product of heights to get
\[ \|g_i\| \le c^N \binom{dN}{d}^N (2kc’)^D\], so we have a collision – there exist distinct sets $I,I’ \subseteq [k]$ such that $g_I = g_I’$. By removing common elements we can assume that $I$ and $I’$ are disjoint.

Let $\ell \in I \cup I’$ be chosen so that $|S_{\ell}|$ is as small as possible. We can assume that $\ell \in I$. Since the set $S_{\ell}$ is realisable, there is a field $\mathbb{K}$ and there are values $u_1, \dotsc, u_m \in \mathbb{K}$ such that $S_{\ell} = \{i \in [N]: f_{\ell}^{\mathbb{K}}(u_1, \dotsc, u_m) \ne 0_{\mathbb{K}}\}$. So $g^{\mathbb{K}}_{\ell}$, by its definition, is the product of nonzero elements of $\mathbb{K}$, so is nonzero. For each $t \in I \cup I’ – \{\ell\}$, on the other hand, since $|S_t| \ge |S_\ell|$ and $S_t \ne S_\ell$ there is some $j \in S_t – S_\ell$, which implies that the zero term $f^{\mathbb{K}}_j(u_1, \dotsc, u_m)$ shows up in the product $g^{\mathbb{K}}_t(u_1, \dotsc, u_m)$. It follows from these two observations that
\[ 0_{\mathbb{K}} \ne g^{\mathbb{K}}_I(u_1, \dotsc, u_m) = g^{\mathbb{K}}_{I’}(u_1, \dotsc, u_m) = 0_{\mathbb{K}}, \] which is a contradiction.

Why is this relevant to representable matroids? Because representing a rank-$r$ matroid $M$ with ground set $[n]$ is equivalent to finding an $r \times n$ matrix $[x_{i,j}]$ over some field, for which the $r \times r$ determinants corresponding to bases of $M$ are nonzero and the other determinants are zero. In other words, a matroid $M$ is representable if and only if the set $\mathcal{B}$ of bases of $M$ is realisable with respect to the polynomials $(f_A \colon A \in \binom{[n]}{r})$, where $f_A$ is the integer polynomial in the $rn$ variables $[x_{ij} \colon i \in [r],j \in [n]]$ that is the determinant of the $r \times r$ submatrix of $[x_{ij}]$ with column set $A$. Thus, the number of rank-$r$ representable matroids on $n$ elements is the number of realisable sets with respect to these $f_A$.

To bound this quantity, we apply the Lemma, for which we need to understand the parameters $N,m,a,d$. Now $m = rn \le n^2$ is just the number of variables. $N = \binom{n}{r} \le 2^n$ is the number of $r \times r$ submatrices. (We can in fact assume that $N = 2^n$ and $m = n^2$ by introducing dummy polynomials and variables). Finally, since the $f_A$ are determinants, we have $\deg(f_A) = r \le n$ and $\|f_A\| = 1$ for all $a$, so $(N,m,c,d) = (2^n,n^2,1,n)$ will do. To apply the lemma, it suffices to find a $k$ for which
\[ 2^k > (2kc(dN)^d)^{N\binom{Nd+m}{m}}, \] or in other words, \[k > N\binom{Nd+m}{m}\log_2(2kc(dN)^d)).\] If you are happy to believe that $k = 2^{2n^3}/2n$ satisfies this, then you can skip the next two estimates, but for the sticklers among us, here they are:
Using $(N,m,d,c) = (2^n,n^2,n,1)$ and $n \ge 20$ we have \[N\binom{Nd+m}{m} \le 2^n(2^{n+1}n)^{n^2} = 2^{n^2(n+1 + \log_2(n)) + n} \le 2^{2n^3}/6n^4.\] (Here we need that $n^3 > n^2(1+\log_2 n) + n + \log_2(6n^4)$, which holds for $n \ge 10$.) Similarly, for $k = 2^{2n^3}/(2n)$ we have $2kc < 2^{2n^3}$, so
\[\log_2(2kc(dN)^d)) < \log_2(2^{2n^3}(n2^n)^n) < 2n^3 + n^2 + n \log_2 n < 3n^3.\] Combining these estimates, we see that $k = 2^{2n^3}/2n$ satisfies the hypotheses of the lemma, so this $k$ is an upper bound on the number of rank-$r$ representable matroids on $n$ elements. This is only a valid bound for each particular $r$, but that is what our extra factor of $2n$ was for; the rank $r$ can take at most $n+1$ values, so the number of representable matroids on $[n]$ in total is at most $(n+1)k < 2nk = 2^{2n^3}$. This completes the proof of the main theorem.

[1] D. Mayhew, M. Newman, D. Welsh, and G. Whittle, On the asymptotic proportion of connected matroids, European J. Combin. 32 (2011), 882-890.
[2] T. Brylawski and D. Kelly, Matroids and combinatorial geometries, University of North Carolina Department of Mathematics, Chapel Hill, N.C. (1980). Carolina Lecture Series
[3] P. Nelson, Almost all matroids are non-representable, arXiv:1605.04288 [math.CO]
[4] L. Rónyai, L. Babai and M. K. Ganapathy, On the number of zero-patterns of a sequence of polynomials, J. Amer. Math. Soc. 14 (2001), 717–735.

Guest post by Carolyn Chun.

In a previous post, Dr. Pivotto posted about multimatroids.  Her post includes a definition of delta-matroid, and a natural way that delta-matroids arise in the context of multimatroid theory.  I recommend her post to readers interested in multimatroids, which generalize delta-matroids.  I will discuss delta-matroids in this post, their discovery and natural ways that a mathematician may innocently stumble into their wonderful world.

Delta-matroids were first studied by Andre Bouchet [BG].  I use $X\bigtriangleup Y$ to denote symmetric difference of sets $X$ and $Y$, which is equal to $(X\cup Y)-(X\cap Y)$. To get a delta-matroid, take a finite set $E$ and a collection of subsets $\mathcal{F}$, called feasible sets, satisfying the following.

I) $\mathcal{F}\neq \emptyset$.

II) If $F,F’\in \mathcal{F}$ and $e\in F\bigtriangleup F’$, then there exists $f\in F\bigtriangleup F’$ such that $F\bigtriangleup \{e,f\}$ is in $\mathcal{F}$.

Then $D=(E,\mathcal{F})$ is a delta-matroid.

It is worth noting that the feasible sets of a delta-matroid can have different cardinalities.  Taking all of the feasible sets of smallest cardinality gives the bases of a matroid, namely the lower matroid for $D$.  Likewise the feasible sets with maximum cardinality give the bases of the upper matroid of $D$.  No other collections of feasible sets of a given size are guaranteed to comprise the bases of a matroid.

Taking minors in delta-matroids is modeled well by considering the bases of a matroid minor.  Take $e\in E$.  As long as $e$ is not in every feasible set (that is, $e$ is not a coloop), the deletion of $e$ from $D$, written $D\backslash e$, is the delta-matroid $(E-e,\{F \mid F\in\mathcal{F}\text{ and }e\notin F\}).$  As long as $e$ is not in no feasible set (that is, $e$ is not a loop), then contracting $e$ from $D$, written $D/e$,  is the delta-matroid $(E-e,\{F-e \mid F\in \mathcal{F}\text{ and }e\in F\})$.  If $e$ is a loop or coloop, then $D\backslash e=D/e$.

There are several natural ways to get to delta-matroids.  They keep showing up, like the page where you die in a choose-your-own-adventure book.  The stairs grow dimmer and dimmer as you walk down the stone staircase into darkness.  You hear what may be screams in the distance.  You finally reach a closed door and hold your candle up to read the label, scrawled in blood.  The label on the door in this metaphor is “delta-matroids,” and they are not as scary as I portrayed them in that story.

***

0) Choose your own adventure by preceding to the appropriate section.

1) “I studied embedded graphs and now I see delta-matroids everywhere.”

2) “Partial duality brings me to delta-matroids.”

3) “I left out a basis axiom when defining matroids.  Ahoy, delta-matroids!”

4) “Circle graphs seemed like fun.  Until they hatched into delta-matroids.”

5) “C’mon, skew symmetric matrices.  This can’t end in delta-matroids.  Or can it?”

6) “DNA recombination in ciliates is my cup of tea.  Who knew I was brewing delta-matroids?”

7) “I abandon this quest and run away.”

***

1) “I studied embedded graphs and now I see delta-matroids everywhere.”

One way to arrive at delta-matroids is by considering cellularly embedded graphs, which I like to think of as ribbon graphs, following [EMM].

To get a cellularly embedded graph, start with a surface (compact, connected 2-manifold), then put vertices (points) and edges (curves between vertices) onto the surface so that no edges cross and each face (unbroken piece of the surface enclosed by edges and vertices) is basically a disk.  That is, no face contains a handle or cross-cap.

The particular embedding of a graph encodes more information than the abstract graph, which just encodes adjacencies.  There’s an order to the edges incident with a vertex as you circumnavigate the vertex in the embedding, but not in the abstract graph.  If you take the matroid of an embedded graph, then you lose the extra information stored in the embedding and you wind up with the matroid of the abstract graph.  For example, a pair of loops is indistinguishable from a pair of loops, even though the first pair of loops are embedded in a sphere so that the graph has three faces, and the second pair of loops is embedded in a torus so that the graph has one face.  By looking at the matroid of an embedded graph, you can’t even tell if the graph is embedded in an orientable surface or a non-orientable surface.  So matroids are the wrong object to model embedded graphs.   

Here is a figure by Steven Noble, where $\mathcal{R}$ is the set of ribbon graphs.  The correspondence between graphs and matroids is akin to the correspondence between ribbon graphs and question mark.  Likewise, graphs are to embedded graphs as matroids are to question mark. Andre Bouchet showed that delta-matroids are the question mark.

To get a ribbon graph, begin with a cellularly embedded graph, cut around the vertices and edges, and throw away the faces.  The vertices have become disks, and the edges have become ribbons connecting disks. Each missing face counts as a boundary component in the ribbon graph.  We have not lost any of the information from our embedding, since the faces were just disks and can be glued back along the boundary components to return to the original presentation.  Spanning forests in a ribbon graph are exactly what you expect, and the edge sets of spanning forests of a ribbon graph give the bases of a matroid.  To get a quasi-tree, we are allowed to delete edges (remove ribbons) from our ribbon graph so that we leave behind a ribbon graph with exactly as many boundary components as the original graph had connected components.  Note that each spanning forest is a quasi-tree.  The edge sets of quasi-trees are the feasible sets of a delta-matroid.  The reader may take a break to draw a ribbon graph with quasi-trees of multiple sizes.  For more information along these lines, I refer you to [CMNR1] or [CMNR2].

You may be familiar with the mutually enriching relationship between graphs and matroids.  There appears to be a similar mutually enriching relationship between ribbon graphs and delta-matroids.  Tutte said, “If a theorem about graphs can be expressed in terms of edges and circuits only it probably exemplifies a more general theorem about matroids.”  To alter this quote for our purposes, we say, “If a theorem about ribbon graphs can be expressed in terms of edges and quasi-trees only it probably exemplifies a more general theorem about delta-matroids.”

Protip:  Not every delta-matroid can be represented by a ribbon graph.  Geelen and Oum gave an excluded minor characterization for ribbon-graphic delta-matroids in [GO].

***

2) “Partial duality brings me to delta-matroids.”

A planar graph has a nice, well-defined dual.  Not all graphs have well-defined duals.  A graph that is not planar that is cellularly embedded in a surface has a well-defined dual, but the dual depends on the surface.  The matroid of a graph has a well-defined dual, as do all matroids.  Matroids are nice and general in that sense.  The notion of partial duality was developed by Chmutov [CG] in the context of embedded graphs, which can be viewed as ribbon graphs, as discussed in ending (1).  To get the dual from a ribbon graph, replace the boundary components with vertices, and the vertices with boundary components.  Now the ribbons still link up the vertices, but they are short and thick, rather than being long and ribbony.  In fact, one way to look at taking a dual is to focus on the ribbon edges, and simply switch the parts of each edge that are incident with vertices with the parts of the edge that are incident with boundary components.  Furthermore, there’s nothing particularly special about switching parts of the ribbon edges for the entire ribbon graph, rather than just a subset of the edges.  We use $G^A$ to denote the partial dual of a ribbon-graph, $G$, with respect to the edge set $A$.

Here is a drawing of a partial dual for a ribbon graph that Iain Moffatt drew.  Actually, it is a slide from a talk by Steven Noble using Iain Moffatt’s figures, with a dash of copyright infringement.  Luckily, this is being used for educational purposes and I’m not being paid for this.  Unless Spielberg buys the movie rights to this.  Then I will cut Noble and Moffatt in on the profits.

Partial duality is also natural enough in matroids, but the partial dual of a matroid is rarely a matroid.  Recall that $X\bigtriangleup Y$ denotes symmetric difference of sets $X$ and $Y$, which is equal to $(X\cup Y)-(X\cap Y)$.  A matroid $M=(E,\mathcal{B})$ defined in terms of its bases has a dual that may be written $(E,\{E\bigtriangleup B \mid B\in\mathcal{B}\})$.  The dual of a matroid is a matroid.  Now, for a set $A\subseteq E$, the entity $(E,\{A\bigtriangleup B\mid B\in\mathcal{B}\}):=M*A$ is the partial dual with respect to $A$.  There is a way to make sure that the partial dual with respect to $A$ is a matroid.  The following result is Theorem 3.10 in [CMNR2].

Theorem.  Let $M=(E,\mathcal{B})$ be a matroid and $A$ be a subset of $E$.  Then $M*A$ is a matroid if and only if $A$ is separating or $A\in\{\emptyset,E\}$.

Whenever $A$ is not empty or the ground set of a component of the matroid, then the partial dual with respect to $A$ is (scrawled in blood) a delta-matroid!  Matroids may be too abstract for most human beings, but they are not quite abstract enough to accommodate partial duality, which is a natural notion generalizing from ribbon graphs.  Delta-matroids are the right object, and we tend to view the set of partial duals of a delta-matroid as all belonging to the same equivalence class, just as matroid theorists often view a matroid and its dual as belonging to one equivalence class.

***

3) “I left out a basis axiom when defining matroids.  Ahoy, delta-matroids!”

For a set $E$ and a collection $\mathcal{B}$ of subsets of $E$, the set $\mathcal{B}$ form the bases of matroid $(E,\mathcal{B})$ exactly when the following hold.

I) $\mathcal{B}\neq \emptyset$.

II) If $B,B’\in \mathcal{B}$ and $e\in B\bigtriangleup B’$, then there exists $f\in B\bigtriangleup B’$ such that $B\bigtriangleup \{e,f\}$ is in $\mathcal{B}$.

III) The sets in $\mathcal{B}$ are equicardinal.

Omit (III) and hello, sailor!  You have the definition of a delta-matroid!  Just change the word “bases” to the phrase “feasible sets.”

***

4) “Circle graphs seemed like fun.  Until they hatched into delta-matroids.”

You approach the nest full of circle graphs with the stealth and speed of a mongoose, only to discover they are cracking open, each containing an even delta-matroid, where even will be defined in a moment.  You should have known that a circle graph is a ribbon-graph in disguise, and a ribbon-graph is, in turn, just a dressed-up delta-matroid.  Geelen and Oum used this relationship in [GO] to find an excluded-minor characterization for ribbon-graphic delta-matroids.

A delta-matroid is even exactly when all of its feasible sets have the same parity.  They do not all have to have even parity, odd parity is also fine in an even delta-matroid, as long as the parity is exclusive.  Maybe a better title would be a monogamous delta-matroid, but maybe not.  A circle graph is easy to view as a ribbon-graph.  To get a circle graph, you start with a circle, and draw chords (straight lines) across it, and then you check to see which ones cross each other.  Your circle graph has a vertex for each chord, and an edge between each pair of vertices corresponding to chords that cross.  Go back to the chord diagram and fatten up your chords into ribbons, which cross each other.  Where two chords cross, just let one ribbon go over the other, we don’t restrict ourselves to two-dimensions.  It doesn’t matter which ribbon is higher than the other, but don’t put any twists into the edges.  Now view the circle as a big vertex.  Your chord diagram has become a ribbon-graph.  It is worth noting that the ribbon-graph corresponds to a graph embedded in an orientable surface.

The edges in your circle graph now correspond to pairs of intertwined loops in your ribbon-graph.  By intertwined, I mean that two loops, $a$ and $b$, incident with a single vertex so that, when you circumnavigate the vertex they share, you hit $a$, $b$, $a$, and then $b$; rather than $a$, $a$, $b$, and $b$.  Now the feasible sets of your delta-matroid include the empty set (because your vertex has a single boundary component), no single-element sets, and each pair $\{v,w\}$ where $vw$ is an edge in your circle graph.  Check this by drawing a big vertex and two interlaced ribbon-graph loops and tracing around the boundary components.  You will find there’s only one boundary component.  The rest of the feasible sets of the delta-matroid come from the remaining quasi-trees in the ribbon-graph, but you’ll find that, mysteriously, there are no quasi-trees with an odd number of edges.  Ribbon-graphs from orientable surfaces give even delta-matroids.  Bouchet showed that even ribbon-graph delta-matroids also come naturally from 4-regular directed graphs.  For more information along these lines, see Section 4.2 and Section 5.2 of [CMNR1].

Bouchet and Duchamp showed in [BD] that ribbon-graphs correspond to a subset of binary delta-matroids, which will be considered in (5).  They did this by giving an excluded minor characterization for binary delta-matroids.  In [GO], Geelen and Oum built on the work of Bouchet [BC] in the area of circle graphs and found pivot-minor-minimal non-circle-graphs. As an application of this they obtained the excluded minors for ribbon-graphic delta-matroids.

***

5) “C’mon, skew symmetric matrices.  This can’t end in delta-matroids.  Or can it?”

A lot of matroid theorists enjoy representable matroids, which have matrix representations.  Delta-matroids do not disappoint.  Take an $E$x$E$ skew-symmetric matrix over your favorite field.  For $A\subseteq E$, consider the $A$x$A$ submatrix obtained by restricting to the rows and columns labeled by elements in $A$.  If this submatrix is non-singular, then put $A$ into the collection $\mathcal{F}$.  Guess what $(E,\mathcal{F})$ is.  A delta-matroid!  Every ribbon-graphic delta-matroid has a partial dual that has a binary matrix representation.  If you pick a field with characteristic other than two, then your delta-matroids representable over that field will be even.  This follows from the nature of skew-symmetric matrices.  For more information along these lines, see Section 5.7 in [CMNR1]

***

6) “DNA recombination in ciliates is my cup of tea.  Who knew I was brewing delta-matroids?”

The title to this section may sound like a good pick-up line, but I have had no success with it.  Ciliates (phylum Ciliophora) are single-celled organisms that experience nuclear dimorphism.  Their cells each contain two nuclei, which contain different, but related, genomes. The DNA reconstruction in ciliates has something to do with 4-regular graphs, which can be thought of as medial graphs of ribbon graphs.  I’m out of my depth here, so I will refer you to the amazing work of people who know more about this subject.  Jonoska and Saito put together a book on biomathematics that is on my reading list.  I’ll highlight in particular an article by Brijder and Hoogeboom [BH] in this book for more delta-matroids.  While you’re waiting for your local library to order that book, I suggest checking out [AJS] by Angeleska, Jonoska, and Saito.

***

7) “I abandon this quest and run away.”

Very well, you decide to abandon this quest and run away.  You drop your axe.  You put down your boomerang.  You throw away your ninja stars.  You retire the commander of your armies, and donate your blowtorches to charity.  You turn from the Siren-like call of the delta-matroids, but what is that sound?  Is the song growing stronger even as you run away?  Yes, delta-matroids seem to be in front of you every direction you face.  After a meltdown or two, you pull yourself together and return to (0), resolved to pick a different course of action.

***

[AJS] A. Angeleska, N. Jonoska, and M. Saito. DNA recombination through assembly graphs. Discrete Applied Mathematics. 157:14 (2009) 3020–3037.

[BC] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B. 60 (1994) 107–144.

[BG] A. Bouchet, Greedy algorithm and symmetric matroids, Math. Program. 38 (1987) 147– 159.

[BD] A. Bouchet and A. Duchamp, Representability of delta-matroids over GF(2), Linear Algebra Appl. 146 (1991) 67–78.

[BH] R. Brijder and H. Hoogeboom, The algebra of gene assembly in ciliates.  In: N. Jonoska and M. Saito (eds.) Discrete and Topological Models in Molecular Biology. Natural Computing Series, Springer, Heidelberg (2014) 289—307.

[CG] S. Chmutov, Generalized duality for graphs on surfaces and the signed Bollobás–Riordan polynomial, J. Combin. Theory Ser. B. 99 (2009) 617–638.

[CMNR1] C. Chun, I. Moffatt, S. Noble, and R. Rueckriemen, Matroids, delta-matroids, and embedded graphs, arXiv:1403.0920.

[CMNR2] C. Chun, I. Moffatt, S. Noble, and R. Rueckriemen, On the interplay between embedded graphs and delta-matroids, arXiv:1602.01306.

[EMM] J. Ellis-Monaghan and I. Moffatt, Graphs on surfaces: Dualities, Polynomials, and Knots, Springer, (2013).

[GO] J. Geelen, S. Oum, Circle graph obstructions under pivoting. J. Graph Theory. 61 (2009) 1–11.

In March Steve Noble came to the University of Western Australia for a few weeks and introduced me and Gordon to the <<add your favourite adjective here>> world of multimatroids. Multimatroids generalise matroids and even Delta matroids. Multimatroids were extensively studied by Bouchet in a series of papers (the first one being [B97]) and I will follow his terminology here.

Definitions

To define multimatroids we need a bit of setup. Let $K$ be a partition of a finite set $U$; in our context we call each class $k \in K$ a skew class and we say that two elements form a skew pair if they are contained in the same skew class. A subtransversal of $K$ is a subset of $U$ that contains at most one element from each skew class. A transversal is a maximal subtransversal (i.e. a subset of $U$ that contains exactly one element from each skew class). Denote by $\mathcal{S}(K)$ and $\mathcal{T}(K)$ the set of all subtransversals and transversals of $K$ respectively. Now let $r$ be a function from $\mathcal{S}(K) \rightarrow \mathbb{N}$ such that the following hold:

1. For every transversal $T$, the restriction of $r$ to $T$ induces a matroid on $T$.
2. For every subtransversal $S$ and any skew pair $\{x,y\}$ in a skew class disjoint from $S$, we have $r(S\cup x)-r(S)+r(S\cup y)-r(S)\geq 1$.

In other words, property 2. is saying that if we have a subtransversal $S$ and a skew class  $k$ not covered by $S$, then $r(S \cup x)=r(S)+1$ for all but possibly one $x \in k$.

Some properties and constructions

A multimatroid in which every skew class has size $p$ is called a $p$-matroid. From the definition it’s immediate that a 1-matroid is simply a matroid. There is another way of obtaining a multimatroid (in fact, a 2-matroid) from a matroid, as follows. Say that $N=(E,r)$ is a matroid and $N^*=(E,r^*)$ is its dual. Make two copies $E_1$ and $E_2$ of $E$, where, for every $e\in E$ we denote by $e_i$ the copy of $e$ in $E_i$ and similarly, for every subset $A \subseteq E$ we denote by $A_i$ the subset of $E_i$ corresponding to $A$ (and write $r(A_i)$ for $r(A)$, and similarly for $r^*$). Define a 2-matroid as follows: the ground set is $E_1 \cup E_2$, the skew classes are all pairs of the form $\{e_1,e_2\}$ for $e \in E$ and, for every subtransversal $S$, the rank of $S$ in the 2-matroid is $r(S\cap E_1) + r^*(S \cap E_2)$. Bouchet showed that, not only this is multimatroid, but in fact we can do a similar construction for any set of mutually orthogonal matroids $N_1,\ldots, N_n$. He also show that, conversely, if $T_1$ and $T_2$ are two disjoint transversals of a multimatroid $M$, then the matroids induced on $T_1$ and on $T_2$ are orthogonal (see [B98]).

Later in the post I’ll explain how Delta matroids correspond to 2-matroids, but first let’s talk about general multimatroids a bit more.

I defined multimatroids in terms of rank and as a matroid theorist the first question that pops to mind is whether we can talk about other matroid-like objects, such as independent sets, bases, etc. The answer is yes, but only while being extra careful. For example, we need to keep in mind that these terms only make sense when talking about subtransversals, not any subset of the ground set that you could think of. As one may expect, a subtransversal $S$ is independent if $r(S)=|S|$, otherwise it’s dependent. The bases of a multimatroid are the maximal independent sets and (by 2. above) if every skew class has size at least 2 then every base is a transversal. Finally a circuit is a minimal transversal that is not independent. In [B97] Bouchet gave equivalent definitions of multimatroids in terms of bases, independent sets and circuits.

One can also define minor operations for multimatroids, as in [B98], but here things are a bit different than for matroids: we don’t have a deletion and a contraction operation, but just a minor operation. Let $x$ by an element of a multimatroid $M=(U,K,r)$ and $k_x$ be the skew class containing $x$. Then the multimatroid $M|x$ has ground set $U’=U-k_x$, skew classes $K’=K-k_x$ and, for every subtransversal $S$ of $K’$ we have $r'(S)=r(S\cup x)-r(x)$. This looks a bit like contracting $x$ and deleting all other elements in $k_x$. In fact, if $M$ is the multimatroid obtained from a matroid $N$ and its dual as above, then $M|x_1$ is the multimatroid obtained from $N/x$ and its dual, while $M|x_2$ is the multimatroid obtained from $N\backslash x$ and its dual.

Delta matroids

First let me define what Delta matroids are. A Delta matroid is a pair $(E,\mathcal{F})$ where $E$ is a finite set and $\mathcal{F}$ is a nonempty family of subsets of $E$ (called feasible sets) satisfying the following property: if $F,F’\in \mathcal{F}$ and $x \in F\Delta F’$, then there exists $y \in F \Delta F’$ such that $F\Delta \{x,y\} \in \mathcal{F}$. Here $x$ could be equal to $y$, though if that doesn’t happen what we get is an even Delta matroid. The terminology is a bit unfortunate here, but basically a Delta matroid is even if all feasible sets have the same parity.

Now say that $(E,\mathcal{F})$ is a Delta matroid. As before, make two copies $E_1$ and $E_2$ of $E$ and define a 2-matroid as follows: the ground set is $E_1 \cup E_2$, the skew classes are all pairs of the form $\{e_1,e_2\}$ for $e \in E$ and the set of bases of the 2-matroid is $\{F_1 \cup (E_2-F_2) :  F \in \mathcal{F}\}$. Then what we get is a 2-matroid and in fact all 2-matroids may be obtained this way from Delta matroids.

References

[B97] A. Bouchet, Multimatroids I. Coverings by independent sets.  SIAM J. Discrete Math 10 (1997) 626-646.

[B98] A. Bouchet, Multimatroids II. Orthogonality, minors and connectivity.  Electron. J. Combinatorics 5 (1998) R8.