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

%I #10 Jun 03 2024 18:17:15

%S 1,5,37,117978

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

%C 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.

%C 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.

%C The sequence is known to be doubly-exponential. To the best of my knowledge, only the four given terms are known.

%H L. S. Shapley, <a href="https://doi.org/10.1007/BF01753431">Cores of convex games</a>, Int J Game Theory 1 (1971), 11-26.

%H M. Studený, R. R. Bouckaert, and T. Kocka, <a href="http://ftp.utia.cas.cz/pub/staff/studeny/toronto-00.pdf">Extreme supermodular set functions over five variables</a>, Research report n. 1977, Institute of Information Theory and Automation, Prague (2000).

%K nonn,more

%O 2,2

%A _Christoph Hertrich_, May 14 2024