A Yannakakis-type theorem for lifts of affine semigroups
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909263191867392 |
|---|---|
| author | Gouveia, João Wiebe, Amy |
| author_facet | Gouveia, João Wiebe, Amy |
| contents | Yannakakis' theorem relating the extension complexity of a polytope to the size of a nonnegative factorization of its slack matrix is a seminal result in the study of lifts of convex sets. Inspired by this result and the importance of lifts in the setting of integer programming, we show that a similar result holds for the discrete analog of convex polyhedral cones-affine semigroups. We define the notions of the integer slack matrix and a lift of an affine semigroup. We show that many of the characterizations of the slack matrix in the convex cone setting have analogous results in the affine semigroup setting. We also show how slack matrices of affine semigroups can be used to obtain new results in the study of nonnegative integer rank of nonnegative integer matrices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_14764 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Yannakakis-type theorem for lifts of affine semigroups Gouveia, João Wiebe, Amy Combinatorics Commutative Algebra 20M99 (Primary) 15A23, 52C07 (Secondary) Yannakakis' theorem relating the extension complexity of a polytope to the size of a nonnegative factorization of its slack matrix is a seminal result in the study of lifts of convex sets. Inspired by this result and the importance of lifts in the setting of integer programming, we show that a similar result holds for the discrete analog of convex polyhedral cones-affine semigroups. We define the notions of the integer slack matrix and a lift of an affine semigroup. We show that many of the characterizations of the slack matrix in the convex cone setting have analogous results in the affine semigroup setting. We also show how slack matrices of affine semigroups can be used to obtain new results in the study of nonnegative integer rank of nonnegative integer matrices. |
| title | A Yannakakis-type theorem for lifts of affine semigroups |
| topic | Combinatorics Commutative Algebra 20M99 (Primary) 15A23, 52C07 (Secondary) |
| url | https://arxiv.org/abs/2407.14764 |