arXiv:1612.06599v1 [math.CO] 20 Dec 2016

Basic facts concerning extreme supermodular functions∗
Milan Studený
the Institute of Information Theory and Automation of the CAS
December 21, 2016

Abstract
Elementary facts and observations on the cone of supermodular set functions are
recalled. The manuscript deals with such operations with set functions which preserve
supermodularity and the emphasis is put on those such operations which even preserve
extremality (of a supermodular function). These involve a few self-transformations of
the cone of supermodular set functions. Moreover, projections to the (less-dimensional)
linear space of set functions for a subset of the variable set are discussed. Finally, several
extensions to the (more-dimensional) linear space of set functions for a superset of the
variable set are shown to be both preserving supermodularity and extremality.

Keywords: supermodular function, standardizations, extreme supermodular function,
permutational transformation, reflection, lifting, support, minor, coarsening, contraction,
modular extension, replication

1

Introduction

The source of motivation for this technical report is the problem of characterization of
extreme supermodular functions. These functions play very important role in describing
(probabilistic) conditional independence structures; see the open problem from [7, Theme 6].
Nevertheless, supermodular functions and their mirror images, submodular functions, also
appear in various branches of discrete mathematics and have numerous applications in
computer science and optimization [5, 9, 10, 1]. There are criteria to recognize whether a
given supermodular function is extreme; one of them was proposed already in the 1970’s [4]
and a new elegant alternative has recently been proposed in [8].
In connection with the application of extreme supermodular functions in testing conditional independence implication by means of a computer a catalogue of all (types of)
extreme supermodular functions over 5 variables has been created [6]. The paper [2] contains several interesting results on (linear) operations with supermodular functions which
preserve extremality. The aim of this technical report is to gather the results on operations
with set functions preserving supermodularity and put the observations from [2] in this context. Specifically, the operations from [2, § 4] are interpreted as special cases of more general
∗

This research has been supported by the grant GAČR n. 16-12010S

1

supermodularity-preserving operations. This hopefully will make it possible, in future, to
interpret these operations in geometric terms in connection with game-theoretical concept
of the core polytope of a supermodular game [5, 8].
The next four sections of the report contain elementary concepts. Section 6 is then
devoted to self-transformations, which are mappings from RP(N ) to itself, where N is a
variable set and P(N ) its power set. Fundamental such operations are the permutational
transformation and the reflection transformation. A special lifting transformation and a
related concept of the support of a function in RP(N ) are discussed in Section 7. This
transformation is a basic extension operation, that is, a mapping from RP(M ) to RP(N ) ,
where M ⊆ N . On the other hand, Section 8 is devoted to various projections, that
is, mappings from RP(N ) to RP(M ) , where M ⊆ N . The important ones are the minor
projections and the coarsening transformation. These operations preserve supermodularity
but not extremality. The last two sections are devoted to the other extension operations
besides the lifting transformation. At least four different such operations are mentioned: two
kinds of so-called modular extensions are introduced and two kinds of so-called replications
are discussed. All of them are shown to preserve both supermodularity and extremality.

2

Notation

Let N be a finite non-empty set of variables; n := |N | ≥ 2 and P(N ) := {A : A ⊆ N }.
Given a ∈ N , the symbol a will also be used to denote the singleton {a}.
We consider the space RP(N ) of the dimension 2n equipped with scalar product
X
m(A) · u(A)
for m, u ∈ RP(N ) .
hm, ui :=
A⊆N

Given A ⊆ N , we introduce δA ∈ RP(N ) and mA⊆ ∈ RP(N ) by the formulas:


+1 if S = A,
+1 if A ⊆ S,
A⊆
δA (S) =
m (S) =
for S ⊆ N .
0 otherwise,
0 otherwise,
The symbol E(N ) will denote the class of elementary triplets ha, b|Ci, where a, b ∈ N are
distinct and C ⊆ N \ {a, b}. Every such triplet is assigned a vector uha,b|Ci ∈ ZP(N ) , called
an elementary imset, given by

 +1 if S = C or S = a ∪ b ∪ C,
uha,b|Ci (S) =
−1 if S = a ∪ C or S = b ∪ C,

0 otherwise.

Sometimes, even more general notation will be used: given an ordered triplet A, B, C of
pairwise disjoint subsets of N , we put
uhA,B|Ci (S) := δA∪B∪C + δC − δA∪C − δB∪C ,

where canceling terms is possible.

The symbol δ(⋆⋆), where ⋆⋆ is a predicate (= statement), will occasionally denote a zero-one
function whose value is +1 if the statement ⋆⋆ is valid and 0 otherwise.
2

3

Basic definitions

Definition 1 A function m : P(N ) 7→ R, that is, an element of RP(N ) , is supermodular if
∀ A, B ⊆ N

m(A) + m(B) ≤ m(A ∪ B) + m(A ∩ B) .

A modular function is defined by equality, the submodular one by converse inequality. The
symbol ♦(N ) will denote the class of supermodular functions over N , L(N ) the class of
modular functions over N .
Supermodular functions are characterized by means of n · (n − 1) · 2n−3 inequalities that
correspond to elementary imsets:
∀ m ∈ RP(N )

m ∈ ♦(N ) ⇔ [ ∀ ha, b|Ci ∈ E(N )

hm, uha,b|Ci i ≥ 0 ].

In particular, ♦(N ) is a (rational) polyhedral cone in RP(N ) . In fact, the above inequalities are just the facet-defining inequalities for the cone ♦(N ) [3, Corollary 11]; they imply
hm, uhA,B|Ci i ≥ 0 for pairwise disjoint sets A, B, C ⊆ N . Analogously, the class of submodular functions −♦(N ) is a polyhedral cone and L(N ) = ♦(N ) ∩ (−♦(N )) is a linear
subspace of RP(N ) .
Definition 2 Every m ∈ ♦(N ) is assigned a table of scalar products, which is a (nonnegative) function on E(N ):
Sm : ha, b|Ci ∈ E(N ) 7→ hm, uha,b|Ci i .
The induced independency model is I(m) := {ha, b|Ci ∈ E(N ) : hm, uha,b|Ci i = 0 }; its
complement D(m) := {ha, b|Ci ∈ E(N ) : hm, uha,b|Ci i > 0 } is the respective dependency
model. For ha, b|Ci ∈ E(N ), we will write a ⊥⊥ b | C [m] to denote hm, uha,b|Ci i = 0, that
is, ha, b|Ci ∈ I(m), meaning a is conditionally independent of b given C with respect to m.
The notation A ⊥⊥ B | C [m] for pairwise disjoint A, B, C ⊆ N will have analogous meaning.
Functions m1 , m2 ∈ ♦(N ) are quantitatively equivalent, or strongly equivalent, if they
induce the same table of scalar products:
m1 ≈ m2 := [ ∀ ha, b|Ci ∈ E(N ) hm1 , uha,b|Ci i = hm2 , uha,b|Ci i ].
Functions m1 , m2 ∈ ♦(N ) are qualitatively equivalent, or model equivalent, if they induce
the same (in)dependency model:
m1 ∼ m2 := [ ∀ ha, b|Ci ∈ E(N ) hm1 , uha,b|Ci i = 0 ⇔ hm2 , uha,b|Ci i = 0 ].
Of course, m1 ≈ m2 ⇒ m1 ∼ m2 for any m1 , m2 ∈ ♦(N ).

3

4

Quantitative equivalence and standardizations

Quantitative equivalence is easily characterized in terms of modular functions:
∀ m1 , m2 ∈ ♦(N )

m1 ≈ m2 ⇔ m1 − m2 ∈ L(N ) .

Since L(N ) has the dimension n + 1 and one of its bases consists of the functions m∅⊆ and
mi⊆ for i ∈ N , a more specific characterization is as follows: given m1 , m2 ∈ ♦(N ),
#
"
X
m1 ≈ m2 ⇔
∃ k ∈ R, ρ(i) ∈ R for i ∈ N
m1 − m2 = k · m∅⊆ +
ρ(i) · mi⊆ .
i∈N

A consistent way of the choice of a representative within (any) equivalence class of ≈
corresponds to fixing a complementary space S(N ) to L(N ) in RP(N ) , which is a linear
subspace of RP(N ) such that S(N ) ∩ L(N ) = {0} and S(N ) + L(N ) = RP(N ) . In this case
every m ∈ ♦(N ) has a uniquely determined decomposition
m = mS + l where mS ∈ ♦S (N ) := ♦(N ) ∩ S(N ) and l ∈ L(N ) ,
which situation will be denoted by ♦(N ) = ♦S (N ) ⊕ L(N ).
Then mS is the unique element of {r ∈ ♦(N ) : r ≈ m} in ♦S (N ). In particular,
∀ m1 , m2 ∈ ♦(N )

m1 ≈ m2 ⇔ m1S = m2S .

Three ways of the representative choice, that is, of a standardization, seem to be suitable:
the ℓ-standardization, named the lower standardization, is determined by
Sℓ (N ) := { m ∈ RP(N ) : m(∅) = 0 & ∀ i ∈ N

m(i) = 0 } and

♦ℓ (N ) := ♦(N ) ∩ Sℓ (N ) .
Given m ∈ ♦(N ), the formula for the respective representative mℓ ∈ ♦ℓ (N ) is
mℓ (T ) = m(T ) + kℓ +

X

ρℓ (i) for T ⊆ N ,

(1)

i∈T

where kℓ = −m(∅) and ρℓ (i) = m(∅) − m(i)

for i ∈ N .

A simple basic observation is that every ℓ-standardized supermodular function is
non-decreasing, that is, S ⊆ T ⇒ mℓ (S) ≤ mℓ (T ), and, hence, non-negative.
the u-standardization, named the upper standardization, is determined by
Su (N ) := { m ∈ RP(N ) : m(N ) = 0 & ∀ i ∈ N
♦u (N ) := ♦(N ) ∩ Su (N ) .

4

m(N \ i) = 0 },

Given m ∈ ♦(N ), the formula for the respective representative mu ∈ ♦u (N ) is
mu (T ) = m(T ) + ku +

X

ρu (i) for T ⊆ N ,

(2)

i∈T

where ku = (n − 1) · m(N ) −

X

m(N \ j)

j∈N

and

ρu (i) = m(N \ i) − m(N ) for i ∈ N .

Again, one can easily observe that every u-standardized supermodular function is
non-increasing, that is, S ⊆ T ⇒ mu (S) ≥ mu (T ), and, hence, non-negative.
the o-standardization, named the orthogonal standardization, is determined by
So (N ) := { m ∈ RP(N ) :

X

m(S) = 0 & ∀ i ∈ N

m(S) = 0 },

S⊆N : i∈S

S⊆N

♦o (N ) := ♦(N ) ∩ So (N ) .

X

Note that the requirements are, in fact, hm, m∅⊆ i = 0 and hm, mi⊆ i = 0 for i ∈ N ,
which means that So (N ) is the orthogonal complement to L(N ). The formula for the
respective representative mo ∈ ♦o (N ), on basis of any m ∈ ♦(N ), is
mo (T ) = m(T ) + ko +

X

ρo (i) for T ⊆ N ,

(3)

i∈T

n+1 X
·
m(S)
2n−1
2n
S⊆N
S⊆N


X
X
1
m(S) − 2 ·
m(S) 
ρo (i) = n−1 · 
2

where ko =

and

1

·

X

|S| · m(S) −

for i ∈ N .

S⊆N : i∈S

S⊆N

A notable fact is that in case of an integral (= integer-valued) ℓ-standardized representative the respective u-standardized representative is also integral, but the respective
o-standardized representative may be fractional. Moreover, the o-standardized representative need not be non-negative.
Remark There are other options. In the context of submodular functions and matroid
theory the following special polymatroidal standardization appears to be utilized: put
Sp (N ) := { m ∈ RP(N ) : m(∅) = 0 & ∀ i ∈ N

m(N \ i) = m(N ) } and

♦p (N ) := ♦(N ) ∩ Sp (N ) ,
which, however, in the supermodular context, leads to non-increasing and non-positive
representatives of equivalence classes of of quantitative equivalence ≈.

5

5

Qualitative equivalence and extremality

In this section, we assume the reader is familiar with some basic facts from polyhedral
geometry, gathered in Appendix, § A.
Definition 3 The symbol F(N ) will denote the lattice of non-empty faces of ♦(N ) ordered
by inclusion ⊆. We will also call it the face lattice of the cone ♦(N ). For any m ∈ ♦(N ),
F (m) will denote the smallest face containing m:
\
F (m) :=
{F : F ∈ F(N ) & m ∈ F } .
Observation 1

∀ m1 , m2 ∈ ♦(N )

F (m1 ) ⊆ F (m2 ) ⇔ I(m1 ) ⊇ I(m2 ) .

Proof. Let F∗ (N ) denote the class of facets of ♦(N ). As every face is the intersection
T
T
of facets containing it, ∀ m ∈ ♦(N ) one has F (m) = F ∈F (N ): m∈F F = F ∈F∗ (N ): m∈F F .
Hence, F (m1 ) ⊆ F (m2 ) iff

∀ F ∈ F∗ (N )

m2 ∈ F ⇒ m1 ∈ F ;

(4)

the necessity of (4) being derived by a contradiction. However, facets of ♦(N ) correspond
to elementary imsets; specifically, they have the form F = {m ∈ ♦(N ) : hm, uha,b|Ci i = 0 }
for triplets ha, b|Ci ∈ E(N ). Therefore, (4) is equivalent to the condition ∀ ha, b|Ci ∈ E(N ),
hm2 , uha,b|Ci i = 0 ⇒ hm1 , uha,b|Ci i = 0, which is exactly I(m1 ) ⊇ I(m2 ).

✷

Corollary 1 (characterization of qualitative equivalence)
∀ m1 , m2 ∈ ♦(N )
m1 ∼ m2 ⇔ I(m1 ) = I(m2 ) ⇔ F (m1 ) = F (m2 ).
Thus, the equivalence classes of ∼ are relative interiors of faces of ♦(N ). In other words,


∀ m1 , m2 ∈ ♦(N )
m1 ∼ m2 ⇔ ∃ F ∈ F(N ) m1 , m2 ∈ relint (F ) .

Proof. Indeed, for F ∈ F(N ), relint (F ) is the set of m ∈ ♦(N ) such that F (m) = F .

✷

Definition 4 We say that a supermodular function m ∈ ♦(N ) is extreme if F (m) is the
atom of the lattice (F(N ), ⊆).
In other words, m is extreme if it belongs to the relative interior of an atomic face of
F(N ), that is, of a face of F(N ) of the dimension dim(L(N )) + 1 = n + 2.
Observation 2
Let S(N ) be a complementary space to L(N ) in RP(N ) and let FS (N ) denote the lattice of
non-empty faces of the cone ♦S (N ) := ♦(N ) ∩ S(N ). The lattice (FS (N ), ⊆) is isomorhic
to the lattice (F(N ), ⊆). The correspondence is as follows:
every F ∈ F(N )

has the form F = FS + L(N ) where FS ∈ FS (N ).

The inverse relation is FS = F ∩ S(N ).
6

Proof. Note that both ♦(N ) and ♦S (N ) is defined by means of inequalities of the type
0 ≤ hm, uha,b|Ci i with ha, b|Ci ∈ E(N ) for m in the respective linear space, which is either
RP(N ) or S(N ). Thus, any facet of ♦(N ), respectively of ♦S (N ), is determined by such an
inequality. Because every face is the intersection of facets, every face of ♦(N ), respectively
of ♦S (N ), is determined by an inequality of the form 0 ≤ hm, vi, where v belongs to the
conic hull {uha,b|Ci : ha, b|Ci ∈ E(N ) }, denoted by U (N ). Note that U (N ) is a subset of
L(N )⊥ , the orthogonal complement of L(N ).
Hence, for any F ∈ F(N ), there exists v ∈ U (N ) with F = {m ∈ ♦(N ) : hm, vi = 0}.
Then L(N ) ⊆ F , and, because ♦(N ) = ♦S (N ) ⊕ L(N ), one has F = FS + L(N ) where
FS := F ∩ S(N ) has the form of a face of ♦S (N ), namely FS = {m ∈ ♦S (N ) : hm, vi = 0}.
Conversely, R ∈ FS (N ) is of the form R = {m ∈ ♦S (N ) : hm, vi = 0} for v ∈ U (N ).
Then L(N ) ⊆ {m ∈ ♦(N ) : hm, vi = 0} implies R + L(N ) ⊆ {m ∈ ♦(N ) : hm, vi = 0}.
Since the converse inclusion follows from the decomposition RP(N ) = S(N ) ⊕ L(N ), one
has R + L(N ) = {m ∈ ♦(N ) : hm, vi = 0} ≡ F ∈ F(N ). The fact that the correspondence
respects the inclusion relation ⊆ is trivial.

✷

Corollary 2
Let S(N ) be an arbitrary complementary space to L(N ) in RP(N ) . Then F ⊆ RP(N ) is an
atom of the lattice (F(N ), ⊆) iff it has the form F = R + L(N ), where R is an extreme ray
of the (pointed) cone ♦S (N ) = ♦(N ) ∩ S(N ).
Proof.

F is an atom of F(N ) iff it has the form F = R + L(N ), where R is an atom of

FS (N ). Since ♦S (N ) is pointed, the atoms of ♦S (N ) are the extreme rays of ♦S (N ).

✷

In other words, m ∈ ♦(N ) is extreme (in sense of Definition 4) iff its standardized
representative mS belongs to the relative interior of an extreme ray of ♦S (N ). Specifically,
the corresponding equivalence class of ∼ has the form
{r ∈ ♦(N ) : r ∼ m} = {α · mS + l : α > 0 & l ∈ L(N ) } .
The characterization of extreme supermodular functions is, therefore, equivalent to the
characterization of extreme rays of ♦S (N ). In particular, the extremality of a supermodular
function can be expressed in terms of any standardization, this concept does not depend on
the choice of a standardization.
Remark The above observation implies that, for extreme supermodular functions, quantitative and qualitative equivalences are very close. In fact, the following can be considered
as a cryptic equivalent definition of extremality: m ∈ ♦(N ) is extreme iff m 6∈ L(N ) and,
for any r ∈ ♦(N ), one has m ∼ r ⇔ [ ∃ α > 0 α · m ≈ r ]. Indeed, in case of non-extreme
P
non-modular m ∈ ♦(N ) \ L(N ) write mS = i αi · mi where αi > 0 and mi are at least
two generators of extreme rays in ♦S (N ). Then choose one of such mj , put r := mS + mj
and, because of mj ∈ F (m), observe that m ∼ r while there is no α > 0 with α · mS = r.
7

Remark Further important observation is that a necessary condition for the extremality (of
a supermodular function) is the existence of an integral (= integer-valued) representative
in the respective class (of qualitative equivalence). To observe that consider the lower
standardization: the cone ♦ℓ (N ) is pointed and every 0 6= m ∈ ♦ℓ (N ) satisfies m(N ) > 0.
The (bounded) polyhedron { m ∈ ♦ℓ (N ) : m(K) ≤ 1 } is specified by inequalities with
rational coefficients. Therefore, it is a polytope with vertices whose all components are
rational numbers. Its non-zero vertices are generators of extreme rays of ♦ℓ (N ) and each of
them can be multiplied by a positive integer to obtain a vector whose all components are
integers, that is, an element of ZP(N ) .

6

Self-transformations preserving supermodularity

In the subsequent text we deal with transformations which preserve supermodularity, mainly
the linear ones, and discuss whether they preserve the extremality (of a supermodular
function). We also ask which of them can be interpreted as transformations of equivalence
classes of ≈. This particular section is devoted to transformations of RP(N ) into itself.

6.1

Permutational transformations

Definition 5 Every permutation π : N → N (= a bijective mapping of N onto itself) can
be extended to a bijective mapping π of P(N ) onto itself by the relation
π(S) := { π(i) : i ∈ S} for any S ⊆ N .
This step allows one to define a permutational transformation Tπ : RP(N ) → RP(N ) :
Tπ : m ∈ RP(N ) 7→ m ◦ π ∈ RP(N ) ,

where m ◦ π (S) := m(π(S))

for S ⊆ N .

Clearly, the permutational transformation is invertible, its inverse is given by the inverse
permutation: (Tπ )−1 = Tπ−1 . As Tπ maps L(N ) to L(N ), m1 ≈ m1 ⇒ m1 ◦ π ≈ m2 ◦ π
and Tπ can be viewed as a mapping between equivalence classes of ≈.
Observation 3
Let π : N → N be a permutation and m ∈ RP(N ) . Then
(i) One has m ∈ ♦(N ) iff Tπ (m) ≡ m ◦ π ∈ ♦(N ) and the independency model induced
by m ◦ π is determined as follows:
a ⊥⊥ b | C [m ◦ π] ⇔ π(a) ⊥⊥ π(b) | π(C) [m]

for any ha, b|Ci ∈ E(N ).

(5)

In particular, Tπ maps ♦(N ) onto ♦(N ).
(ii) The transformation Tπ assigns faces of ♦(N ) to faces of ♦(N ) while the inclusion is
preserved: G ⊆ F iff Tπ (G) ⊆ Tπ (F ) for any G, F ⊆ RP(N ) .
In particular, m ∈ ♦(N ) is extreme in ♦(N ) iff Tπ (m) ≡ m ◦ π is extreme in ♦(N ).
8

Proof. (i): since Tπ is invertible and its inversion is a mapping of the same type, namely
Tπ−1 , it is enough to show m ∈ ♦(N ) ⇒ m ◦ π ∈ ♦(N ). Given ha, b|Ci ∈ E(N ), one has
hm ◦ π, uha,b|Ci i = m ◦ π (a ∪ b ∪ C) + m ◦ π (C) − m ◦ π (a ∪ C) − m ◦ π (b ∪ C)
= m(π(a) ∪ π(b) ∪ π(C)) + m(π(C)) − m(π(a) ∪ π(C)) − m(π(b) ∪ π(C))
= hm, uhπ(a),π(b)|π (C)i i ,

(6)

and the latter expression is non-negative because hπ(a), π(b)|π(C)i ∈ E(N ) and m ∈ ♦(N ).
The formula (6) also implies (5) because i ⊥⊥ j | K [m̃] means hm̃, uhi,j|Ki i = 0.
(ii): the first step is to show that facets of ♦(N ) are transformed by Tπ to facets of ♦(N ).
The facets have the form {m ∈ ♦(N ) : hm, uhi,j|Ki i = 0 } for hi, j|Ki ∈ E(N ). Realize that
(6) can be re-written in the form hm, uhi,j|Kii = hm ◦ π, uhπ−1 (i),π−1 (j)|π−1 (K)i i and obtain
Tπ ({m ∈ ♦(N ) : hm, uhi,j|Kii = 0}) =
= {m ◦ π ∈ ♦(N ) : hm ◦ π, uhπ−1 (i),π−1 (j)|π−1 (K)i i = 0}
= {r ∈ ♦(N ) : hr, uhπ−1 (i),π−1 (j)|π −1 (K)i i = 0} .
Since hi, j|Ki 7→ hπ −1 (i), π −1 (j)|π −1 (K)i is bijection of E(N ) onto E(N ), Tπ transforms
facets of ♦(N ) to themselves. Because every face of ♦(N ) is the intersection of facets
T
T
containing it and Tπ ( γ Fγ ) = γ Tπ (Sγ ), faces of ♦(N ) come to faces of ♦(N ). Since Tπ
is bijective, the inclusion (of faces) is preserved. Thus, the correspondence of faces of ♦(N )
determined by Tπ is an auto-isomorphism of the face lattice F(N ). The second claim in (ii)
is an easy consequence: atoms of F(N ) must be transformed to atoms of F(N ).
✷
Remark Permutational transformations respect three main standardizations from § 4:
∀ m ∈ ♦(N )

mℓ ◦ π = (m ◦ π)ℓ ,

mu ◦ π = (m ◦ π)u ,

mo ◦ π = (m ◦ π)o .

Indeed, it is easy to see that any complementary space S(N ) among Sℓ (N ), Su (N ) and
So (N ) satisfies the following condition:
∀ r ∈ RP(N )

r ∈ S(N ) ⇒ r ◦ π ∈ S(N ) .

To show this implies mS ◦ π = (m ◦ π)S for any m ∈ ♦(N ) consider a decomposition
m = mS + l with l ∈ L(N ), using linearity of Tπ write m ◦ π = mS ◦ π + l ◦ π and realize
l ◦ π ∈ L(N ). The uniqueness of the decomposition of m ◦ π implies what is desired.

6.2

Reflection transformation

Definition 6 We consider a reflection mapping ι : P(N ) → P(N ) defined by
ι(S) := N \ S

for S ⊆ N ,

which is a bijective mapping of P(N ) onto itself.
9

This allows one to define the reflection transformation Tι : RP(N ) → RP(N ) :
Tι : m ∈ RP(N ) 7→ m ◦ ι ∈ RP(N ) ,
where m ◦ ι (S) := m(ι(S)) ≡ m(N \ S) for S ⊆ N .
Given m ∈ RP(N ) , its reflection is the function Tι (m) ≡ m ◦ ι.
Evidently, the reflection transformation is invertible, its inverse is itself: (Tι )−1 = Tι .
Since Tι maps L(N ) to L(N ), m1 ≈ m1 implies m1 ◦ ι ≈ m2 ◦ ι and the reflection can be
interpreted as a transformation of equivalence classes of ≈.
Observation 4

Assume m ∈ RP(N ) . Then

(i) One has m ∈ ♦(N ) iff Tι (m) ≡ m ◦ ι ∈ ♦(N ) and the independency model induced
by m ◦ ι is determined as follows:
a ⊥⊥ b | C [m ◦ ι] ⇔ a ⊥⊥ b | N \ (a ∪ b ∪ C) [m]

for any ha, b|Ci ∈ E(N ). (7)

In particular, Tι maps ♦(N ) onto ♦(N ).
(ii) The transformation Tι assigns faces of ♦(N ) to faces of ♦(N ) while the inclusion is
preserved: G ⊆ F iff Tι (G) ⊆ Tι (F ) for any G, F ⊆ RP(N ) .
In particular, m ∈ ♦(N ) is extreme in ♦(N ) iff Tι (m) ≡ m ◦ ι is extreme in ♦(N ).
Note that the last fact from Observation 4(ii) was noticed in [6, § 5.1.3], [2, Lemma 4.1].
Proof. (i): since Tι is self-invertible, it is enough to show m ∈ ♦(N ) ⇒ m ◦ ι ∈ ♦(N ).
Given ha, b|Ci ∈ E(N ) and D := N \ (a ∪ b ∪ C), one has
hm ◦ ι, uha,b|Ci i = m ◦ ι (a ∪ b ∪ C) + m ◦ ι (C) − m ◦ ι (a ∪ C) − m ◦ ι (b ∪ C)
= m(D) + m(a ∪ b ∪ D) − m(b ∪ D) − m(a ∪ D)
= hm, uha,b|Di i = hm, uha,b|N \(a∪b∪C)i i ,

(8)

and the latter expression is non-negative because ha, b|Di ∈ E(N ) and m ∈ ♦(N ). The
formula (8) also implies (7) because i ⊥⊥ j | K [m̃] means hm̃, uhi,j|Kii = 0.
(ii): we first show that facets of ♦(N ), having the form {m ∈ ♦(N ) : hm, uhi,j|Ki i = 0 }
for hi, j|Ki ∈ E(N ), are transformed by Tι to facets of ♦(N ). Realize that (8) also says
hm, uhi,j|Kii = hm ◦ ι, uhi,j|N \(i∪j∪K) i and obtain
Tι ({m ∈ ♦(N ) : hm, uhi,j|Kii = 0}) = {m ◦ ι ∈ ♦(N ) : hm ◦ ι, uhi,j|N \(i∪j∪K)i i = 0}
= {r ∈ ♦(N ) : hr, uhi,j|N \(i∪j∪K)i i = 0} .
Since hi, j|Ki 7→ hi, j | N \ (i ∪ j ∪ K)i is bijection of E(N ) onto E(N ), Tι transforms facets
of ♦(N ) to themselves. Because every face of ♦(N ) is the intersection of facets containing
it and Tι is bijective, faces of ♦(N ) come to faces of ♦(N ) while their inclusion is preserved.
Hence, the correspondence of faces of ♦(N ) given by Tι is an auto-isomorphism of the face
lattice F(N ) and the second claim in (ii) is evident.
10

✷

Remark The reflection transformation behaves to the standardizations from § 4 as follows:
∀ m ∈ ♦(N )

mℓ ◦ ι = (m ◦ ι)u ,

mu ◦ ι = (m ◦ ι)ℓ ,

mo ◦ ι = (m ◦ ι)o .

Indeed, it is easy to see that
∀ r ∈ RP(N )

r ∈ Sℓ (N ) ⇔ r ◦ ι ∈ Su (N ),

r ∈ So (N ) ⇔ r ◦ ι ∈ So (N ) .

To show the former equivalence implies mℓ ◦ι = (m ◦ι)u for any m ∈ ♦(N ) write m = mℓ + l
with l ∈ L(N ) and by linearity of Tι get m ◦ ι = mℓ ◦ ι + l ◦ ι. Since mℓ ◦ ι ∈ Su (N ) and
l ◦ ι ∈ L(N ), the uniqueness of the decomposition of m ◦ ι with respect to Su (N ) implies
what is needed. The proof of the other formulas is analogous.

6.3

Monotonizations

There are transformations of ♦(N ) into itself which are not injective but ascribe monotone
(supermodular) functions to supermodular functions.
6.3.1

Lower and upper standardizations as linear monotonizations

In fact, the ℓ-standardization from § 4 can be viewed as a linear transformation from ♦(N )
to ♦(N ) which ascribes a non-decreasing function mℓ to any m ∈ ♦(N ). Analogously,
the u-standardization is a linear transformation from ♦(N ) to ♦(N ) which ascribes a nonincreasing function mu to m ∈ ♦(N ).
It follows from arguments in § 5 that these two transformations preserve extremality,
that is, they ascribe extreme supermodular functions to extreme ones. However, since they
assign quantitatively equivalent functions to supermodular functions they are not useful if
one is interested in generating new (= different) types of extreme supermodular functions.
6.3.2

Non-linear maximum-based monotonizations

There are also non-linear transformations of ♦(N ) into itself which ascribe monotone functions to functions from ♦(N ); they are defined through maximization over the class of
subsets, respectively of supersets. Specifically, given m ∈ ♦(N ), let us put
mmax⊆ (S) := max { m(T ) : T ⊆ S}

for S ⊆ N , and

mmax⊇ (S) := max { m(T ) : T ⊇ S}

for S ⊆ N .

Analogues of these transformations in the context of submodular functions have been pinpointed in [1, Prop. 19, 20], where mimimization over subsets/supersets is applied instead.
Observation 5
If m ∈ ♦(N ) then mmax⊆ is non-decreasing function in ♦(N ) and mmax⊇ is non-increasing
function in ♦(N ) .
11

Proof. Given A, B ⊆ N , there exist A′ ⊆ A and B ′ ⊆ B such that mmax⊆ (A) = m(A′ ) and
mmax⊆ (B) = m(B ′ ). Thus, we write using supermodularity of m:
mmax⊆ (A) + mmax⊆ (B) = m(A′ ) + m(B ′ ) ≤ m(A′ ∪ B ′ ) + m(A′ ∩ B ′ )
≤ max { m(T ) : T ⊆ A ∪ B } + max { m(T ) : T ⊆ A ∩ B }
= mmax⊆ (A ∪ B) + mmax⊆ (A ∩ B) ,
because A′ ∪ B ′ ⊆ A ∪ B and A′ ∩ B ′ ⊆ A ∩ B. The proof for mmax⊇ is analogous.

✷

The above-defined maximum-based monotonizations can be viewed as mutually dual;
specifically, they are reflections of each other in the sense
(m ◦ ι)max⊆ = mmax⊇ ◦ ι and (m ◦ ι)max⊇ = mmax⊆ ◦ ι

for every m ∈ ♦(N ).

However, they do not preserve extremality of a supermodular function, although they may
generate distinct types of extreme functions.
Example 1 Consider N = {a, b, c} and put
m0 := 2 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} ,
which an extreme non-decreasing function in ♦ℓ (N ). Quantitatively equivalent function
m1 := m0 − 12 · ma⊆ − 12 · mb⊆ ≈ m0 is not non-decreasing. The monotonization of m1 (the
maximization over subsets) gives a non-extreme non-decreasing supermodular function
mmax⊆
= δ{a,b,c} +
1

1
1
1
1
· δ{a,c} + · δ{b,c} = · (δ{a,b,c} + δ{a,c} ) + · (δ{a,b,c} + δ{b,c} ).
2
2
2
2

On the other hand, putting m2 := m0 − mc⊆ results in mmax⊆
= δ{a,b,c} + δ{a,b} , which is
2
an extreme function in ♦ℓ (N ), but of another permutation type than the original m2 ≈ m0 .
To complete the picture note that putting m3 := m0 − 23 · ma⊆ − 32 · mb⊆ − 23 · mc⊆ gives
mmax⊆
≡ 0, which is a modular function.
3

✷

The above example shows that m ≈ r 6⇒ mmax⊆ ≈ r max⊆ ; thus, the monotonization
cannot be interpreted as a mapping between equivalence classes of ≈.
Remark The observation that the maximum-based monotonization can “generate” a different extreme type from a given extreme type (of supermodular functions) leads to the
following idea. Let us introduce a binary relation
between ∼-equivalence classes:
for m, r ∈ ♦(N ),

m

r if

[ ∃ m∗ ≈ m such that mmax⊆
∼ r ].
∗

The question is whether this relation, respectively its transitive closure, offers a sensible
complexity comparison between distinct extreme types of supermodular functions. For
example, in case N = {a, b, c} one has m0
δN for m0 from Example 1 while ¬[δN
m0 ];
the same holds for m{a,b}⊆ in place of δN .
12

6.4

Outer composition and multiplication

An example of a transformation preserving supermodularity in the ℓ-standardized frame is
the outer composition with certain convex functions. An example of a binary operation on
♦ℓ (N ) is pointwise multiplication. These facts follow from the next observation, mentioned
in more general context in [9, Lemma 2.6.4].
Lemma 3 Let m, r ∈ ♦ℓ (N ) and g : [0, ∞)×[0, ∞) → R be a real function of two variables,
whose one-variable sections are non-decreasing and convex on [0, ∞) and which satisfies
∀ x ≤ x′ , y ≤ y ′

g(x′ , y) + g(x, y ′ ) ≤ g(x′ , y ′ ) + g(x, y) .

(9)

Then the composed function S ⊆ N 7→ g(m(S), r(S)) is supermodular on P(N ).
In particular, if h : [0, ∞) → R is a non-decreasing convex function with h(∅) = 0 then
m ∈ ♦ℓ (N ) ⇒ (h ◦ m) ∈ ♦ℓ (N ).
Proof. Consider A, B ⊆ N and the goal is to show
0 ≤ g(m(A ∪ B), r(A ∪ B)) − g(m(A), r(A)) − g(m(B), r(B)) + g(m(A ∩ B), r(A ∩ B)).
Let us denote m̄ := m(A ∪ B) + m(A ∩ B) − m(A) and r̄ := r(A ∪ B) + r(A ∩ B) − r(A);
since m and r are both supermodular and non-decreasing one has m(B) ≤ m̄ ≤ m(A ∪ B)
and r(B) ≤ r̄ ≤ r(A ∪ B). The goal is reached by summing the following six inequalities:
(a)

0 ≤ g(m(A ∪ B), r(A ∪ B)) − g(m(A ∪ B), r̄) − g(m(A), r(A ∪ B)) + g(m(A), r̄),

(b) 0 ≤ g(m(A ∪ B), r̄) − g(m(A ∪ B), r(A ∩ B)) − g(m̄, r̄) + g(m̄, r(A ∩ B)),
(c)

0 ≤ g(m(A), r(A ∪ B)) − g(m(A), r̄) − g(m(A), r(A)) + g(m(A), r(A ∩ B)),

(d) 0 ≤ g(m(A ∪ B), r(A ∩ B)) − g(m̄, r(A ∩ B))
− g(m(A), r(A ∩ B)) + g(m(A ∩ B), r(A ∩ B)),
(e)

0 ≤ g(m̄, r̄) − g(m̄, r(B)),

(f)

0 ≤ g(m̄, r(B)) − g(m(B), r(B)).

Indeed, most of the terms cancel after summing; specifically, ∓g(m(A∪B), r̄) in (a) and (b),
∓g(m(A), r(A ∪ B)) ± g(m(A), r̄) in (a) and (c), ∓g(m(A ∪ B), r(A ∩ B)) ± g(m̄, r(A ∩ B)) in
(b) and (d), ∓g(m̄, r̄) in (b) and (e), ±g(m(A), r(A ∩ B)) in (c) and (d), and ∓g(m̄, r(B))
in (e) and (f). It remains to observe the validity of those inequalities (a)-(f).
The inequality (a) is (9) with x = m(A), x′ = m(A ∪ B), y = r̄ and y ′ = r(A ∪ B);
note that x ≤ x′ and y ≤ y ′ because m is non-decreasing with respect to inclusion. The
inequality (b) is (9) with x = m̄, x′ = m(A ∪ B), y = r(A ∩ B) and y ′ = r̄; again x ≤ x′
and y ≤ y ′ for r is non-decreasing. The inequality (c) follows from the convexity of the
function y ∈ [0, ∞) 7→ ĝ(y) := g(m(A), y). Specifically, the convexity of ĝ means that it has
non-decreasing increments, which can be formulated in a symmetric way as follows:
∀ y ∈ [0, ∞), ∆ ≥ 0, δ ≥ 0,

0 ≤ ĝ(y + ∆ + δ) − ĝ(y + ∆) − ĝ(y + δ) + ĝ(y) .
13

Thus, putting y = r(A∩B), ∆ = r(A∪B)−r(A) and δ = r(A)−r(A∩B) results in (c). The
inequality (d) follows from the convexity of the function x ∈ [0, ∞) 7→ g̃(x) := g(x, r(A∩B));
where, analogously, x = m(A ∩ B), ∆ = m(A ∪ B) − m(A), δ = m(A) − m(A ∩ B). Finally,
(e) follows from the assumption that the function y ∈ [0, ∞) 7→ g(m̄, y) is non-decreasing
and (f) from the fact that x ∈ [0, ∞) 7→ g(x, r(B)) is non-decreasing.
The second statement (about the function h on [0, ∞)) follows easily from the main one by
putting g(x, y) := h(x) for x, y ≥ 0 and r := m.
✷
Corollary 4 Given m1 , m2 ∈ ♦ℓ (N ), their pointwise multiple
m3 (S) := m1 (S) · m2 (S)

for S ⊆ N ,

is also in ♦ℓ (N ). Analogously, if m1 , m2 ∈ ♦u (N ) then m3 ∈ ♦u (N ).
Proof. Use Lemma 3, where m = m1 , r = m2 and g(x, y) = x · y for x, y ≥ 0. The statement about u-standardized functions then follows from Observation 4(i) and the reflection
correspondence between ♦u (N ) and ♦ℓ (N ): mi ∈ ♦u (N ) ⇒ mi ◦ ι ∈ ♦ℓ (N ), i = 1, 2, and
one has m3 ◦ ι = (m1 ◦ ι) · (m2 ◦ ι) ∈ ♦ℓ (N ) ⇒ m3 ∈ ♦u (N ).

✷

However, neither the multiplication nor the outer composition with a convex function
preserves extremality of a supermodular function. Consider N = {a, b, c} and m0 from
Example 1. The multiplication of m0 with itself results in
m̂0 = 4 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} = 2 · δ{a,b,c} + (2 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} ),
which is not extreme in ♦(N ). Of course, m̂0 is the outer composition of m0 with h(x) := x2 .

7

Lifting and support

In this section we deal with a simple linear mapping to a higher-dimensional space which
preserves supermodularity and even extremality of a supermodular function. Then we
introduce a related characteristic of equivalence classes of supermodular functions.

7.1

Lifting transformation

Definition 7 Given M ⊆ N , the lifting transformation (from M to N ) is a mapping
TM րN : RP(M ) → RP(N ) defined as follows:
TM րN :

r ∈ RP(M ) 7→ TM րN (r) ≡ m ∈ RP(N ) ,
where [TM րN (r)](S) = m(S) := r(S ∩ M )

for S ⊆ N .

(10)

Given r ∈ RP(M ) the function m ≡ TM րN (r) is called the lifting of r (to N ). A function
m ∈ RP(N ) will be called a lifting from M if r ∈ RP(M ) exists with TM րN (r) = m.
14

Clearly, if m is a lifting of r ∈ RP(M ) then r is the restriction of m to P(M ). In
particular, TM րN is an injective mapping from RP(M ) to RP(N ) . Because TM րN maps
linearly L(M ) to L(N ), r 1 ≈ r 2 implies TM րN (r 1 ) ≈ TM րN (r 2 ) and the lifting can be
interpreted as a transformation of equivalence classes of ≈.
Observation 6

Assume M ⊆ N and r ∈ RP(M ) .

(i) Then r ∈ ♦(M ) iff TM րN (r) ∈ ♦(N ) and the independency model induced by
TM րN (r) is determined as follows: for any ha, b|Ci ∈ E(N ),
a ⊥⊥ b | C [ TM րN (r) ] ⇔ { a 6∈ M or b 6∈ M or a ⊥⊥ b | C ∩ M [r] } .

(11)

In particular, TM րN maps ♦(M ) into ♦(N ).
(ii) The lifting transformation commutes with basic standardizations: given r ∈ ♦(M ),
(TM րN (r))ℓ = TM րN (rℓ ), (TM րN (r))u = TM րN (ru ), (TM րN (r))o = TM րN (ro ).
Proof. (i): given ha, b|Ci ∈ E(N ), r ∈ RP(M ) and m = TM րN (r), one has
h TM րN (r), uha,b|Ci i = hm, uha,b|Ci i = m(a ∪ b ∪ C) + m(C) − m(a ∪ C) − m(b ∪ C)
= r((a ∪ b ∪ C) ∩ M ) + r(C ∩ M ) − r((a ∪ C) ∩ M ) − r((b ∪ C) ∩ M )
= δ( (a ∪ b) ⊆ M ) · hr, uha,b | C∩M i i ,

(12)

and, if r ∈ ♦(M ) then the latter expression is non-negative as ha, b | C ∩ M i ∈ E(M ) in case
(a ∪ b) ⊆ M ; (12) also implies (11) because i ⊥⊥ j | K [m̃] means hm̃, uhi,j|Kii = 0.
(ii): a basic observation is this: if a linear transformation T maps L(M ) into L(N ) and
a complementary space S(M ) into S(N ) (see § 4) then, given r ∈ ♦(M ), r = rS + l with
rS ∈ S(M ), l ∈ L(M ) one has T (r) = T (rS ) + T (l) with T (rS ) ∈ S(N ), T (l) ∈ L(N )
implying that T (r)S = T (rS ) for any r ∈ ♦(M ). We leave the reader to verify that TM րN
maps Sℓ (M ) to Sℓ (N ), Su (M ) to Su (N ) and So (M ) to So (N ).
✷
Remark However, not every standardization commutes with the lifting transformation.
Consider the following weird standardization, given by the complementary space
Sw (N ) := { m ∈ RP(N ) : m(∅) = 0 & ∀ i ∈ N

m(i) = −m(N ) }

Put N = {a, b, c}, M = {a, b} and r = δ{a,b} ∈ ♦(M ). One has rw =

1
3

to L(N ).

· δ{a,b} − 31 · δa − 13 · δb

while TM րN (r) = m{a,b}⊆ = δ{a,b,c} + δ{a,b} with
1
1
1
1
1
1
1
· δ{a,b,c} + · δ{a,b} − · δ{a,c} − · δ{b,c} − · δa − · δb − · δc ,
4
2
2
2
4
4
4
which differs from the lifting of rw to N .
m{a,b}⊆
=
w

The lifting transformation preserves extremality of a supermodular function. However,
one cannot use a direct argument to show that because faces are not mapped to faces.
Nevertheless, considering suitable standardization, for example the ℓ-standardization, allows
one to overcome this technical obstacle. The following auxiliary observation is used.
15

Lemma 5 If M ⊆ N then
F(M ) := { m ∈ ♦(N ) : mℓ (S) = mℓ (S ∩ M ) for any S ⊆ N }
=

{ m ∈ ♦(N ) : hm, uhi,j|Ci i = 0 for i ∈ N \ M , j ∈ N \ i, C ⊆ N \ (i ∪ j) }

is a face of ♦(N ). The face lattice of ♦(M ) is isomorphic to the face lattice of F(M ): a face
F of ♦(M ) is assigned the least face of ♦(N ) containing TM րN (F ) of the following form
F ∈ F(M ) 7−→ { TM րN (r) +

X

αi · mi⊆ : r ∈ F & αi ∈ R for i ∈ N \ M } ⊆ F(M ).

i∈N \M

Proof. Because m ≈ mℓ for any m ∈ RP(N ) , to verify the equality of two expressions for
F(M ) it is enough to show, for m = mℓ ∈ ♦ℓ (N ), that
[ m(S) = m(S ∩ M ) for any S ⊆ N ]
⇔ [ hm, uhi,j|Ci i = 0 for i ∈ N \ M , j ∈ N \ i, C ⊆ N \ (i ∪ j) ].
The necessity of the latter condition is evident as m(i ∪ j ∪ C) = m((j ∪ C) ∩ M ) = m(j ∪ C)
and m(i ∪ C) = m(C ∩ M ) = m(C) for i ∈ N \ M . To verify the sufficiency, we first show by
induction on |C| that m(i ∪ C) = m(C) for i ∈ N \ M and C ⊆ M . Indeed, the assumption
m is ℓ-standardized implies that in case |C| = 0; if |C| > 0 choose j ∈ C and write
0 = hm, uhi,j|C\ji i = m(i ∪ C) − m(C) −m(i ∪ (C \ j)) + m(C \ j) = m(i ∪ C) − m(C)
{z
}
|
0

by the induction premise. Second, we show by induction on |T | that m(T ∪ C) = m(C) for
T ⊆ N \ M and C ⊆ M . Indeed, we know that in case |T | ≤ 1; if |T | > 1 then choose
distinct i, j ∈ T , denote T ′ = T \ (i ∪ j) and write
0 = hm, uhi,j|T ′ ∪Ci i
= m(T ∪ C) −m(i ∪ T ′ ∪ C) − m(j ∪ T ′ ∪ C) + m(T ′ ∪ C) = m(T ∪ C) − m(C)
|
{z
}
−2·m(C)+m(C)

by the induction premise. This concludes the proof of sufficiency. The latter expression for
F(M ) implies that it is a face of ♦(N ).
To observe that the face lattices of ♦(M ) and F(M ) are isomorphic we introduce
Fℓ (M ) := F(M ) ∩ Sℓ (N ) = {m ∈ ♦ℓ (N ) : mℓ (S) = mℓ (S ∩ M ) for any S ⊆ N },
which is, by the above alternative description of F(M ), a face of ♦ℓ (N ). The proof of
isomorphy is based on Observation 2 and follows the following line:
♦(M ) ←→ ♦ℓ (M ) ←→ Fℓ (M ) ←→ F(M ) .

16

Firstly, Observation 2 applied to N = M and ℓ-standardization says that ♦(M ) and ♦ℓ (M )
have isomorphic face lattices. Secondly, it is easy to see that
Fℓ (M ) = { TM րN (r) : r ∈ ♦ℓ (M ) },
that is, TM րN maps bijectively ♦ℓ (M ) onto Fℓ (M ). Therefore, TM րN defines an isomorphism of face latices of ♦ℓ (M ) and Fℓ (M ). Thirdly, Observation 2 applied to N and
S(N ) = Sℓ (N ) says that the face F(M ) of ♦(N ) corresponds to Fℓ (M ) and allows one to
deduce that the face lattice of Fℓ (M ) and that of F(M ) are isomorphic. Putting these three
facts together implies what is desired.
It remains to realize that the face ascribed to F ∈ F(M ) has just the above described
form. This also follows from Observation 2:
F ∈ F(M ), F ⊆ ♦(M ) 7→ F ∩ ♦ℓ (M ) 7→ {TM րN (r) : r ∈ F ∩ ♦ℓ (M )}
7→ {TM րN (r) + l : r ∈ F ∩ ♦ℓ (M ) & l ∈ L(N ) }
= {TM րN (r) + l : r ∈ F & l ∈ L(N ) } ,
which is clearly the least face of ♦(N ) containing TM րN (F ). The fact L(M ) ⊆ F leads to
a further simplification of the latter expression.

✷

Corollary 6 Assume M ⊆ N and m ∈ ♦(N ) be a lifting of r ∈ ♦(M ) to N .
Then m is extreme in ♦(N ) iff r is extreme in ♦(M ).
Proof. This follows from the second claim in Lemma 5 because atomic faces of F(M ) are
just the atomic faces of ♦(N ) belonging to F(M ).
✷
An analogous observation for ℓ-standarized functions only was derived in [2, Lemma 4.3].

7.2

Support

The lifting transformation allows one to introduce a set characteristic for any m ∈ ♦(N ).
Its definition is not immediate: actually, the “right” concept appears to be a characteristic
of an equivalence class of quantitative equivalence ≈. That concept even occurs to be a
characteristic of an equivalence class of qualitative equivalence ∼.
Observation 7

Assume m ∈ RP(N ) .

(i) There exists the least set M ⊆ N such that m is a lifting from M , that is,
m(S) = m(S ∩ M )

for every S ⊆ N .

Let’s call this least set M ⊆ N the carrier of m and denote by carr (m).

17

(13)

(ii) Given m ∈ ♦(N ), one has
carr (mℓ ) ⊆ carr (m),

carr (mu ) ⊆ carr (m),

carr (mo ) ⊆ carr (m).

In particular, there exists the least carrier within { r ∈ ♦(N ) : r ≈ m}, namely the
set carr (mℓ ), which coincides with carr (mu ) and with carr (mo ).
Proof. (i): if both M1 ⊆ N and M2 ⊆ N satisfy (13), then their intersection does so:
m(S) = m(S ∩ M1 ) = m((S ∩ M1 ) ∩ M2 ) = m(S ∩ (M1 ∩ M2 )) for every S ⊆ N ,
where, first, (13) for M1 is applied and then (13) for M2 with S ∩ M1 in place of S is used.
Similarly, one can easily observe that if m satisfies (13) with M1 and M1 ⊆ M2 ⊆ N then
m satisfies (13) with M2 . In particular, the (non-empty) class of M ⊆ N such that (13)
holds for M is closed under intersection and supersets; therefore, it has the least element.
(ii): put M = carr (m) and realize that m is the lifting from M of its restriction r to P(M ).
By Observation 6(ii), mℓ is the lifting from M of rℓ . In particular, carr (mℓ ) ⊆ M and,
because mℓ ≈ m, carr (mℓ ) is the least carrier within {r ∈ ♦(N ) : r ≈ mℓ }. Analogous
arguments can be applied in the cases of u-standardization and o-standardization.

✷

The term “carrier” we use to name our auxiliary concept was taken over from [4]. As one
can expect, the carrier is not an invariant of an equivalence class of ≈: take N = {a, b, c},
m1 = m{a,b}⊆ and m2 = m1 + mc⊆ in which case m1 ≈ m2 but carr (m1 ) = {a, b} =
6
{a, b, c} = carr (m2 ). Thus, the substantial concept seems to be the following one.
Definition 8 (support)
Given m ∈ ♦(N ), the least carrier within the equivalence class { r ∈ ♦(N ) : r ≈ m} will
be called the support of m and denoted by supp (m).
Thus, Observation 7(ii) claims, in fact, that the support exists for any m ∈ ♦(N ) and,
moreover, supp (m) = carr (mℓ ) = carr (mu ) = carr (mo ). A deeper fact is as follows.
Observation 8

Given m1 , m2 ∈ ♦(N ), one has
m1 ∼ m2

⇒

supp (m1 ) = supp (m2 ) .

Proof. Given m1 , m2 ∈ ♦(N ) with m1 ∼ m2 , Corollary 1 says there exists a face F ∈ F(N )
of ♦(N ) such that m1 , m2 ∈ relint (F ). Of course, this face F is uniquely determined by
either m1 or m2 . Another note is that relint (F ) is closed under quantitative equivalence,
because m ≈ r implies m ∼ r and one can apply Corollary 1 to m and r.
Take the above face F ∈ F(N ) and consider a set function m ∈ relint (F ) 7→ carr (m)
on its interior. This function must have some minimizer with respect to set inclusion; let
M be the corresponding set-minimal carrier, that is,
M = carr (m) for some m ∈ relint (F )

& ∀ r ∈ relint (F )
18

¬[ carr (r) ⊂ M ] .

(14)

We are going to show
∀r ∈ F

carr (rℓ ) ⊆ M .

(15)

Indeed, since relint (F ) is closed under ≈-equivalence and m ≈ mℓ , Observation 7(ii) and
(14) allows us to deduce M = carr (mℓ ). Thus, mℓ is a lifting from M and m belongs to
the special face F(M ) of ♦(N ) introduced in Lemma 5. In particular,
m ∈ relint (F ) ∩ F(M ) ⊆ F ∩ F(M ) .
| {z }
F′

The sub-face F ′ of F cannot be a proper sub-face of F , because otherwise, by the definition
of relint (F ) a contradictory conclusion m 6∈ relint (F ) is derived. Hence, F ′ = F , which
is another way of saying F ⊆ F(M ). That implies, for every r ∈ F and S ⊆ N , that
rℓ (S) = rℓ (S ∩ M ). By the definition of the carrier, carr (rℓ ) ⊆ M and (15) is verified.
Now, (15) combined with (14) implies carr (rℓ ) = M for any r ∈ relint (F ). In particular,
the set-function r ∈ relint (F ) 7→ carr (rℓ ) ≡ supp (r) is constant on relint (F ), taking the
value M . Thus, one has supp (m1 ) = M = supp (m2 ) for original m1 , m2 ∈ ♦(N ).
✷

8

Projections

In this section we discuss supermodularity-preserving transformations from RP(N ) to a
lower-dimensional space RP(M ) where |M | ≤ |N |.

8.1

Linear projections: minors and their mean

A natural linear mapping from RP(N ) to RP(M ) , M ⊆ N , is the restriction of m ∈ RP(N ) to
P(M ). It can be viewed as a complementary operation to the lifting because its application
to TM րN (r) returns back r ∈ RP(M ) . However, the restriction is not the only such linear
mapping. One can alternatively ascribe to m ∈ RP(N ) the function r ∈ RP(M ) given by
r(S) := m(S ∪ (N \ M ))

for S ⊆ M ,

(16)

which defines a different projection of RP(N ) to RP(M ) . Both these projections can be
interpreted as special cases of a more general linear projection.
Definition 9 Assume M ⊆ N and N \ M = D ∪ E with D ∩ E = ∅, that is, the sets D, E
and M form a partitioning of N . The minor projection with deleting of D and extracting
of E is a mapping T−D|E : RP(N ) → RP(M ) defined as follows:
T−D|E :

m ∈ RP(N ) 7→ T−D|E (m) ≡ r ∈ RP(M ) ,

where [T−D|E (m)](S) = r(S) := m(S ∪ E)

for S ⊆ M .

(17)

Given m ∈ RP(N ) the function r ≡ T−D|E (m) is called the minor of m obtained by deleting
of D and extracting of E. A function r ∈ RP(M ) , M ⊆ N , will be called a minor of
m ∈ RP(N ) if a partitioning of N \ M into sets D and E exists such that T−D|E (m) = r.
19

The terminology is motivated by matroid theory, where these operations (with rank
functions of matroids) are named analogously. Because T−D|E maps linearly L(N ) to
L(M ), m1 ≈ m2 implies T−D|E (m1 ) ≈ T−D|E (m2 ); thus, T−D|E can be interpreted as a
transformation of equivalence classes of ≈. Minor projections preserve supermodularity.
Observation 9

Assume M ⊆ N and N \ M = D ∪ E with D ∩ E = ∅. If m ∈ ♦(N )

then T−D|E (m) ∈ ♦(M ) and the independency model induced by T−D|E (m) is as follows:
a ⊥⊥ b | C [ T−D|E (m) ] ⇔ a ⊥⊥ b | C ∪ E [m]

for any ha, b|Ci ∈ E(M ).

(18)

In particular, T−D|E maps linearly ♦(N ) into ♦(M ).
Proof. Assume m ∈ ♦(N ) and put r := T−D|E (m). Given ha, b|Ci ∈ E(M )
h T−D|E (m), uha,b|Ci i = hr, uha,b|Ci i = r(a ∪ b ∪ C) + r(C) − r(a ∪ C) − r(b ∪ C)
= m(a ∪ b ∪ C ∪ E) + m(C ∪ E) − m(a ∪ C ∪ E) − m(b ∪ C ∪ E)
= hm, uha,b|C∪Ei i ≥ 0,

(19)

because ha, b|C ∪ Ei ∈ E(N ) and m ∈ ♦(N ). The formula (19) also implies (18) because
i ⊥⊥ j | K [m̃] means hm̃, uhi,j|Kii = 0.

✷

The above discussed restriction to P(M ) can be interpreted as the minor projection with
deleting of N \M , that is, D = N \M , E = ∅ (no extraction part); a simplified notation can
be T−D then. In the context of the corresponding operation with (induced) independency
models, given by (18) with E = ∅, the name marginalization is common.
Similarly, the mapping (16) is called the minor projection with extracting of N \ M , that
is, D = ∅, E = N \ M (no deletion part); shorter simpler notation could be T|E . Some
books on matroid theory use the term “contraction” instead of “extraction”, but we found
that misleading because “contraction” much better fits another operation which discussed
later in § 8.2. In the context of the operation with independency models, given by (18) with
E = N \ M , the name conditioning has often been used.
It is easy to see that any minor projection is a linear transformation complementary to
the lifting transformation in the sense that T−D|E ◦ TM րN is identity, formally
∀ M ⊆ N, D ∪ E = N \ M, D ∩ E = ∅

T−D|E ( TM րN (r) ) = r for any r ∈ RP(M ) .

However, the minor projections do not preserve extremality of a supermodular function.
Example 2 Consider N = {a, b, c, d}, M = {a, b, c} and put
m∗ := 2 · δ{a,b,c,d} + δ{a,b,c} + δ{a,b,d} + δ{a,c,d} ,
which an extreme non-decreasing function in ♦ℓ (N ). The extraction of E = {d} gives
T|d (m∗ ) = 2 · δ{a,b,c} + δ{a,b} + δ{a,c} = (δ{a,b,c} + δ{a,b} ) + (δ{a,b,c} + δ{a,c} ) ,
20

which is not an extreme supermodular function. Another example is
r∗ := 3 · δ{a,b,c,d} + 2 · δ{a,b,c} + 2 · δ{a,b,d} + 2 · δ{a,c,d} + δ{b,c,d} + δ{a,b} + δ{a,c} + δ{a,d} ,
which is also an extreme supermodular function in ♦ℓ (N ). The deletion of D = {d} gives
the same result T−d (r∗ ) = (δ{a,b,c} + δ{a,b} ) + (δ{a,b,c} + δ{a,c} ).

✷

Remark Another linear projection from RP(N ) to RP(M ) , M ⊆ N , is as follows: assign to
m ∈ RP(N ) the function r ∈ RP(M ) given by the formula
r(S) :=

2|M |
·
2|N |

X

m(S ∪ L)

for any S ⊆ M .

(20)

L⊆N \M

This linear mapping can be interpreted as the mean-minor projection because (20) can be
re-written as
r(S) =

1
2|N \M |

·

X

for S ⊆ M .

[T−D|E (m)](S)

D,E⊆N \M, D∩E=∅

Being a convex combination of (all) minor projections, this mean-minor projection also
maps linearly ♦(N ) to ♦(M ) and is complementary to the lifting transformation. The
independency model induced by r given by (20) is determined as follows:
a ⊥⊥ b | C [ r ] ⇔ { ∀ L ⊆ N \ M

a ⊥⊥ b | C ∪ L [m] }

for any ha, b|Ci ∈ E(M ).

As one can expect, the mean-minor projection does not preserve extremality; one can follow
Example 2 and observe that m∗ = 2 · δ{a,b,c,d} + δ{a,b,c} + δ{a,b,d} + δ{a,c,d} has the projection
1
1
1
· (δ{a,b,c} + δ{a,b} ) + · (δ{a,b,c} + δ{a,c} ) + · δ{a,b,c}
2
2
2

to M = {a, b, c} .

An additional comment on the linear projections is that the deletion T−N \M preserves
ℓ-standardization, the extraction T|N \M preserves u-standardization and the mean-minor
projection preserves o-standardization; but they do not preserve the other standardizations.
Thus, it seems these three linear projections “correspond” to the basic standardizations.

8.2

Coarsening and contraction

Besides minor projections, there is another linear supermodularity-preserving mapping to
a lower-dimensional space. To illustrate the idea consider a set S ⊆ N of variables and
imagine we wish to “contract” the set S into a single variable s ∈ S. The following concept
of coarsening generalizes the idea of the contraction operation.

21

Definition 10 Let N, M be sets of variables and σ : N → M a mapping onto M . It induces
a pre-image mapping σ −1 : P(M ) → P(N ). The coarsening transformation determined by
σ is a mapping Tσ−1 : RP(N ) → RP(M ) defined as follows:
Tσ−1 : m ∈ RP(N ) 7→ m ◦ σ −1 ∈ RP(M ) , where m ◦ σ −1 (T ) := m(σ−1 (T )) for T ⊆ M . (21)
A special case of this operation is as follows: given s ∈ S ⊆ N and N ′ := (N \ S) ∪ s ⊆ N
′
the contraction (of S to s) is the mapping TS→s : RP(N ) → RP(N ) defined as the coarsening
transformation determined the mapping σ : N → N ′ given by

s
if t ∈ S,
σ(t) =
for t ∈ N .
t
if t ∈ N \ S,
In particular, given m ∈ RP(N ) , s ∈ S ⊆ N and r := TS→s (m), one has
r(L) = m(L) and r(L ∪ s) = m(L ∪ S)

for L ⊆ N \ S,

which operation clearly differs from the minor operation, either that with deleting of S \ s
and that with extracting of S \ s. Because Tσ−1 maps linearly L(N ) to L(M ), m1 ≈ m2
implies Tσ−1(m1 ) ≈ Tσ−1(m2 ) and the coarsening can be interpreted as a transformation of
equivalence classes of ≈; in particular, the same holds for the contraction.
Another comment is that the permutation transformation Tπ from § 6.1 can be viewed
as a special case of the coarsening transformation Tσ−1, with σ being the inverse of π. The
coarsening also preserves supermodularity.
Observation 10

Assume that σ : N → M a mapping onto M . If m ∈ ♦(N ) then

Tσ−1(m) ∈ ♦(M ) and the independency model induced by Tσ−1(m) is as follows:
a ⊥⊥ b | C [ Tσ−1(m) ] ⇔ σ−1 (a) ⊥⊥ σ−1 (b) | σ−1 (C) [m]

for any ha, b|Ci ∈ E(M ). (22)

In particular, given s ∈ S ⊆ N , TS→s maps ♦(N ) to ♦(N ′ ) with N ′ := (N \ S) ∪ s ⊆ N .
Proof. Assume m ∈ ♦(N ) and put r := Tσ−1(m). Given ha, b|Ci ∈ E(M )
h Tσ−1(m) , uha,b|Ci i = hr, uha,b|Ci i = r(a ∪ b ∪ C) + r(C) − r(a ∪ C) − r(b ∪ C)
= m(σ−1 (a ∪ b ∪ C)) + m(σ−1 (C)) − m(σ−1 (a ∪ C)) − m(σ−1 (b ∪ C))
= m( σ−1 (a) ∪ σ−1 (b) ∪ σ−1 (C) ) + m( σ−1 (C) ) − m( σ−1 (a) ∪ σ−1 (C) )
− m( σ−1 (b) ∪ σ−1 (C) ) = hm, uhσ−1 (a),σ−1 (b) | σ−1 (C)i i ≥ 0,

(23)

because hσ−1 (a), σ−1 (b) | σ−1 (C)i is a triplet of pairwise disjoint subsets of N and m ∈ ♦(N ).
The formula (23) also implies (22) because i ⊥⊥ j | K [m̃] means hm̃, uhi,j|Ki i = 0.
✷
Thus, the contraction transformation TS→s , where s ∈ S ⊆ N , can be interpreted as a
supermodularity-preserving projection and also viewed as a complementary transformation
to TM րN where M = (N \ S) ∪ s. Nevertheless, it does not preserve the extremality of a
supermodular function: follow Example 2 with m∗ = 2 · δ{a,b,c,d} + δ{a,b,c} + δ{a,b,d} + δ{a,c,d} ,
take S = {c, d}, s = c, and observe that TS→s (m∗ ) = (δ{a,b,c} + δ{a,c} ) + δ{a,b,c} , which is
not extreme.
22

8.3

Non-linear maximum-based projection

There is a non-linear supermodularity-preserving mapping from RP(N ) to RP(M ) , M ⊆ N .
Definition 11 Given M ⊆ N , the max-minor projection is a mapping
TmaxցM : RP(N ) → RP(M ) defined as follows:
TmaxցM :

m ∈ RP(N ) 7→ TmaxցM (m) ≡ r ∈ RP(M ) ,

where [TmaxցM (m)](S) = r(S) := max { m(S ∪ L) : L ⊆ N \ M }

for S ⊆ M . (24)

Given m ∈ RP(N ) the function r ≡ TmaxցM (m) will be called the max-minor of m for M .
The motivation for the terminology is clear: one can re-write (24) as follows:
[TmaxցM (m)](S) ≡ r(S) =

max

D,E⊆N \M, D∩E=∅

[T−D|E (m)](S)

for S ⊆ M ,

that is, r is a point-wise maximum on P(M ) of all minors of m. It also follows from this
interpretation that the max-minor projection can be viewed as complementary to the lifting
TM րN . Clearly, TmaxցM is not a linear mapping, but it preserves supermodularity.
Observation 11

If M ⊆ N and m ∈ ♦(N ) then TmaxցM (m) ∈ ♦(M ).

Proof. Denote r := TmaxցM (m). Given A, B ⊆ M , there exist A′ , B ′ ⊆ N \ M such that
r(A) = m(A ∪ A′ ) and r(B) = m(B ∪ B ′ ). Thus, we write using supermodularity of m,
r(A) + r(B) = m(A ∪ A′ ) + m(B ∪ B ′ )
≤ m( (A ∪ A′ ) ∪ (B ∪ B ′ ) ) + m( (A ∪ A′ ) ∩ (B ∪ B ′ ) )
= m( (A ∪ B) ∪ (A′ ∪ B ′ ) ) + m( (A ∩ B) ∪ (A′ ∩ B ′ ) )
≤

max m( (A ∪ B) ∪ L ) +

L⊆N \M

max m( (A ∩ B) ∪ L )

L⊆N \M

= r(A ∪ B) + r(A ∩ B) ,
because A′ ∪ B ′ ⊆ N \ M and A′ ∩ B ′ ⊆ N \ M .

✷

The above fact has been mentioned in more general context in [9, Theorem 2.7.6]. A
minimum-based analogue of the discussed transformation has been applied in the context
of submodular functions: it has been named “partial minimum” in [1] and utilized in the
definition of the concept of “expressibility” in [10].
The max-minor projection does not preserve quantitative equivalence and cannot be
interpreted as a transformation between ≈-equivalence classes. Follow Example 1 with
N = {a, b, c}, M = {a, b} and m0 = 2 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} . Then m0 ≈ m0 − mc⊆
despite TmaxցM (m0 ) = 2 · δ{a,b} + δa + δb 6≈ δ{a,b} = TmaxցM (m0 − mc⊆ ). Neither the
max-minor projection preserves extremality of a supermodular function. Follow Example 2
with N = {a, b, c, d}, m∗ = 2 · δ{a,b,c,d} + δ{a,b,c} + δ{a,b,d} + δ{a,c,d} and observe that its
max-minor projection 2 · δ{a,b,c} + δ{a,b} + δ{a,c} to M = {a, b, c} is not extreme.
23

9

Product-based composition and modular extensions

The topic of this section is a special product-based binary operation with set functions which
preserves both supermodularity and extremality. Two linear transformations, interpreted
as modular extensions of set functions, can be derived from that binary operation.

9.1

Product-based composition

Consider the cone ♦∗ (N ) of non-negative non-decreasing supermodular functions, which is
a pointed polyhedral cone. The next lemma is a slight generalization of [2, Proposition 4.3].
Lemma 7 Let N decompose into non-empty sets R and L, r ∈ RP(R) and l ∈ RP(L) .
(i) If both r ∈ ♦∗ (R) and l ∈ ♦∗ (L) then the function m ∈ RP(N ) defined by
m(S) := r(S ∩ R) · l(S ∩ L)

for any S ⊆ N ,

(25)

belongs to the cone ♦∗ (N ). Conversely, if m ∈ ♦∗ (N ) is non-zero and (25) holds with
non-negative r ∈ RP(R) and l ∈ RP(L) then r ∈ ♦∗ (R) and l ∈ ♦∗ (L).
(ii) The function m given by (25) generates an extreme ray of ♦∗ (N ) iff r generates an
extreme ray of ♦∗ (R) and l generates an the extreme ray of ♦∗ (L).
Proof. (i): in the non-trivial case of non-zero r and l one has r(R) > 0, l(L) > 0 and the
observation that m is non-negative and non-decreasing is easy. Consider ha, b|Ci ∈ E(N )
and distinguish three cases of its relation to R and L. If a ∈ R and b ∈ L then write
hm, uha,b|Ci i = m(a ∪ b ∪ C) − m(a ∪ C) − m(b ∪ C) + m(C)
= r(a ∪ (C ∩ R)) · l(b ∪ (C ∩ L)) − r(a ∪ (C ∩ R)) · l(C ∩ L)
− r(C ∩ R) · l(b ∪ (C ∩ L)) + r(C ∩ R) · l(C ∩ L)
= [ r(a ∪ (C ∩ R)) − r(C ∩ R) ] · [ l(b ∪ (C ∩ L)) − l(C ∩ L) ] ≥ 0 ,
because r and l are non-decreasing. If a, b ∈ R then write
hm, uha,b|Ci i = m(a ∪ b ∪ C) − m(a ∪ C) − m(b ∪ C) + m(C)
= r(a ∪ b ∪ (C ∩ R)) · l(C ∩ L) − r(a ∪ (C ∩ R)) · l(C ∩ L)
− r(b ∪ (C ∩ R)) · l(C ∩ L) + r(C ∩ R) · l(C ∩ L)
= l(C ∩ L) · hr, uha,b|C∩Ri i ≥ 0

since l is non-negative and r supermodular.

The case a, b ∈ L is analogous, just interchange R and L.
As concerns the converse claim in (i) note that m(N ) > 0 implies r(R) > 0 and l(L) > 0.
(25)

Because the function A ⊆ R 7→ m(A ∪ L) = r(A) · l(L) is non-decreasing with respect to
inclusion, the same holds for r. Given ha, b|Ci ∈ E(R) observe
(25)

l(L) · hr, uha,b|Ci i = hm, uha,b|C∪Li i ≥ 0

which implies that r is supermodular.
24

The arguments for l are analogous.
(ii): note that generators of extreme rays must be non-zero and m ∈ ♦∗ (N ) generates an
extreme ray if m = m1 + m2 for m1 , m2 ∈ ♦∗ (N ) implies that m1 = α · m and m2 = β · m
with α, β ≥ 0. Thus, the necessity of r being extreme follows from (i) because r = r 1 + r 2
for r 1 , r 2 ∈ ♦∗ (R) implies m = m1 +m2 , where mi is obtained from r i and l by (25), i = 1, 2.
Thus, m1 = α · m with α ≥ 0 implies r 1 = α · r for l(L) > 0 and similarly with r 2 . The
necessity of l generating an extreme ray of ♦∗ (L) is shown analogously.
As concerns the sufficiency assume that m given by (25) is written m = m1 + m2 with
non-zero m1 , m2 ∈ ♦∗ (N ). First, we show that non-negative r 1 , r 2 ∈ RP(R) exist such that
r 1 + r 2 = r & mi (S) = r i (S ∩ R) · l(S ∩ L),

for S ⊆ N , i = 1, 2.

(26)

Given A ⊆ R with r(A) = 0 we put r 1 (A) = r 2 (A) = 0, which works in the case of any
set S ⊆ N with S ∩ R = A because then m(S) = 0 and m1 (S) = m2 (S) = 0. Given
A ⊆ R with r(A) > 0 consider the functions B ⊆ L 7→ m1 (A ∪ B). This non-negative and
non-decreasing function is the minor of m1 with deleting of R \ A and extracting of A, and,
1
therefore, supermodular, by Observation 9. Thus, its r(A)
-multiple belongs to ♦∗ (L). Of
course, the same conclusion holds in case of B ⊆ L 7→ m2 (A ∪ B). Now, realize that
∀B ⊆ L

(25)

r(A) · l(B) = m(A ∪ B) = m1 (A ∪ B) + m2 (A ∪ B)
1
1
⇒ l(B) =
· m1 (A ∪ B) +
· m2 (A ∪ B) ,
r(A)
r(A)
{z
} |
{z
}
|
∈♦∗ (L)

∈♦∗ (L)

and the assumption that l generates an extreme ray of ♦∗ (L) implies the existence of
constants r 1 (A), r 2 (A) ≥ 0 such that mi (A ∪ B) = r i (A) · l(B) for B ⊆ L, i = 1, 2. Then
(25)

r(A) · l(L) = m(A ∪ L) = m1 (A ∪ L) + m2 (A ∪ L) = r 1 (A) · l(L) + r 2 (A) · l(L)
implies r(A) = r 1 (A) + r 2 (A) because l(L) > 0. Thus, this choice of r 1 (A) and r 2 (A),
ensures that (26) holds for S ⊆ N with S ∩ R = A.
The condition (26) says that non-zero m1 is obtained from non-negative r 1 and l by
(25). Hence, by the second observation in (i), r 1 ∈ ♦∗ (R). Analogously, r 2 ∈ ♦∗ (R) and the
assumption that r generates an extreme ray of ♦∗ (R) implies that r 1 = α · r and r 2 = β · r
with α, β ≥ 0. Hence, (26) and (25) imply the desired conclusion about m, m1 and m2 . ✷
To apply Lemma 7 realize what are the generators of extreme rays of ♦∗ (N ). They
break into three types, namely the constant function, singleton superset identifiers, and the
generators of extreme rays of the cone ♦ℓ (N ) of ℓ-standardized supermodular functions.
The composition with the constant function m∅⊆ is, in fact, the lifting transformation
discussed already in § 7.1. The next corollary is devoted to the composition of an extreme
ℓ-standardized function with a singleton subset identifier; it leads to a linear transformation
discussed later in § 9.2. The observation has already been mentioned in [2, Lemma 4.4].
25

Corollary 8

Assume |N | ≥ 2, x ∈ N and M := N \ x. Given r ∈ ♦ℓ (M ), let m′ ∈ RP(N )

be defined as follows:
′

m (S) :=



r(S ∩ M ) if x ∈ S,
0
otherwise,

for any S ⊆ N .

(27)

Then m′ ∈ ♦ℓ (N ) and, moreover, r is extreme in ♦ℓ (M ) iff m′ is extreme in ♦ℓ (N ).
Proof. Apply Lemma 7 with R = M , L = x and l = mx⊆ . Then m defined by (25) coincides
with m′ given by (27) and is evidently ℓ-standardized. The rest follows from Lemma 7. ✷
The product-based combination of two ℓ-standardized supermodular functions is treated
in another corollary, which is, basically, the result from [2, Proposition 4.3].
Corollary 9 Let N decompose into non-empty sets R and L. Assume that r ∈ ♦ℓ (R),
l ∈ ♦ℓ (L) and the function m ∈ RP(N ) is defined by (25). Then m ∈ ♦ℓ (N ), and, moreover,
m is extreme in ♦ℓ (N ) iff [ r is extreme in ♦ℓ (R) and l extreme in ♦ℓ (L) ].
Proof. This follows directly from Lemma 7, taking into account what was said above.

✷

Note that the product-based composition as a tool for generating “new” types of extreme
supermodular functions only applies in the case |N | ≥ 4; this is because non-zero extreme
ℓ-standardized supermodular functions exist if they are at least two variables. In the case
|N | = 4 the result of product-based composition is equivalent to the application of the
lower modular extension from § 9.2. However, in the case |N | ≥ 5 its application results in
non-trivial types of extreme supermodular functions.
The specialty of this operation is that, if applied to extreme supermodular functions with
zero-one table of scalar products (see Definition 2) it may result in an extreme supermodular
function whose table of scalar products has more than two distinct values. None of other
transformations discussed in this report has this property.

9.2

Lower modular extension

The extension of ℓ-standardized functions mentioned in Corollary 8 is a special case of the
following linear transformation.
Definition 12 Let M, N be sets of variables such that ∅ =
6 M ⊂ N . The lower modular
extension transformation Tℓ-mod : RP(M ) → RP(N ) is defined as follows:
Tℓ-mod : r ∈ RP(M ) 7→ Tℓ-mod (r) ≡ m ∈ RP(N ) , where

r(S ∩ M )
if (N \ M ) ⊆ S,
m(S) :=
r(S ∩ M ) − rℓ (S ∩ M ) otherwise,

26

for any S ⊆ N.

(28)

Observe that the difference r − rℓ ∈ RP(M ) is a modular function: specifically, (1) says
X
r − rℓ = r(∅) · m∅⊆ +
[r(i) − r(∅)] · mi⊆ ∈ L(M )
i∈M

and one can interpret r − rℓ as the lower modular part of r. This perhaps explains the
motivation for the term lower modular extension: one basically “copies” r to the “upper”
class of sets (N \ M ) ∪ P(M ) := { (N \ M ) ∪ L : L ⊆ M } and extends this copy of r by
the copies of its lower modular part “written” to all remaining “lower” classes R ∪ P(M ),
R ⊂ (N \M ). In particular, the minor of m = Tℓ-mod (r) with extracting of N \M is again r,
which means that the extraction minor projection from § 8.1 is a complementary operation
to Tℓ-mod . Note that Tℓ-mod maps linearly L(M ) to L(N ), specifically
α∅ · m∅⊆ +

X

αi · mi⊆ ∈ L(M )

Tℓ-mod

7−→

α∅ · m∅⊆ +

i∈M

X

αi · mi⊆ ∈ L(N )

for α∅ , αi ∈ R,

i∈M

where the pre-image is a function in RP(M ) while the image, given by the same formal
expression, is viewed as a function in RP(N ) . Hence, r 1 ≈ r 2 implies Tℓ-mod (r 1 ) ≈ Tℓ-mod (r 2 )
and the lower modular extension is a transformation between equivalence classes of ≈.
Without loss of generality, one can limit oneself to the case |N \M | = 1 because repeated
lower modular extension is equivalent to lower modular extension with a larger set N \ M .
Indeed, if N \M = {x1 , x2 } then one first applies Tℓ-mod with N \M = x1 to r and gets r ′ on
P(M ′ ) where M ′ = M ∪ x1 . Observe that the lower modular part of r ′ can be interpreted
as two copies of the lower modular part of r “written” to P(M ) and x1 ∪ P(M ). Therefore,
the application of Tℓ-mod with N \ M ′ = x2 to r ′ has then the same effect as the application
of Tℓ-mod to r with N \ M = {x1 , x2 }.
Observation 12

Assume |N | ≥ 2, x ∈ N and M := N \ x and r ∈ RP(M ) .

(i) One has m = Tℓ-mod (r) ∈ ♦(N ) iff r ∈ ♦(M ). The independency model induced by
Tℓ-mod (r) is then determined as follows: given ha, b|Ci ∈ E(N ) one has

 either x 6∈ (a ∪ b ∪ C) ,
a ⊥⊥ b | C [m] ⇔
or x ∈ {a, b} & rℓ ( (a ∪ b ∪ C) \ x) = rℓ (C) ,
(29)

or x ∈ C & a ⊥⊥ b | (C \ x) [r] .

(ii) The function r is extreme in ♦(M ) iff m = Tℓ-mod (r) is extreme in ♦(N ).

Proof. (i): Observation 9 implies the necessity of r = T|x (m) ∈ ♦(M ) for m ∈ ♦(N ). As
concerns the sufficiency realize that one can re-write (28) in the form

P
r(∅) + i∈S∩M
P[r(i) − r(∅)] + rℓ (S ∩ M ) if x ∈ S,
m(S) =
for S ⊆ N ,
r(∅) + i∈S∩M [r(i) − r(∅)]
if x 6∈ S,
P
which means m = l + m′ , where l = r(∅) · m∅⊆ + i∈M [r(i) − r(∅)] · mi⊆ ∈ L(N ) and

m′ = Tℓ-mod (rℓ ) is the “lower” zero extension of rℓ defined by (27) in Corollary 8. This
27

allows us to deduce (29): since mℓ ≈ m′ one has a ⊥⊥ b | C [m] iff a ⊥⊥ b | C [m′ ] for any
ha, b|Ci ∈ E(N ). Moreover, Corollary 8 says m′ ∈ ♦ℓ (N ), which implies m ∈ ♦(N ).
(ii): Corollary 2 says that the extremality in ♦(N ) reduces to the extremality in ♦ℓ (N ) and
Corollary 8 claims that rℓ is extreme in ♦ℓ (M ) iff its extension m′ is extreme in ♦ℓ (N ). ✷
Example 3 Take N = {a, b, c, d}, M = {a, b, c} and r̄ = δ{a,b,c} ∈ RP(M ) , which is extreme
in ♦(M ). As r̄ itself is ℓ-standardized, its lower modular extension m = δ{a,b,c,d} ∈ RP(N )
is also ℓ-standardized. Observation 12(ii) says m is extreme in ♦(N ). The extremality of
m also follows from Corollary 9 with R = {a, b}, L = {c, d} , r = δ{a,b} and l = δ{c,d} .
✷

9.3

Upper modular extension

One can combine the lower modular extension from § 9.2 with the reflection transformation
from § 6.2, which leads to the following concept.
Definition 13 Let M, N be sets of variables such that ∅ =
6 M ⊂ N . The upper modular
P(M
)
P(N
)
extension transformation Tu-mod : R
→R
is defined as follows:
Tu-mod : r ∈ RP(M ) 7→ Tu-mod (r) ≡ m ∈ RP(N ) , where

r(S)
if S ⊆ M ,
m(S) :=
r(S ∩ M ) − ru (S ∩ M )
otherwise,

for any S ⊆ N.

(30)

The difference r − ru ∈ RP(M ) is a modular function and can be interpreted as an upper
modular part of r. Thus, the term upper modular extension has similar motivation as the
term lower modular extension from § 9.2. The formula (30) can be interpreted as follows:
one “copies” r to P(M ) and then extends this copy of r by the copies of its upper modular
extension r − ru “written” to all remaining classes R ∪ P(M ), where ∅ =
6 R ⊆ N \ M . As
concerns the expression for r − ru , one has
(2)

r(S ∩ M ) − ru (S ∩ M ) =

X

r(M \ i) + (1 − |M \ S|) · r(M ) for any S ⊆ N .

i∈M \S

It follows from (30) that the restriction of m = Tu-mod (r) to P(M ) is again r; hence, the
deletion minor projection T−(N \M ) is a complementary operation to Tu-mod .
Because m∅⊆ , mj⊆ ∈ RP(M ) , for j ∈ M , are ascribed m∅⊆ , mj⊆ ∈ RP(N ) by Tu-mod , the
transformation maps linearly L(M ) to L(N ). This says r 1 ≈ r 2 ⇒ Tu-mod (r 1 ) ≈ Tu-mod (r 2 )
and the upper modular extension can be interpreted as a transformation of ≈-equivalence
classes. Without loss of generality, one can limit oneself to the case |N \ M | = 1 since
repeated upper modular extension is equivalent to upper modular extension with a larger
set N \M ; the arguments are analogous to those used in the case of lower modular extension.
The relation of Tu-mod and Tℓ-mod can be described as follows. The application of the
upper modular extension Tu-mod followed by the application of the reflection transformation
28

on RP(N ) (see § 6.2) has the same effect as the application of the reflection transformation on
RP(M ) followed by the application of the lower modular transformation Tℓ-mod . Indeed, this
observation follows from the above descriptions of both transformations in terms of “copies”
to classes R∪P(M ), R ⊆ N \M and the formula Tι (r−ru ) = Tι (r)−Tι (ru ) = Tι (r)−(Tι (r))ℓ ;
see the remark concluding § 6.2. An analogous statement holds with interchanged Tu-mod
and Tℓ-mod , that is, one has
∀ r ∈ RP(M )

Tι (Tu-mod (r)) = Tℓ-mod (Tι (r)) & Tι (Tℓ-mod (r)) = Tu-mod (Tι (r)) .

(31)

Owing to the relation of Tu-mod and Tℓ-mod the following observation can easily be derived
from Observation 12; a special case of it has been shown in [2, Lemma 4.5].
Observation 13

Assume |N | ≥ 2, x ∈ N and M := N \ x and r ∈ RP(M ) .

(i) One has m = Tu-mod (r) ∈ ♦(N ) iff r ∈ ♦(M ). The independency model induced by
Tu-mod (r) is then determined as follows: given ha, b|Ci ∈ E(N ) one has

 either x ∈ C ,
a ⊥⊥ b | C [m] ⇔
or x ∈ {a, b} & ru ( (a ∪ b ∪ C) \ x) = ru (C) ,
(32)

or x 6∈ (a ∪ b ∪ C) & a ⊥⊥ b | C [r] .

(ii) The function r is extreme in ♦(M ) iff m = Tu-mod (r) is extreme in ♦(N ).

Proof. (i): Observation 4(i) with M in place of N says r ∈ ♦(M ) iff r ◦ ι = Tι (r) ∈ ♦(M ).
(31)

The latter is equivalent to Tι (Tu-mod (r)) = Tℓ-mod (Tι (r)) ∈ ♦(N ) by Observation 12(i).
Observation 4(i) implies the latter is equivalent to Tu-mod (r) ∈ ♦(N ). To derive (32) denote
m′ := Tu-mod (ru ), observe that r ≈ ru ⇒ m = Tu-mod (r) ≈ Tu-mod (ru ) = m′ ⇒ m ∼ m′
and realize that m′ vanishes outside P(M ) and coincides with ru within P(M ).
(ii): the arguments are analogous to the case of (i): one applies Observation 4(ii) with M
in place of N , then Observation 12(ii), (31) and, finally, Observation 4(ii) with N .

✷

Example 4 Take N = {a, b, c}, M = {a, b} and r̂ = δ{a,b} ∈ RP(M ) , which is extreme in
♦(M ). One has r̂ − r̂u = δ{a,b} − δ∅ and the application of (30) gives
m = Tu-mod (r̂) = δ{a,b} + δ{a,b,c} − δc

and

mℓ = 2 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} .

Note that r̂u = δ∅ ∈ RP(M ) and Tu-mod (r̂u ) = δ∅ ∈ RP(N ) . Indeed, since r ≈ ru = δ∅ one has
Tu-mod (r) ≈ Tu-mod (δ∅ ) and their ℓ-standardizations coincide: mℓ = (δ∅ )ℓ . This illustrates
that Tu-mod for u-standardized functions is just the “upper” zero extension.

10

✷

Replications

In this section we discuss two other linear mappings to a higher-dimensional space which,
under certain non-restrictive conditions, preserve both supermodularity and extremality.
29

They cannot be interpreted directly as mappings between ≈-equivalence classes; however,
after minor modification, they can be viewed as mappings between ≈-equivalence classes of
extreme supermodular functions.

10.1

Lower replication

Definition 14 Let M, N be sets of variables such that z ∈ M exists with L := M \ z ⊂ N .
The lower replication transformation T↓↓ : RP(M ) → RP(N ) is defined as follows:
T↓↓ : r ∈ RP(M ) 7→ T↓↓ (r) ≡ m ∈ RP(N ) , where

r(z ∪ (S ∩ L))
if (N \ L) ⊆ S,
m(S) =
r(S ∩ L)
if N \ (L ∪ S) 6= ∅,

for any S ⊆ N .

(33)

To explain the motivation for the terminology “decompose” virtually r ∈ RP(M ) into its
“lower” part, which is its restriction to P(L), and its “upper” part, which is its restriction
to the class of sets z ∪ P(L) := {z ∪ R : R ⊆ L}. In the non-trivial case |N \ L| ≥ 2, the
function m = T↓↓ (r) is obtained by copying once the “upper” part of r to (N \ L) ∪ P(L)
and by multiple copying its “lower” part (= the replication) to each R ∪ P(L), R ⊂ N \ L.
A simple observation is that, without loss of generality, one can limit oneself to the case
|N \L| = 2 because repeated lower replication is equivalent to lower replication with a larger
set N \ L. Indeed, if N \ L = {z1 , z2 , z3 } then one first applies T↓↓ with N \ L = {z1 , z2 }
and gets r ′ = T↓↓ (r) on P(L ∪ z1 ∪ z2 ). The choice z ′ = z2 , L′ = L ∪ z1 and N \ L′ = {z2 , z3 }
has then the same effect as the application of T↓↓ to r with N \ L = {z1 , z2 , z3 }.
The lower replication can be interpreted as a simultaneous inversion of some “coinciding”
projections. Specifically, if N \ L = {x, y} and m = T↓↓ (r) then r can be “obtained” from
m in three ways: taking the extraction minor T|x (m) and re-naming y to z, taking the
extraction minor T|y (m) and re-naming x to z, and taking the contraction T{x,y}→x (m)
and re-naming x to z, respectively by renaming y to z in T{x,y}→y (m). The supermodular
extremality is not preserved by these projections, but, it is preserved if they “coincide”.
Observation 14
Assume r ∈

Let N, M be sets of variables with z ∈ M , L := M \z and N \L = {x, y}.

RP(M ) .

(i) One has m = T↓↓ (r) ∈ ♦(N ) iff [ r ∈ ♦(M ) and r(z) ≥ r(∅) ]. The independency
model induced by T↓↓ (r) is then determined as follows: given ha, b|Ci ∈ E(N ) one has
a ⊥⊥ b | C [m] in the following cases:
a ∩ L ⊥⊥ b ∩ L | C ∩ L [r] in case {x, y} \ (a ∪ b ∪ C) 6= ∅ ,
a ⊥⊥ b | z ∪ (C ∩ L) [r] in case {x, y} ⊆ C,
z ⊥⊥ {a, b} ∩ L | C ∩ L [r] in case |{x, y} ∩ C| = 1 & {x, y} ⊆ a ∪ b ∪ C,
r(z ∪ C) = r(C) in case {x, y} = {a, b} .
30

(ii) If r ∈ ♦ℓ (M ) then T↓↓ (r) ∈ ♦ℓ (N ). A function r ∈ ♦ℓ (M ) is extreme in ♦(M ) iff
T↓↓ (r) is extreme in ♦(N ).
(iii) If r is extreme in ♦(M ) and r(z) = r(0) then T↓↓ (r) is extreme in ♦(N ) and, moreover,
T↓↓ (r) ≈ T↓↓ (rℓ ). Conversely, if T↓↓ (r) is extreme in ♦(N ) then either the above case
occurs or one has r(z) > r(∅), r ∈ L(M ) and T↓↓ (r) ≈ [r(z) − r(∅)] · m{x,y}⊆ .
Proof. (i): the necessity of r ∈ ♦(M ) is easy for r can be interpreted as the minor of m
obtained by extracting of x and renaming y to z (Observation 9). Owing to supermodularity
0 ≤ hm, uhx,y|∅i i = m(x ∪ y) − m(x) − m(y) + m(∅) = r(z) − r(∅) − r(∅) + r(∅) = r(z) − r(∅) .
As concerns the sufficiency, the first step is to realize that r(z) ≥ r(∅) and supermodularity
of r allows one to observe by induction on |C| that r(z ∪ C) ≥ r(C) for any C ⊆ L. The
second step is to consider ha, b|Ci ∈ E(N ) and distinguish the cases of its relation to {x, y}.
If {x, y} \ (a ∪ b ∪ C) 6= ∅ then write using (33):
hm, uha,b|Ci i = m(a ∪ b ∪ C) − m(a ∪ C) − m(b ∪ C) + m(C)
= r( (a ∪ b ∪ C) ∩ L ) − r( (a ∪ C) ∩ L ) − r( (b ∪ C) ∩ L ) + r(C ∩ L)
= hr, uha∩L,b∩L | C∩Li i ≥ 0 because r ∈ ♦(M ).
If {x, y} ⊆ a ∪ b ∪ C then, depending on |{x, y} ∩ C|, three subcases can occur. In the
subcase x, y ∈ C one gets hm, uha,b|Ci i = hr, uha,b|C̃∪zi i ≥ 0, where C̃ = C \ {x, y}. If x = a
and y ∈ C then denote C ′ = C \ y and write
hm, uha,b|Ci i = m(x ∪ b ∪ C) − m(x ∪ C) − m(b ∪ C) + m(C)
= r(z ∪ b ∪ C ′ ) − r(z ∪ C ′ ) − r(b ∪ C ′ ) + r(C ′ ) = hr, uhz,b|C ′ i i ≥ 0 .
An analogous reasoning works for other variants of |{x, y} ∩ C| = 1. Finally, in the last
subcase {x, y} = {a, b} write
hm, uha,b|Ci i = m(x ∪ y ∪ C) − m(x ∪ C) − m(y ∪ C) + m(C)
= r(z ∪ C ) − r(C) − r(C) + r(C) = r(z ∪ C ) − r(C) ≥ 0 ,
by the first step. Thus, m ∈ ♦(N ) has been verified. The form of the independency model
induced by m follows from the proof, which breaks into the above mentioned cases.
(ii): the fact that T↓↓ maps ℓ-standardized functions to ℓ-standardized functions is evident;
thus, the first claim follows from (i). As concerns the second claim, by Corollary 2, it is
enough to show that r generates an extreme ray of ♦ℓ (M ) iff T↓↓ (r) generates an extreme
ray of ♦ℓ (N ). For the necessity of the latter realize that any m ∈ ♦ℓ (N ) is non-decreasing,
for which reason
{m ∈ ♦ℓ (N ) : m(x ∪ y) = 0

& m(x ∪ R) = m(R) = m(y ∪ R) for any R ⊆ L }
31

is a face of ♦ℓ (N ). One can easily observe that this face is nothing but the image of ♦ℓ (M )
by T↓↓ . Thus, given r ∈ RP(M ) generating an extreme ray of ♦ℓ (M ), if m = T↓↓ (r) is an
inner point of the segment between m1 and m2 in ♦ℓ (N ) then, since m belongs to that face,
m1 , m2 do so. In particular, there are r 1 , r 2 ∈ ♦ℓ (M ) such that T↓↓ (r i ) = mi for i = 1, 2
and, by linearity of the inversion of T↓↓ , r is an inner point of the segment between r 1
and r 2 . Thus, r i are non-negative multiples of r and mi must be non-negative multiples
of m; the fact that m = T↓↓ (r) generates an extreme ray of ♦ℓ (N ) has been verified. The
sufficiency of the latter condition for r generating an extreme ray of ♦ℓ (M ) can be shown
analogously.
(iii): as concerns the first claim, realize that in case r(z) = r(∅) the formula (1) implies
that r − rℓ is a linear combination of m∅⊆ and mi⊆ for i ∈ L. Since these functions
are mapped by T↓↓ to the functions of the same form on P(N ), T↓↓ (r) − T↓↓ (rℓ ) is a linear
combination of these, T↓↓ (r) ≈ T↓↓ (rℓ ) and the first claim follows from (ii) using Corollary 2.
As concerns the converse claim, if r(z) = r(∅), use the same reasoning and the converse
implication in (ii). In case α := r(z) − r(∅) 6= 0 write r = α · mz⊆ + r ′ , where r ′ ≈ r satisfies
(i)

r ′ (z) = r ′ (∅). Observe T↓↓ (r) ∈ ♦(N ) ⇒ r ∈ ♦(M ) and, necessarily α = r(z) − r(∅) > 0.
(i)

Then r ∈ ♦(M ) ⇔ r ′ ∈ ♦(M ) ⇒ T↓↓ (r ′ ) ∈ ♦(N ). As T↓↓ maps mz⊆ to m{x,y}⊆ one has
T↓↓ (r) = α·m{x,y}⊆ +T↓↓ (r ′ ), where m′ := T↓↓ (r ′ ) is not a non-zero multiple of m{x,y}⊆ since
m′ ({x, y}) = m′ (∅). Thus, provided T↓↓ (r) is extreme in ♦(N ), the function T↓↓ (r ′ ) = m′
must be modular. Because mx⊆ and my⊆ are not in the image of T↓↓ , this means m′ is a
linear combination of m∅⊆ and mi⊆ for i ∈ L. Hence, the same holds for r ′ on P(M ) and r
must belong to L(M ). Since T↓↓ (r ′ ) ∈ L(N ) one has T↓↓ (r) ≈ α · m{x,y}⊆ .
✷
The following consequence allows one to interpret the lower replication as a mapping
between ≈-equivalence classes of extreme supermodular functions.
Corollary 10

In the situation from Observation 14, if r is extreme in ♦(M ) then

T↓↓ (r) ≈ T↓↓ (rℓ ) ⇔ T↓↓ (r) is extreme in ♦(N ) ⇔ r(z) = r(∅) .
Proof. Corollary 2 implies that the extremality of a function and of its ℓ-standardized
version are equivalent. Since rℓ ≈ r is extreme in ♦(M ), by Observation 14(ii), T↓↓ (rℓ ) is
extreme in ♦(N ). Hence, T↓↓ (r) ≈ T↓↓ (rℓ ) implies the extremality of T↓↓ (r) in ♦(N ). If
T↓↓ (r) is extreme in ♦(N ) then, by Observation 14(i), r(z) ≥ r(∅). The case r(z) − r(∅) > 0
cannot occur because then, by Observation 14(iii), r ∈ L(M ), which is a contradiction with
the assumption that r is extreme in ♦(M ). Therefore, r(z) = r(∅), which implies that
T↓↓ (r) ≈ T↓↓ (rℓ ), again by Observation 14(iii). The equivalence of the extremality of T↓↓ (r)
in ♦(N ) with r(z) = r(∅) follows analogously from Observation 14(iii).
✷
To summarize: any extreme supermodular function r on P(M ) produces, through the
lower replication, an extreme supermodular function on P(N ). Of course, T↓↓ (r) itself need
32

not be supermodular and, even if supermodular, it need not be extreme in ♦(N ). However,
one can always take rℓ in place of r and, by Observation 14(ii), T↓↓ (rℓ ) is ensured to be
extreme in ♦(N ). Moreover, by Corollary 10, if r ≈ r ′ ∈ ♦(M ) such that T↓↓ (r ′ ) is extreme
in ♦(N ) then T↓↓ (r ′ ) ≈ T↓↓ (rℓ ). Thus, the ≈-equivalence class of extreme functions in ♦(N )
ascribed to the ≈-equivalence class of r is uniquely determined!
The technical condition r(z) = r(∅), under which T↓↓ (r) is guaranteed to be extreme
(see Corollary 10), is not restrictive because, without loss of generality, one can limit oneself
to the ℓ-standardized framework.
Example 5 Consider N = {a, b, c, d}, M = {a, b, c} and z = c, that is, L = {a, b}. Take
r = 2 · δ{a,b,c} + δ{a,b} + δ{a,c} + δ{b,c} ∈ ♦ℓ (M ). Then the application of (33) gives
m = T↓↓ (r) = 2 · δ{a,b,c,d} + δ{a,b,c} + δ{a,b,d} + δ{a,c,d} + δ{b,c,d} + δ{a,b} , which is,
by Observation 14(ii), an extreme ℓ-standardized supermodular function on P(N ).

10.2

✷

Upper replication

The lower replication from § 10.1 can be combined with the reflection transformation from
§ 6.2, which leads to the following concept.
Definition 15 Let M, N be sets of variables such that z ∈ M exists with L := M \ z ⊂ N .
The upper replication transformation T↑↑ : RP(M ) → RP(N ) is defined as follows:
T↑↑ : r ∈ RP(M ) 7→ T↑↑ (r) ≡ m ∈ RP(N ) , where

r(z ∪ (S ∩ L))
if S \ L 6= ∅,
m(S) =
r(S)
if S ⊆ L,

for any S ⊆ N .

(34)

It can be derived easily from the definition that the application of the upper replication
T↑↑ followed by the application of the reflection transformation Tι on RP(N ) (see § 6.2) has
the same effect as the application of Tι on RP(M ) followed by the application of the lower
replication T↓↓ . The roles of T↑↑ and T↓↓ can be interchanged here:
∀ r ∈ RP(M )

Tι (T↑↑ (r)) = T↓↓ (Tι (r)) & Tι (T↓↓ (r)) = T↑↑ (Tι (r)) .

(35)

The motivation for the terminology is similar as in the case of lower replication. In the
non-trivial case |N \ L| ≥ 2, if r ∈ RP(M ) is virtually “decomposed” into its “lower” part
T−z (r) and its “upper” part T|z (r) then the function m = T↑↑ (r) is obtained by copying
once the “lower” part of r to P(L) and by (multiple) replication of its “upper” part to each
R ∪ P(L) where ∅ =
6 R ⊆ N \ L.
Without loss of generality, one can limit oneself to the case |N \ L| = 2 because repeated
upper replication is equivalent to upper replication with a larger set N \ L; the justification
33

is analogous as in the case of lower replication. The upper replication can also be interpreted
as a simultaneous inversion of certain “coinciding” projections. Indeed, if N \ L = {x, y}
and m = T↑↑ (r) then r can be reconstructed from m in three ways: from the deletion minor
T−x (m) by re-naming y to z, from the deletion minor T−y (m) by re-naming x to z, and
from the contraction T{x,y}→x (m) by re-naming x to z.
Observation 15 Let N, M be sets of variables with z ∈ M , L := M \z and N \L = {x, y}.
Assume r ∈ RP(M ) .
(i) One has m = T↑↑ (r) ∈ ♦(N ) iff [ r ∈ ♦(M ) and r(L) ≥ r(M ) ]. The independency
model induced by T↑↑ (r) is then determined as follows: given ha, b|Ci ∈ E(N ) one has
a ⊥⊥ b | C [m] in the following cases
a ∩ L ⊥⊥ b ∩ L | z ∪ (C ∩ L) [r] in case {x, y} ∩ C 6= ∅ ,
a ⊥⊥ b | C [r] in case (a ∪ b ∪ C) ⊆ L,
z ⊥⊥ {a, b} ∩ L | C [r] in case |{x, y} ∩ {a, b}| = 1 & {x, y} ∩ C = ∅,
r(z ∪ C) = r(C) in case {x, y} = {a, b} .
(ii) If r ∈ ♦u (M ) then T↑↑ (r) ∈ ♦u (N ). A function r ∈ ♦u (M ) is extreme in ♦(M ) iff
T↑↑ (r) is extreme in ♦(N ).
(iii) If r is extreme in ♦(M ) and r(L) = r(M ) then T↑↑ (r) is extreme in ♦(N ) and,
moreover, T↑↑ (r) ≈ T↑↑ (ru ). Conversely, if T↑↑ (r) is extreme in ♦(N ) then either the
above case occurs or one has r(L) > r(M ), r ∈ L(M ) and T↑↑ (r) ≈ [r(L) − r(M )] · v,
where v(T ) := δ(T ⊆ L) for T ⊆ N , denotes the identifier of subsets of L.
Proof. (i): Denote r ′ := Tι (r), apply Observation 4(i) and Observation 14(i) which say
(35)

m = T↑↑ (r) ∈ ♦(N ) ⇔ T↓↓ (r ′ ) = T↓↓ (Tι (r)) = Tι (T↑↑ (r)) ∈ ♦(N )
⇔ [ r ′ ∈ ♦(M ) & r ′ (z) ≥ r ′ (∅) ] ⇔ [ r ∈ ♦(M ) & r(L) ≥ r(z ∪ L) ] .
The form of the induced model also follows from combined Observations 4(i) and 14(i).
(ii): realize that r ′ := Tι (r) is ℓ-standardized iff r is u-standardized; thus, one can use the
same reasoning procedure and combine Observation 4(i)(ii) with Observation 14(ii).
(iii): again, combine Observation 4(ii) with (35) and Observation 14(iii); one also needs to
realize that the reflection Tι transforms m{x,y}⊆ to the identifier v of subsets of L.
Analogously, one can verify the following fact.
Corollary 11

In the situation from Observation 15, if r is extreme in ♦(M ) then

T↑↑ (r) ≈ T↑↑ (ru ) ⇔ T↑↑ (r) is extreme in ♦(N ) ⇔ r(z ∪ L) = r(L) .
34

✷

Proof. Combine Observation 4(ii), (35) and Corollary 10.

✷

Thus, the upper replication also allows one to produce an extreme supermodular function
on P(N ) on basis of any given extreme supermodular function r on P(M ). The point is
that one can always take ru and T↑↑ (ru ) is then extreme in ♦(N ), by Observation 15(ii).
On the top of that, by Corollary 11, if r ≈ r ′ ∈ ♦(M ) such that T↑↑ (r ′ ) is extreme in ♦(N )
then T↑↑ (r ′ ) ≈ T↑↑ (ru ). Thus, T↑↑ establishes a mapping between ≈-equivalence classes of
extreme supermodular functions.
Example 6 Consider N = {a, b, c, d}, M = {b, c, d} and z = b, that is, L = {c, d}.
Take r = δ{b,c,d} + δ{b,c} , which is an extreme supermodular function on P(M ). Then
ru = δd + δ∅ ∈ RP(M ) . The application of (34) gives m = T↑↑ (ru ) = δd + δ∅ ∈ RP(N ) , which
is by Observation 15(ii), an extreme u-standardized supermodular function on P(N ). Its
ℓ-standardized version is then
mu = 2 · δ{a,b,c,d} + 2 · δ{a,b,c} + δ{a,b,d} + δ{a,c,d} + δ{b,c,d} + δ{a,b} + δ{a,c} + δ{b,c} ,
which is an extreme ℓ-standardized supermodular function.

✷

References
[1] F. Bach. Convex analysis and optimization with submodular functions: a tutorial. A
manuscript from November 2010, available at arXiv:1010.4207v2 .
[2] T. Kashimura, T. Sei, A. Takemura, K. Tanaka. Cones of elementary imsets and supermodular functions: a review and some new results. In Proceedings of the 2nd CRESTSBM International Conference Harmony of Gröbner Bases and the Modern Industrial
Society, World Scientific 2012, pp. 117-152.
[3] J. Kuipers, D. Vermeulen, M. Voorneveld. A generalization of the Shapley-Ichiishi
result. International Journal of Game Theory 39 (2010) 585-602.
[4] J. Rosenmüller, H.G. Weidner. Extreme convex set functions with finite carrier: general
theory. Discrete Mathematics 10 (1974) 342-382.
[5] L.S. Shapley. Cores of convex games. International Journal of Game Theory 1
(1971/72) 11-26.
[6] M. Studený, R.R. Bouckaert, T. Kočka. Extreme supermodular set functions over five
variables. Research report n. 1977, Institute of Information Theory and Automation,
Prague, January 2000.
[7] M. Studený. Probabilistic Conditional Independence Structures. Springer-Verlag 2005.
35

[8] M. Studený, T. Kroupa. Core-based criterion for extreme supermodular functions.
Discrete Applied Mathematics 206 (2016) 122-151.
[9] D.M. Topkis. Supermodularity and Complementarity. Princeton University Press 1998.
[10] S. Živný, D.A. Cohen, P.G. Jeavons. The expressive power of binary submodular functions. Discrete Applied Mathematics 157 (2009) 3347-3358.

A

Facts on faces

Definition 16 Consider the linear space RP(N ) ; let K ⊆ RP(N ) be a convex cone.
The cone K is called pointed if K ∩ (−K) = {0}.
A valid inequality for K is an inequality (for vectors m ∈ RP(N ) ) of the form
k ≤ hm, vi

where v ∈ RP(N ) and k ∈ R are such that K ⊆ {m ∈ RP(N ) : k ≤ hm, vi }.

A face of K is its subset F ⊆ K of the form
F = {m ∈ K : k = hm, vi }

where v ∈ RP(N ) and k ∈ R define a valid inequality for K.

The dimension of a face F is the dimension of its affine hull.
The relative interior of a face F is
[
relint (F ) := F \
{L : L is a face of K such that L ⊂ F } .

Observation 16 Every non-empty face F of a convex cone K is defined by an inequality
of the form 0 ≤ hm, vi. If an inner point of a segment in K belongs a face F (of K) then
the whole segment belongs to F .
Proof. Indeed, we know that m0 := 0 ∈ K and, thus, k ≤ hm0 , vi = 0. Assume for a
contradiction k < 0; the non-emptiness of F then implies the existence of y ∈ F ⊆ K with
k = hy, vi. Since K is a cone, x = 2·y ∈ K and k > 2·k = hx, vi for which reason k ≤ hm, vi
does not hold for m = x ∈ K, which is a contradiction.
To show the second statement, assume m1 , m2 ∈ K such that α·m1 +(1−α)·m2 ∈ F for
some α ∈ (0, 1). That means, by linearity of scalar product, 0 = α·hm1 , vi+(1−α)·hm2 , vi.
Since the respective inequality is valid for K we know 0 ≤ hm1 , vi and 0 ≤ hm2 , vi, which
together with the equality forces hm1 , vi = 0 = hm2 , vi, that is, m1 , m2 ∈ F .

✷

Basic facts on the face lattice
The class of non-empty faces of a polyhedral cone K ⊆ RP(N ) , that is, of a cone K defined
by means of a finite number of inequalities of the type 0 ≤ hm, v i i with v i ∈ RP(N ) , forms a
finite lattice relative to the inclusion order ⊆. This face lattice has the following properties.
• It is a graded lattice in which the dimension of a face is its grade in the lattice.
36

• The one of the lattice, that is, the largest element (= face) is the whole cone K, with
the maximal dimension dim(K).
• The zero of the lattice, that is, the smallest element (= face) is the linear subspace
L = K ∩ (−K), with the minimal dimension dim(L). In case of a pointed cone K the
dimension of L is 0.
In case K 6= L we, moreover, distinguish atoms and co-atoms of the face lattice.
• The atoms of the lattice are the upper neighbors of the zero in the lattice. This is such
a face F that the only proper sub-face G ⊂ F is the linear space G = L ≡ K ∩ (−K).
Since the face lattice is graded, an equivalent characterization is that it is a face of
the dimension dim(L) + 1. In case of a pointed cone K it a face of the dimension
1, that is, an extreme ray of K. An equivalent definition of an extreme ray is as
follows. A ray R = {λ · m : λ ≥ 0}, m ∈ K is extreme if every segment in K whose
inner point belongs to R must whole belong to R; formally: for every m1 , m2 ∈ K, if
[α · m1 + (1 − α) · m2 = m for α ∈ (0, 1)] then [mi = λi · m with λi ≥ 0, i = 1, 2].
• The co-atoms of the lattice are the lower neighbors of the one in the lattice. This
is such a face F that the only proper super-face G ⊃ F is the whole cone G = K.
Since the face lattice is graded, an equivalent characterization is that it is a face of the
dimension dim(K)− 1. Such faces are called facets. Since the face lattice is co-atomic,
that is, every element is an infimum of (a set of) co-atoms, we know that every face
F is the intersection of facets (containing F ). Of course, in case of the largest face
F = K (= the one of the lattice) it is the intersection of the empty system of facets.
In case K is a polyhedral cone, that is, defined by a list of linear inequalities
K = {m ∈ RP(N ) : 0 ≤ hm, v i i } for v 1 , . . . , v t ∈ RP(N ) \ {0}, t ≥ 1,
one knows that the facets of K are determined by those inequalities. More precisely, facets
of K are given by just those inequalities 0 ≤ hm, v i i that are not redundant, that is, not
derivable from the others (by a conic combination of inequalities).

37

