{"id":1857,"date":"2016-06-14T08:38:45","date_gmt":"2016-06-14T12:38:45","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1857"},"modified":"2016-06-14T08:38:45","modified_gmt":"2016-06-14T12:38:45","slug":"an-intro-to-multimatroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1857","title":{"rendered":"An intro to multimatroids"},"content":{"rendered":"

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<\/em>>> world of multimatroids. Multimatroids generalise matroids and even Delta matroids. Multimatroids were\u00a0extensively studied by Bouchet in a series of papers (the first one being [B97]) and I will follow his terminology here.<\/p>\n

Definitions<\/strong><\/p>\n

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<\/em> and\u00a0we say that two elements form a skew pair<\/em> if they are contained in the same skew class.\u00a0A\u00a0subtransversal<\/i>\u00a0of $K$ is a subset of $U$ that contains at most one element from each skew class. A\u00a0transversal<\/em> 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:<\/p>\n

    \n
  1. For every transversal $T$, the\u00a0restriction of $r$ to $T$ induces a matroid on $T$.<\/li>\n
  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$.<\/li>\n<\/ol>\n

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

    Some properties and constructions<\/strong><\/p>\n

    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\u00a0is 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.\u00a0Make 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^*$).\u00a0Define 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\u00a0$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]).<\/p>\n

    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.<\/p>\n

    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\u00a0independent<\/em> if $r(S)=|S|$, otherwise it’s\u00a0dependent<\/em>. The\u00a0bases<\/em> of a multimatroid are the maximal independent sets and (by 2. above) if every\u00a0skew class has size at least 2 then every base is a transversal. Finally a\u00a0circuit<\/em> is a minimal transversal that is not independent. In [B97] Bouchet gave equivalent definitions of multimatroids in terms of bases, independent sets and circuits.<\/p>\n

    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$\u00a0is the multimatroid obtained from $N\\backslash x$ and its dual.<\/p>\n

    Delta matroids<\/strong><\/p>\n

    First let me define what Delta matroids are. A\u00a0Delta 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\u00a0feasible sets<\/em>) 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\u00a0even Delta matroid<\/em>. The terminology is a bit unfortunate here, but basically a Delta matroid is even if all feasible sets have the same parity.<\/p>\n

    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) : \u00a0F \\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.<\/p>\n

    References<\/strong><\/p>\n

    [B97] A. Bouchet, Multimatroids I. Coverings by independent sets<\/em>. \u00a0SIAM J. Discrete Math 10 (1997) 626-646.<\/p>\n

    [B98] A. Bouchet,\u00a0Multimatroids II. Orthogonality, minors and connectivity<\/em>. \u00a0Electron. J. Combinatorics 5 (1998) R8.<\/p>\n","protected":false},"excerpt":{"rendered":"

    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\u00a0extensively studied … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1857","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1857","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1857"}],"version-history":[{"count":21,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1857\/revisions"}],"predecessor-version":[{"id":1879,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/1857\/revisions\/1879"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1857"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1857"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1857"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}