Submodular functions, generalized permutahedra, conforming preorders, and cointeracting bialgebras

Abstract: Generalized permutahedra (GP) is a central class of polyhedra with surprisingly many connections to various areas. Examples are matroid polytopes and and polymatroids. GP are also equivalent to submodular functions, an important class in optimization and economics.

To a submodular function we: Define a class of preorders, conforming preorders We show the faces of a GP are in bijection with the conforming preorders. The face poset structure of the GP induces two order relations on conforming preorders, subdivision and contraction, and we investigate their properties. There is Hopf monoid of submodular functions. We show it has a bimonoid of modular functions cointeracting in a non-standard way. By recent theory of L.Foissy this associates a canonical polynomial to any submodular function.

commutative algebraalgebraic geometrycombinatoricscategory theoryrings and algebras

Audience: researchers in the topic

( chat | paper | slides | video )

---

Algebraic and Combinatorial Perspectives in the Mathematical Sciences

Series comments: To receive announcements: Register into our mailing list by going to our main website www.math.ntnu.no/acpms/

---