Unbounded matroids
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915624246050816 |
|---|---|
| author | Berggren, Jonah Martin, Jeremy L. Samper, José A. |
| author_facet | Berggren, Jonah Martin, Jeremy L. Samper, José A. |
| contents | A matroid base polytope is a polytope in which each vertex has 0,1 coordinates and each edge is parallel to a difference of two coordinate vectors. Matroid base polytopes are described combinatorially by integral submodular functions on a boolean lattice, satisfying the unit increase property. We define a more general class of unbounded matroids, or U-matroids, by replacing the boolean lattice with an arbitrary distributive lattice. U-matroids thus serve as a combinatorial model for polyhedra that satisfy the vertex and edge conditions of matroid base polytopes, but may be unbounded. Like polymatroids, U-matroids generalize matroids and arise as a special case of submodular systems. We prove that every U-matroid admits a canonical largest extension to a matroid, which we call the generous extension; the analogous geometric statement is that every U-matroid base polyhedron contains a unique largest matroid base polytope. We show that the supports of vertices of a U-matroid base polyhedron span a shellable simplicial complex, and we characterize U-matroid basis systems in terms of shelling orders, generalizing Björner's and Gale's criteria for a simplicial complex to be a matroid independence complex. Finally, we present an application of our theory to subspace arrangements and show that the generous extension has a natural geometric interpretation in this setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_02040 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Unbounded matroids Berggren, Jonah Martin, Jeremy L. Samper, José A. Combinatorics 05B35, 52B40, 52C35 A matroid base polytope is a polytope in which each vertex has 0,1 coordinates and each edge is parallel to a difference of two coordinate vectors. Matroid base polytopes are described combinatorially by integral submodular functions on a boolean lattice, satisfying the unit increase property. We define a more general class of unbounded matroids, or U-matroids, by replacing the boolean lattice with an arbitrary distributive lattice. U-matroids thus serve as a combinatorial model for polyhedra that satisfy the vertex and edge conditions of matroid base polytopes, but may be unbounded. Like polymatroids, U-matroids generalize matroids and arise as a special case of submodular systems. We prove that every U-matroid admits a canonical largest extension to a matroid, which we call the generous extension; the analogous geometric statement is that every U-matroid base polyhedron contains a unique largest matroid base polytope. We show that the supports of vertices of a U-matroid base polyhedron span a shellable simplicial complex, and we characterize U-matroid basis systems in terms of shelling orders, generalizing Björner's and Gale's criteria for a simplicial complex to be a matroid independence complex. Finally, we present an application of our theory to subspace arrangements and show that the generous extension has a natural geometric interpretation in this setting. |
| title | Unbounded matroids |
| topic | Combinatorics 05B35, 52B40, 52C35 |
| url | https://arxiv.org/abs/2312.02040 |