Decomposition-width for matroids

In this post I want to discuss material I have been working on with Daryl Funk, Mike Newman, and Geoff Whittle. In particular, I’m going to discuss a parameter for matroids called decomposition-width. This terminology has been used by Dan Král [Kra12] and Yann Strozecksi [Str10, Str11]. We didn’t discover their work until after we had developed our own notion of decomposition-width, so our definition looks quite different from theirs, although it is equivalent. We have chosen to adopt their terminology.

Decomposition-width has a very natural motivation if you are familiar with matroids representable over finite fields, and matroid branch-width. Consider the following geometric illustration of the binary matroid $AG(3,2)$. The ground set has been partitioned into the sets $U$ and $V$. Let $X$ stand for the set of points coloured purple, and let $X’$ stand for the set of orange points. In the lefthand diagram, $V$ can distinguish between $X$ and $X’$. By this I mean that there is a subset $Z\subseteq V$ (we colour the points in $Z$ green) such that $X\cup Z$ is a circuit while $X’\cup Z$ is independent. However, in the righthand diagram, no subset of $V$ can distinguish $X$ and $X’$ in this way. Geometrically, this is because $X$ and $X’$ span exactly the same subset of the three-point line that lies in the spans of both $U$ and $V$ in the ambient binary space.

In general, let $M$ be a matroid on the ground set $E$, and let $(U,V)$ be a partition of $E$. We define the equivalence relation $\sim_{U}$ on subsets of $U$. We write $X\sim_{U} X’$ to mean that whenever $Z$ is a subset of $V$, both $X\cup Z$ and $X’\cup Z$ are independent, or neither is. This is clearly an equivalence relation.

Now we consider branch-width and decomposition-width. A decomposition of a matroid, $M=(E,\mathcal{I})$, consists of a pair $(T,\varphi)$, where $T$ is a binary tree (by this I mean that every vertex has degree one or three), and $\varphi$ is a bijection from $E$ to the set of leaves of $T$. If $e$ is an edge of $T$ joining vertices $u$ and $v$, then let $U_{e}$ be the subset containing elements $z\in E$ such that the path in $T$ from $\varphi(z)$ to $u$ does not contain $v$. Define $V_{e}$ symmetrically. We say that $U_{e}$ and $V_{e}$ are displayed by the decomposition. Define $\operatorname{bw}(M;T,\varphi)$ to be the maximum of $r(U_{e})+r(V_{e})-r(M)+1$, where the maximum is taken over all edges $e$ with end-vertices $u$ and $v$. Now I will define $\operatorname{dw}(M;T,\varphi)$ to be the maximum number of equivalence classes under the relation $\sim_{U_{e}}$, where we again take the maximum over all displayed sets $U_{e}$. The branch-width of $M$ is the minimum of $\operatorname{bw}(M;T,\varphi)$, where the minimum is taken over all decompositions $(T,\varphi)$. We define the decomposition-width of $M$ in the same way: as the minimum value taken by $\operatorname{dw}(M;T,\varphi)$. We write $\operatorname{bw}(M)$ and $\operatorname{dw}(M)$ for the branch- and decomposition-widths of $M$.

The notion of decomposition-width is clearly motivated by matroids over finite fields, but I won’t discuss those applications now. Instead we will continue to look at more abstract properties of decomposition-width. Král proved this next result for matroids representable over finite fields.

Proposition 1. Let $M$ be a matroid. Then $\operatorname{dw}(M)\geq \operatorname{bw}(M)$.

Proof. Let $E$ be the ground set of $M$, and let $U$ be a subset of $E$. Recall that $\lambda(U)$ is $r(U)+r(E-U)-r(M)$. We will start by proving that $\sim_{U}$ has at least $\lambda(U)+1$ equivalence classes. Define $V$ to be $E-U$. Let $B_{V}$ be a basis of $M|V$, and let $B$ be a basis of $M$ that contains $B_{V}$. Then $B\cap U$ is independent in $M|U$, and
r(U)-|B\cap U| &=r(U)-(|B|-|B_{V}|)\\
Therefore we let $(B\cap U)\cup\{x_{1},\ldots, x_{\lambda(U)}\}$ be a basis of $M|U$, where $x_{1},\ldots, x_{\lambda(U)}$ are distinct elements of $U-B$. Next we construct a sequence of distinct elements, $y_{1},\ldots, y_{\lambda(U)}$ from $B_{V}$ such that $(B-\{y_{1},\ldots, y_{i}\})\cup\{x_{1},\ldots, x_{i}\}$ is a basis of $M$ for each $i\in\{0,\ldots, \lambda(U)\}$. We do this recursively. Let $C$ be the unique circuit contained in\[(B-\{y_{1},\ldots, y_{i}\})\cup\{x_{1},\ldots, x_{i}\}\cup x_{i+1}\] and note that $x_{i+1}$ is in $C$. If $C$ contains no elements of $B_{V}$, then it is contained in $(B\cap U)\cup\{x_{1},\ldots, x_{\lambda(U)}\}$, which is impossible. So we simply let $y_{i+1}$ be an arbitrary element in $C\cap B_{V}$.

We complete the claim by showing that $(B\cap U)\cup\{x_{1},\ldots,x_{i}\}$ and $(B\cap U)\cup\{x_{1},\ldots, x_{j}\}$ are inequivalent under $\sim_{U}$ whenever $i< j$. Indeed, if $Z=B_{V}-\{y_{1},\ldots, y_{i}\}$, then $(B\cap U)\cup\{x_{1},\ldots, x_{i}\}\cup Z$ is a basis of $M$, and is properly contained in $(B\cap U)\cup\{x_{1},\ldots, x_{j}\}\cup Z$, so the last set is dependent, and we are done. Now assume for a contradiction that $\operatorname{bw}(M)>\operatorname{dw}(M)$. Let $(T,\varphi)$ be a decomposition of $M$ such that if $U$ is any set displayed by an edge of $T$, then $\sim_{U}$ has at most $\operatorname{dw}(M)$ equivalence classes. There is some edge $e$ of $T$ displaying a set $U_{e}$ such that $\lambda(U_{e})+1>\operatorname{dw}(M)$, for otherwise this decomposition of $M$ certifies that
$\operatorname{bw}(M)\leq \operatorname{dw}(M)$. But $\sim_{U_{e}}$ has at least $\lambda_{M}(U_{e})+1$ equivalence classes by the previous claim. As $\lambda_{M}(U_{e})+1>\operatorname{dw}(M)$, this contradicts our choice of $(T,\varphi)$. $\square$

Král states the next result without proof.

Proposition 2. Let $x$ be an element of the matroid $M$. Then $\operatorname{dw}(M\backslash x) \leq \operatorname{dw}(M)$ and
$\operatorname{dw}(M/x) \leq \operatorname{dw}(M)$.

Proof. Let $(T,\varphi)$ be a decomposition of $M$ and assume that whenever $U$ is a displayed set, then $\sim_{U}$ has no more than $\operatorname{dw}(M)$ equivalence classes. Let $T’$ be the tree obtained from $T$ by deleting $\varphi(x)$ and contracting an edge so that every vertex in $T’$ has degree one or three. Let $U$ be any subset of $E(M)-x$ displayed by $T’$. Then either $U$ or $U\cup x$ is displayed by $T$. Let $M’$ be either $M\backslash x$ or $M/x$. We will show that in $M’$, the number of equivalence classes under $\sim_{U}$ is no greater than the number of classes under $\sim_{U}$ or $\sim_{U\cup x}$ in $M$. Let $X$ and $X’$ be representatives of distinct classes under $\sim_{U}$ in $M’$. We will be done if we can show that these representatives correspond to distinct classes in $M$. Without loss of generality, we can assume that $Z$ is a subset of $E(M)-(U\cup x)$ such that $X\cup Z$ is independent in $M’$, but $X’\cup Z$ is dependent. If $M’=M\backslash x$, then $X\cup Z$ is independent in $M$ and $X’\cup Z$ is dependent, and thus we are done. So we assume that $M’=M/x$. If $U$ is displayed by $T$, then we observe that $X\cup (Z\cup x)$ is independent in $M$, while $X’\cup (Z\cup x)$ is dependent. On the other hand, if $U\cup x$ is displayed, then $(X\cup x)\cup Z$ is independent in $M$ and $(X’\cup x)\cup Z$ is dependent. $\square$

When we combine Propositions 1 and 2, we see that the class of matroids with decomposition-width at most $k$ is a minor-closed subclass of the matroids with branch-width at most $k$. The class of matroids with branch-width at most $k$ has finitely many excluded minors [GGRW03]. In contrast to this, Mike and I convinced ourselves that there are classes of the form $\{M\colon \operatorname{dw}(M) \leq k\}$ with infinitely many excluded minors. I guess we’d had a couple of beers by that point, but I think our argument holds up. I’ll eventually add that argument to this post. If anyone presents a proof in the comments before I do then I will buy them a drink at the next SIGMA meeting.


[GGRW03] J. F. Geelen, A. M. H. Gerards, N. Robertson, and G. P. Whittle. On the excluded minors for the matroids of branch-width $k$. J. Combin. Theory Ser. B 88 (2003), no. 2, 261–265.

[Kra12] D. Král. Decomposition width of matroids. Discrete Appl. Math. 160 (2012), no. 6, 913–923.

[Str10] Y. Strozecki. Enumeration complexity and matroid decomposition. Ph.D. thesis, Université Paris Diderot (2010).

[Str11] Y. Strozecki. Monadic second-order model-checking on decomposable matroids. Discrete Appl. Math. 159 (2011), no. 10, 1022–1039.

The matroid union is back!

It has been almost a year, but now the Matroid Union is back. Just as before, we’re planning to have a new post every 2 weeks on Monday. Over the next month Laura Anderson will be writing about a new application of oriented matroids in mathematical psychology, and I will introduce the deepest problem in the theory of infinite matroids, the infinite matroid intersection conjecture.

The team of core contributors has changed a little; we’re sorry to say goodbye to Stefan van Zwam and Irene Pivotto, who put a lot of energy into making this blog what it is. But we have some fresh new contributors: Laura Anderson and Nick Brettell. You can get some idea of what topics we are each hoping to cover here. A variety of other topics will be covered by guest posts. If you have any ideas for topics which you would like to see on the blog, or even which you would like to write about yourself, then please get in touch.