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.

Leave a Reply

Your email address will not be published. Required fields are marked *