A Yannakakis-type theorem for lifts of affine semigroups
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _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 |