Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909866223730688 |
|---|---|
| author | Fløystad, Gunnar Manchon, Dominique |
| author_facet | Fløystad, Gunnar Manchon, Dominique |
| contents | Submodular functions $z$ defined on the power set of a finite set are in bijection with generalized permutahedra $\egp(z)$. To any such $z$ we define a class of preorders, {\it conforming} preorders. We show the faces of $\egp(z)$ and the conforming preorders are in bijection. We investigate in detail this interplay between submodular functions and generalized permutahedra on one side, and conforming preorders on the other side, with many examples. In particular, the face poset structure of $\egp(z)$ correspond to two order relations $\lhd$ and $\btl$ on preorders, and we investigate their properties.
Ardila and Aguiar \cite{AA2017} introduced a Hopf monoid of submodular functions/generalized permutahedra. We show there is a bimonoid of modular functions cointeracting in a non-standard way. By recent theory of L.Foissy \cite{Fo2022}, on double bialgebras we get a canonical polynomial associated to any submodular function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_08200 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras Fløystad, Gunnar Manchon, Dominique Combinatorics Rings and Algebras 16T30, 06A11 Submodular functions $z$ defined on the power set of a finite set are in bijection with generalized permutahedra $\egp(z)$. To any such $z$ we define a class of preorders, {\it conforming} preorders. We show the faces of $\egp(z)$ and the conforming preorders are in bijection. We investigate in detail this interplay between submodular functions and generalized permutahedra on one side, and conforming preorders on the other side, with many examples. In particular, the face poset structure of $\egp(z)$ correspond to two order relations $\lhd$ and $\btl$ on preorders, and we investigate their properties. Ardila and Aguiar \cite{AA2017} introduced a Hopf monoid of submodular functions/generalized permutahedra. We show there is a bimonoid of modular functions cointeracting in a non-standard way. By recent theory of L.Foissy \cite{Fo2022}, on double bialgebras we get a canonical polynomial associated to any submodular function. |
| title | Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras |
| topic | Combinatorics Rings and Algebras 16T30, 06A11 |
| url | https://arxiv.org/abs/2409.08200 |