Dense Large-Rank Lean Bag Yields Dense Tangle Breadth

Claim/Theorem

Keep the notation of [[every-matroid-admits-optimal-lean-tree-decomposition.md]], [[lean-matroid-bag-gives-rank-connected-set.md]], [[large-k-connected-set-generates-order-k-tangle.md]], and [[sufficiently-dense-k-connected-set-yields-dense-tangle-breadth.md]].

Let M be a matroid on a ground set E of size n, let 0<\beta\le 1/2, and let (T,\tau) be a lean tree-decomposition of M. Suppose some bag

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

has rank

\[ r := r_M(B). \]

Assume there exists an integer k\ge 3 such that

\[ r \ge 3k - 5 \]

and

\[ r > (1-\beta)n + k - 2. \]

Then M has a tangle of order k whose breadth exceeds (1-\beta)n+k-2. Equivalently, M satisfies the canonical dense-tangle-breadth hypothesis of [[dense-tangle-breadth-is-the-canonical-remaining-intrinsic-target.md]].

Consequently every \beta-balanced cut L\subseteq E satisfies

\[ \lambda_M(L)\ge k-1. \]

In the binary/stabilizer setting, every \beta-balanced qubit cut satisfies

\[ \chi_L(\mathcal S)\ge k-1. \]

Proof.

1. Choose a basis I\subseteq B of the bag B, so

   \[ |I| = r. \]

2. By [[lean-matroid-bag-gives-rank-connected-set.md]], for every A\subseteq E(M),

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

   Since I is independent and I\subseteq B, this implies

   \[ r_M(A\cap B)\ge r_M(A\cap I)=|A\cap I| \]

   and

   \[ r_M(B-A)\ge r_M(I-A)=|I-A|. \]

   Therefore

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

   for all A\subseteq E(M).

3. Hence I is a cardinality-based connected set. In particular, for every k\le |I|+1, the set I is k-connected in the sense of [[tangle-breadth-gives-k-connected-set.md]]. By the hypothesis on r=|I|, the chosen k is admissible.

4. Since |I|=r\ge 3k-5 and |I|=r>(1-\beta)n+k-2, apply [[sufficiently-dense-k-connected-set-yields-dense-tangle-breadth.md]] to obtain a tangle of order k and breadth exceeding (1-\beta)n+k-2.

5. The final balanced-cut-rank conclusion then follows from [[dense-tangle-breadth-forces-balanced-cut-rank.md]].

So the lean-decomposition concentration route now reduces to one explicit quantitative invariant:

an optimal-width lean decomposition must contain a bag of sufficiently large rank, dense enough to beat the hardware balance threshold.

Special case.

If one chooses

\[ k := \left\lfloor \frac{r+5}{3} \right\rfloor, \]

then the side condition r\ge 3k-5 is automatic. Therefore a sufficient purely rank-density condition on one lean bag is

\[ r > (1-\beta)n + \left\lfloor \frac{r+5}{3} \right\rfloor - 2. \]

In particular, it is enough that

\[ r > \frac{3}{2}(1-\beta)n - \frac{1}{2}. \]

This is very strong, but it is now the exact theorem-sized decomposition-concentration target on this route.

Dependencies

• [[every-matroid-admits-optimal-lean-tree-decomposition.md]]
• [[lean-matroid-bag-gives-rank-connected-set.md]]
• [[large-k-connected-set-generates-order-k-tangle.md]]
• [[sufficiently-dense-k-connected-set-yields-dense-tangle-breadth.md]]
• [[dense-tangle-breadth-forces-balanced-cut-rank.md]]
• [[dense-tangle-breadth-is-the-canonical-remaining-intrinsic-target.md]]

Conflicts/Gaps

• This is a conditional reduction, not a theorem for the current Quantum Tanner / left-right-Cayley family.
• The hypothesis is very strong: it requires one bag in a lean decomposition whose rank is itself dense in the whole ground set.
• Existing good-code width theorems, such as [[good-codes-admit-logarithmic-width-lean-decomposition.md]], are far weaker. They provide only \Omega(n/\log n) width, not a dense bag rank.
• So the exact remaining gap on this route is a bag-concentration theorem, not merely the existence of lean decompositions or rank-connected bags.

Sources

• 10.1016/j.jctb.2017.12.001
• 10.37236/12467
• 10.48550/arXiv.2109.14599