Many rays of the submodular cone
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908907769692160 |
|---|---|
| author | Loho, Georg Padrol, Arnau Poullot, Germain |
| author_facet | Loho, Georg Padrol, Arnau Poullot, Germain |
| contents | The study of the cone of submodular functions goes back to Jack Edmonds' seminal 1970 paper, which already highlighted the difficulty of characterizing its extreme rays. Since then, researchers from diverse fields have sought to characterize, enumerate, and bound the number of such rays. In this paper, we introduce an inductive construction that generates new rays of the submodular cone. This allows us to establish that the $n$-th submodular cone has at least $2^{2^{n-2}}$ rays, which improves upon the lower bound obtained from Hien Q. Nguyen's 1986 characterization of indecomposable matroid polytopes by a factor of order $\sqrt{n^3}$ in the exponent. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03177 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Many rays of the submodular cone Loho, Georg Padrol, Arnau Poullot, Germain Combinatorics Algebraic Geometry 52B11, 52B12, 52B40 (Primary), 90C25, 90C27 (Secondary) The study of the cone of submodular functions goes back to Jack Edmonds' seminal 1970 paper, which already highlighted the difficulty of characterizing its extreme rays. Since then, researchers from diverse fields have sought to characterize, enumerate, and bound the number of such rays. In this paper, we introduce an inductive construction that generates new rays of the submodular cone. This allows us to establish that the $n$-th submodular cone has at least $2^{2^{n-2}}$ rays, which improves upon the lower bound obtained from Hien Q. Nguyen's 1986 characterization of indecomposable matroid polytopes by a factor of order $\sqrt{n^3}$ in the exponent. |
| title | Many rays of the submodular cone |
| topic | Combinatorics Algebraic Geometry 52B11, 52B12, 52B40 (Primary), 90C25, 90C27 (Secondary) |
| url | https://arxiv.org/abs/2510.03177 |