A372839 Number of extreme submodular functions on n items, up to equivalence.

1, 5, 37, 117978

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

Table of n, a(n) for n=2..5.

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

Sequence in context: A081971 A350966 A086877 * A061674 A247709 A097276

Adjacent sequences: A372836 A372837 A372838 * A372840 A372841 A372842

Keyword

nonn,more

Author

Christoph Hertrich, May 14 2024

Status

approved