Metraipolis › archive › dc_e294eec4fa2e

On integral polytopes related to Edmonds' problem — arXiv:2609.19703

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.19703
License (as archived): CC0-1.0
Archived: 2026-10-10T04:47:03.806Z
SHA-256 of the archived text: 1c18b21038adfee646f3bb93b965b2490c53d99403203d6109242654b3b629ee
Stable URL of this page: https://metraipolis.com/documento/dc_e294eec4fa2e

How to cite

On integral polytopes related to Edmonds' problem — arXiv:2609.19703 — arXiv (en), https://arxiv.org/abs/2609.19703 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e294eec4fa2e (Metraipolis archive dc_e294eec4fa2e, sha256 1c18b21038adfee646f3bb93b965b2490c53d99403203d6109242654b3b629ee)

BibTeX

@misc{dce294eec4fa2e,
  title = {On integral polytopes related to Edmonds' problem — arXiv:2609.19703},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.19703},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e294eec4fa2e; sha256 1c18b21038adfee646f3bb93b965b2490c53d99403203d6109242654b3b629ee},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19703. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In this paper, we study polyhedral aspects on commutative and noncommutative Edmonds' problems for computing the rank of linear symbolic matrix $A = \sum_{k=1}^m A_k x_k$. We regard them as linear optimization over integral polytopes ${\cal P}(A)$ and ${\cal Q}(A)$, respectively, which are obtained by the convex hulls of exponent vectors of subdeterminants of~$A$ and its blow-ups $A^{\{d\}} = \sum_{k=1}^m A_k \otimes X_k$ $(d=1,2,\ldots)$. By extending previously known results on nc-rank, we establish a hierarchy of integral polytopes ${\cal P}(A) \subseteq {\cal P}^{\leq 2}(A) \subseteq {\cal P}^{\leq 3}(A) \subseteq \cdots = {\cal Q}(A)$ and show that the integrality gap of ${\cal Q}(A)$ relative to ${\cal P}(A)$ is at least $1/2$. Further, we show that if each $A_k$ is rank-2 skew-symmetric, then the above hierarchy terminates at the second level and the integrality gap is improved to $2/3$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM).
Pagina del lavoro: https://arxiv.org/abs/2609.19703 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:15:33.123Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).