%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