Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras
Fløystad, Gunnar, Manchon, Dominique
arXiv2024
Abstract
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.
Cite this publication
@article{flystad2024submodular,
author = {Fløystad and Gunnar and Manchon and Dominique},
title = {Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras},
journal = {arXiv},
year = {2024},
doi = {10.48550/arXiv.2409.08200},
eprint = {2409.08200},
archivePrefix = {arXiv}
}