{"id":2338,"date":"2018-09-18T00:19:50","date_gmt":"2018-09-18T04:19:50","guid":{"rendered":"http:\/\/matroidunion.org\/?p=2338"},"modified":"2018-09-18T10:51:26","modified_gmt":"2018-09-18T14:51:26","slug":"decomposition-width-for-matroids","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=2338","title":{"rendered":"Decomposition-width for matroids"},"content":{"rendered":"

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<\/em>. This terminology has been used by Dan Kr\u00e1l [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.<\/p>\n

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

\"\"<\/a><\/p>\n

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

Now we consider branch-width and decomposition-width. A decomposition<\/em> 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<\/em> 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<\/em> 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<\/em> 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$.<\/p>\n

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\u00e1l proved this next result for matroids representable over finite fields.<\/p>\n

Proposition 1.<\/strong> Let $M$ be a matroid. Then $\\operatorname{dw}(M)\\geq \\operatorname{bw}(M)$.<\/p>\n

Proof.<\/em> 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
\n\\begin{align*}
\nr(U)-|B\\cap U| &=r(U)-(|B|-|B_{V}|)\\\\
\n&=r(U)-(r(M)-r(V))\\\\
\n&=r(U)-(r(U)-\\lambda(U))\\\\
\n&=\\lambda(U).
\n\\end{align*}
\nTherefore 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}$.<\/p>\n

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

Kr\u00e1l states the next result without proof. <\/p>\n

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

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

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

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

[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<\/em> 88<\/strong> (2003), no. 2, 261\u2013265.<\/p>\n

[Kra12] D. Kr\u00e1l. Decomposition width of matroids. Discrete Appl. Math.<\/em> 160<\/strong> (2012), no. 6, 913\u2013923.<\/p>\n

[Str10] Y. Strozecki. Enumeration complexity and matroid decomposition.<\/em> Ph.D. thesis, Universit\u00e9 Paris Diderot (2010).<\/p>\n

[Str11] Y. Strozecki. Monadic second-order model-checking on decomposable matroids. Discrete Appl. Math.<\/em> 159<\/strong> (2011), no. 10, 1022\u20131039.<\/p>\n","protected":false},"excerpt":{"rendered":"

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