M. Studeny, R.R. Bouckaert, T. Kocka: Extreme supermodular set functions over five variables. Research report n. 1977, Institute of Information Theory and Automation, Prague, January 2000.

The class of supermodular functions on the power set of a non-empty finite set N forms a cone. It can be viewed as the direct sum of a linear subspace and of a cone of standardized supermodular functions which has finitely many extreme rays. Every extreme ray can be described by a standardized integer-valued set function. The situation in the case when N has five elements (variables) is analysed. A computer program was used to obtain a catalogue of all classes of permutably equivalent extreme standardized supermodular functions on the power set of N. Several alternative ways of representation of these equivalence classes are considered and various characteristics are used to describe them. Moreover, two relevant hypotheses valid in case of four variables are disproved in case of five variables.

AMS classification 68T30 90D99 52B99

extreme supermodular set function
permutably equivalent functions

A pdf copy (269kB) is available.