# An intro to multimatroids

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.

## 2 thoughts on “An intro to multimatroids”

1. What is the conceptual reason for only allowing a single minor operation? A natural candidate would be to contract a single element x, and delete the rest of the elements in the skew class. Are multimatroids not closed under such operations?

On a related note, is there a way to generalise duality to multimatroids/p-matroids? Some desiderata of such a function would be that it’s an involution between multimatroids and that minors of duals are equal to duals of minors.

2. Kenneth: Yes, the operation you suggest is the minor operation. If you “lift” a matroid to a 2-matroid, then there is a skew class comprising two elements corresponding to each element of the matroid. Taking the multimatroid minor operation with respect to one of these two elements corresponds to deletion in the matroid and with respect to the other you get something corresponding to contraction in the matroid. It might be helpful to think of the skew classes of the multimatroid as “playing the role of elements” and the members of a skew class describing something like different “states” that an element might have. Although there is only one way to take a minor with respect to an element, by picking different elements of a skew class to take the minor you effectively get lots of different minors.

In some sense, a multimatroid already contains all of its duals. More precisely, if you construct a 2-matroid (or a 3-matroid) from a delta-matroid D, then the multimatroid M encodes D and all of its twists (twisted duals). Really, M depends on the collection of twists of D rather than D itself. To get D back from M, you have to remember what E_1 and E_2 are. Varying the partition of the elements into E_1 and E_2, and reversing the construction gives you all twists of D.

This site uses Akismet to reduce spam. Learn how your comment data is processed.