Skip to content

Lean Matroid Bag Gives Rank-Connected Set

Claim/Theorem

Let \((T,\tau)\) be a lean tree-decomposition of a matroid \(M\) in the sense of Erde, and let

\[ B:=\tau^{-1}(t) \]

be the bag at a node \(t\in V(T)\). Then for every subset \(A\subseteq E(M)\),

\[ \lambda_M(A)\;\ge\;\min\{\,r_M(A\cap B),\ r_M(B-A)\,\}. \]

Equivalently, every bag of a lean matroid tree-decomposition is an internally rank-connected set: any partition that separates rank-k pieces of the bag on opposite sides must have connectivity at least k.

Proof sketch:

  1. Let
\[ k:=\min\{r_M(A\cap B),\ r_M(B-A)\}. \]

Choose subsets

\[ Z_1\subseteq A\cap B, \qquad Z_2\subseteq B-A \]

with

\[ r_M(Z_1)=r_M(Z_2)=k. \]
  1. Apply the lean property at the same bag \(t=t'\) from Erde's Definition 5.13. Since the path \(tTt'\) has no edges, the separator alternative is impossible, so one must have
\[ \lambda_M(Z_1,Z_2)\ge k, \]

where

\[ \lambda_M(Z_1,Z_2):=\min\{\lambda_M(X): Z_1\subseteq X,\ Z_2\subseteq E(M)-X\}. \]
  1. The set \(A\) itself separates \(Z_1\) from \(Z_2\), so
\[ \lambda_M(A)\ge \lambda_M(Z_1,Z_2)\ge k. \]

Hence the stated inequality follows.

In particular, if the bag \(B\) is independent, then

\[ \lambda_M(A)\ge \min\{|A\cap B|,\ |B-A|\} \]

for all \(A\subseteq E(M)\), so \(B\) is an actual cardinality-based connected set in the sense used by [[tangle-breadth-gives-k-connected-set.md]].

Dependencies

  • [[tangle-breadth-gives-k-connected-set.md]]

Conflicts/Gaps

  • The theorem is only useful if one can find a bag whose rank, or whose independent part, is large.
  • High tree-width or branchwidth alone does not yet imply the existence of a bag with linear rank or linear cardinality.
  • So this node does not settle the intrinsic frontier by itself. It converts the problem into a more concrete concentration question: force a large-rank or large independent bag inside an optimal lean tree-decomposition.

Sources

  • 10.1016/j.jctb.2017.12.001