Nonnegative rank of the spanning-tree slack matrix

@misc{lemmata:2610.00003,
  title        = {Nonnegative rank of the spanning-tree slack matrix},
  author       = {Sebastian Pokutta},
  howpublished = {Lemmata Repository, lemmata:2610.00003, \url{https://lemmata.iol.berlin/abs/2610.00003}},
  year         = {2026},
  url          = {https://lemmata.iol.berlin/abs/2610.00003},
  note         = {Version a9429cb9cbf5; formal statements checked in Lean 4}
}

Abstract. A minimum-root decomposition of tree slacks can also accommodate every edge nonnegativity row without adding factors. This gives an explicit cubic upper bound on the nonnegative rank of the full spanning-tree slack matrix, saving $\binom n2$ factors over appending a separate factor for every edge. No symmetry of the factorization is required.

Status¶

All formal results are kernel-checked with Lean v4.35.0. What “checked” means.

View the full entry → · category: Optimization