Lean Linked Decomposition Route Stops Before Dense Bag-Rank Concentration

Claim/Theorem

Keep the notation of [[dense-large-rank-lean-bag-yields-dense-tangle-breadth.md]], [[every-matroid-admits-optimal-lean-tree-decomposition.md]], [[linked-branch-decomposition-exists-at-optimal-width.md]], [[lean-matroid-bag-gives-rank-connected-set.md]], and [[good-codes-admit-logarithmic-width-lean-decomposition.md]].

The current sourced decomposition package does not imply any theorem of the following type for the target original qubit parity-check matroids M_n on qubit sets Q_n:

\[ H_{\mathrm{bag}}^{\beta}: \quad \text{some optimal lean tree-decomposition } (T_n,\tau_n) \text{ has a bag } B_n=\tau_n^{-1}(t_n) \]

with

\[ r_{M_n}(B_n) > (1-\beta)|Q_n| + k_n - 2 \]

and

\[ r_{M_n}(B_n) \ge 3k_n - 5 \]

for some k_n=\Omega(|Q_n|), or any source-faithful linked/adjacent-bag variant that would yield the same dense linear k_n-connected-set conclusion.

More precisely, all currently sourced lean / linked decomposition theorems still stop earlier, for three separate reasons.

1. Hlineny--Whittle's matroid tree-width is a node-width built from external branch rank defects, not from bag rank.

   For a tree-decomposition (T,\tau) of a matroid M, if the components of T-t are T_1,\dots,T_d and F_i=\tau^{-1}(V(T_i)), then the node-width at t is

   \[ w(t)=\sum_{i=1}^d r_M(E-F_i) - (d-1)r(M) \]

   and equivalently

   \[ w(t)=r(M)-\sum_{i=1}^d \bigl(r(M)-r_M(E-F_i)\bigr). \]

   So optimal tree-width measures how much rank defect can be placed into the branches around a node. It does not provide any lower bound on the rank of the bag

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

   Therefore width lower bounds, even optimal ones, do not by themselves imply dense bag rank.

2. Erde's lean-normalization theorem preserves width, and [[lean-matroid-bag-gives-rank-connected-set.md]] upgrades a bag only after its rank is already known to be large.

   Theorem 5.14 of Erde gives a lean tree-decomposition of width exactly \operatorname{tw}(M). For a fixed bag B, the lean property implies

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

   for all A\subseteq E(M).

   This is a local rank-connectedness statement for B. It says that a large-rank bag would be useful. It does not show that any optimal lean decomposition contains such a bag.

3. Linked branch decompositions control only edge widths and pathwise linkage between displayed cuts; they do not even supply bags.

   Geelen--Gerards--Whittle prove that every symmetric submodular connectivity function of branch-width n has a linked branch decomposition of width n. In such a decomposition the controlled objects are displayed edge cuts and the minimum edge width along paths between edges. No bag-rank statement appears in the theorem, and no currently sourced theorem converts those linked displayed cuts into one bag of large rank or into a dense connected set carried by a bounded connected region of the decomposition tree.

Hence the current graph stops strictly before bag-rank concentration. The exact missing theorem on this route is:

a decomposition-concentration theorem that converts optimal intrinsic width, in a lean or linked decomposition of the original qubit parity-check matroid, into one bag or one source-faithfully merged bounded cluster of adjacent bags whose rank is dense enough to trigger [[dense-large-rank-lean-bag-yields-dense-tangle-breadth.md]].

In particular, even the current positive intrinsic width theorem

\[ \operatorname{tw}(M_n),\,\operatorname{bw}(M_n)\in \Omega(|Q_n|/\log |Q_n|) \]

only yields optimal decompositions of logarithmic-order width. It does not localize that width into any bag rank of comparable order, let alone into the dense threshold

\[ r_{M_n}(B_n) > (1-\beta)|Q_n| + k_n - 2. \]

So the lean/linked decomposition route is now canonically sharpened to one exact unsourced step:

\[ \text{optimal intrinsic width} \Longrightarrow \text{dense bag-rank concentration} \Longrightarrow \text{dense tangle breadth}. \]

The middle implication is the missing theorem.

Dependencies

• [[dense-large-rank-lean-bag-yields-dense-tangle-breadth.md]]
• [[every-matroid-admits-optimal-lean-tree-decomposition.md]]
• [[linked-branch-decomposition-exists-at-optimal-width.md]]
• [[lean-matroid-bag-gives-rank-connected-set.md]]
• [[good-codes-admit-logarithmic-width-lean-decomposition.md]]

Conflicts/Gaps

• This node does not rule out that such a bag-concentration theorem might be true for the target family. It only records that no such theorem is currently sourced on the graph.
• The obstruction is stronger than the earlier “need a large-rank bag” phrasing: it identifies the exact mismatch between the quantities controlled by the decomposition theorems and the quantity needed by the dense-breadth route.

• Any future reopening of this route should bring either:

  • a theorem converting node-width or linked edge-width into one dense bag rank; or
  • a source-faithful adjacent-bag merger theorem that preserves enough connectivity to replace a single dense bag.

Sources

• 10.1016/j.ejc.2006.06.005
• 10.1016/j.jctb.2017.12.001
• 10.1006/jctb.2001.2082