OFFSET
2,2
COMMENTS
Number of extreme rays of the cone of (equivalence classes of) sub- or supermodular functions on an n-dimensional ground set. Two submodular functions are equivalent if their difference is a modular function. A submodular function f is extreme if any representation of f as a sum of submodular functions implies that the summands are equivalent to f.
Equivalently, number of extreme rays of the type cone of the (n-1)-dimensional permutahedron in R^n. That is, number of irreducible Minkowski summands (modulo translation and dilation) of the permutahedron. Here, a polytope P is irreducible if in any decomposition of P as a Minkowski sum, the summands must be (potentially translated and dilated) copies of P.
The sequence is known to be doubly-exponential. To the best of my knowledge, only the four given terms are known.
LINKS
L. S. Shapley, Cores of convex games, Int J Game Theory 1 (1971), 11-26.
M. Studený, R. R. Bouckaert, and T. Kocka, Extreme supermodular set functions over five variables, Research report n. 1977, Institute of Information Theory and Automation, Prague (2000).
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Christoph Hertrich, May 14 2024
STATUS
approved