Extending submodular functions from a sublattice

Question

This came about when I was studying the connection between matroids and strong
greedoids, but it has broken through into a subject I am not particularly
familiar with: submodular functions on lattices.
Let $L$ be a finite lattice (in the sense of combinatorics).
Let $mathbb{N}=left{  0,1,2,ldotsright}  $. A function $f:Lto
mathbb{N}$ is said to be

submodular if it satisfies $fleft(  aright)  +fleft(  bright)  geq
fleft(  awedge bright)  +fleft(  avee bright)  $ for all $a,bin L$.

isotone if it satisfies $fleft(  aright)  leq fleft(  bright)  $
whenever $a,bin L$ satisfy $aleq b$.

1-continuous if it satisfies $fleft(  bright)  -fleft(  aright)
inleft{  0,1right}  $ whenever $a,bin L$ satisfy $alessdot b$ (that is,
$a<b$ but there exists no $cin L$ satisfying $a<c<b$).

Note that the first two of these notions are standard, while the third is mine.
Now, assume that $L$ is the Boolean lattice $2^{E}$ of a finite set $E$ (so
that the order relation $leq$ on $L$ is the relation $subseteq$ on $2^{E}$).
Thus, the 1-continuous isotone submodular functions $f:Ltomathbb{N}$
satisfying $fleft(  varnothingright)  =0$ are precisely the rank functions
of matroids on the ground set $E$. If we drop the "1-continuous", then we obtain the rank functions of
polymatroids instead.
Note that "$alessdot b$" is equivalent to "$a subseteq b$ and $left|b setminus a right| = 1$"
for any $a, b in L = 2^E$.
Let $M$ be a sublattice of $L$, by which I mean a subset of $L$ that is a
lattice when equipped with the partial order it inherits from $L$ and that has
the same $0$, $1$, $wedge$ and $vee$ as $L$. (This may or may not be some
people's definition of a sublattice.) Let $g:Mtomathbb{N}$ be a
function. An extension of $g$ to $L$ will mean a function
$f:Ltomathbb{N}$ such that $fmid_{M}=g$.

Theorem 1. If $g$ is an isotone submodular function on $M$, then there
exists an isotone submodular extension of $g$ to $L$.

This theorem is (a particular case of) Lemma 5.1 in Donald M. Topkis,
Minimizing a Submodular Function on a Lattice, Operations Research 26,
No. 2 (Mar. - Apr., 1978), pp. 305--321.
The proof defines the extension $f:Ltomathbb{N}$ of $g$ to $L$ by
setting
begin{align}
fleft(  yright)  =minleft{  gleft(  xright)   mid xin Ltext{
satisfying }xgeq yright}
end{align}
for all $yin L$. It is easy to check that this extension $f$ is indeed isotone and
submodular. Note that $L$ could be any finite lattice here, not necessarily a Boolean one.
My question is: how well do other properties extend from $M$ to $L$ ? The
specific question I am most interested in is:

Question 2. If $g$ is a 1-continuous isotone submodular function on $M$,
then does there exist a 1-continuous isotone submodular extension of $g$ to
$L$ ?

(Here, $L$ is still supposed to be Boolean.) A positive answer to Question 2
(specifically, in the case when $M$ is the lattice of order ideals of a
certain poset structure on $E$) would yield a neat (if not quite one-to-one)
correspondence between matroids and strong
greedoids that I believe could help
understand the latter. (I could elaborate if there is interest.) Note that
Topkis's above construction of $f$ does not produce a 1-continuous $f$ even if
it is applied to a 1-continuous $g$.
Having asked Question 2, we can vary the assumptions and get curious:

Question 3. If Question 2 has a positive answer, how far does it
generalize? For example, can we replace the Boolean lattice $L$ by an
arbitrary geometric lattice? ranked distributive lattice? ranked lattice?

Note that we cannot get rid of the "ranked" condition completely; e.g., the
rank function on the long chain of the pentagon lattice $N_{5}$ is a
1-continuous isotone submodular function, but has no 1-continuous extension to
the whole $N_{5}$.
Curiosity also suggests a different question:

Question 4. If $g$ is merely submodular (but not necessarily 1-continuous
or isotone), then does there exist a submodular extension of $g$ to $L$ ?

Geva Yashfe · Answer

The answer to Q2 is positive. A consequence is the answer to Q3 for $L$ any finite distributive lattice, by Birkhoff's theorem (which embeds such a lattice in a boolean lattice in such a way that a maximal chain between elements is mapped to such a maximal chain in the boolean lattice, so the proof of $1$-continuity goes through). It might be possible to extend to infinite distributive complemented lattices (using Stone's representation theorem), I'm not sure.
The case of a geometric lattice should be true and not be much harder. I don't know about finite modular lattices.
In any case, I hope there is a shorter, more conceptual proof.
Proof:
We will regard $M$ as a collection of sets closed under union and intersection. The strategy will be to gradually extend it (along with the function $r$) by steps of the following two types:

If some nonempty set $A$ is inclusion-minimal in $M$, add all its subsets to $M$, and extend $M$ to the sublattice of $L$ this generates.
If all inclusion-minimal subsets in $M$ are singletons (i.e. ${x}$ for some $xin E$,) find some $Sin M$ which is not a union of singletons in $M$, and extend $M$ by $S setminus T$ for $T = {xin Emid {x}in M, xin S}$ the unique maximal union of singletons in $M$ which $S$ covers. ($S$ is chosen to satisfy a certain condition, see below.)

Steps of type 1: Consider all the atoms of $M$ - that is, the elements covering $0$. Each of these is some subset $A$ of $E$, and we extend $r$ to the minimal sublattice generated by $M$ and the singletons contained in $A$ by setting the elements of $A$ to be parallel (each of rank $r(A)$). Here "parallel" is in the matroid-theoretic sense. It means that for any set $S$ in the sublattice generated by $M$ and ${{a}mid ain A}$,
$$r(S) = begin{cases}r(S) & Scap A=emptyset \ r(Scup A) & mathrm{otherwise}.end{cases}$$
In other words, any element of $A$ spans all the rest, so the influence on the rank of adding one of them to a set is the same as adding all $A$.
After enough such steps have been performed, every atom of $M$ is a singleton.
Steps of type 2: Take the union $U$ of all atoms of $M$, and denote
$$M_x = bigcap_{xin S in M} S$$
for each $x in E setminus U$. The family ${M_x}_{xin E setminus U}$ has a minimal nonzero element $M_z$.
Since $M_z$ does not cover $0$ in $M$ (or it would be an atom, hence contained in $U$,) it covers some unique $T=Ucap M_z$ in $2^U$ (on which we already have a matroid structure). Denote $A = M_z setminus T$, and note that if $A$ intersects an element of $M$ nontrivially it is contained in it (else $Acap S ni y$ but $Acap S notni y'$ for some $y,y' in M_z$ and some subset $Sin M$, but then $M_y subsetneq M_z$ contradicts minimality). Hence, without loss of generality, we can think of $A$ as a singleton (and later set all its elements parallel to each other). What remains is to extend the rank function to the lattice generated by $M$ and $A$.
If $r(M_z) - r(T) = 0,$ just make each element of $A$ a loop, i.e. set the rank of $A$ to $0$. Otherwise, $r(M_z) - r(T) = 1$. For each $W in M$, define the rank of $Acup W$ to be
$$begin{cases}
r(W)+1 & Tnotsubset overline{W} \
r(W cup (Tcup A)) & T subset overline{W},
end{cases}$$
where $overline{W}$ is the closure, i.e. $Tsubsetoverline{W}$ iff $r(W)=r(Wcup T)$ (note that in the second case, the rank is already defined, since $W, (Tcup A)$ are both in $M$). This is still submodular, isotone, and continuous, and extends the rank function to the sublattice generated by $M$ and $A$. Let's verify this:

Edit: The previous version of the proof had a bug: I considered only $W subset U$ and not general $Win M$. So there is more computation to be done. I suspect much of this can be shortened.
The most unfortunate part is that this error makes the previous explanation (based on modular filters) invalid. This was more conceptual and much shorter.

Submodularity: let $W_1,W_2 in M$. If $T subset overline{W_1},overline{W_2}$ then we have
begin{align}
& r(W_1 cup A) + r(W_2 cup A) \
&= r(W_1 cup T cup A) + r(W_2 cup Tcup A) \
&ge r(W_1 cup W_2 cup T cup A) + r((W_1 cap W_2)cup T cup A).
end{align}
It suffices to show that if $T notsubset overline{W_1 cap W_2}$ then the last summand is at least $r(W_1 cap W_2) + 1$. This is clear, since by assumption
$$r(W_1 cap W_2) < r((W_1 cap W_2)cup T) le r((W_1 cap W_2)cup T cup A).$$
If $T$ is in the closure of $W_1$ only, then
begin{align}
r(W_1 cup A) + r(W_2 cup A)
&= r(W_1 cup Tcup A) + r(W_2) + 1 \
&ge r(W_1 cup W_2 cup T cup A) + r(W_1 cap W_2) + 1 \
&= r(W_1 cup W_2 cup A) + r((W_1 cap W_2) cup A).
end{align}
The case in which $T$ is in the closure of neither $W_i$ is easier, as $r(W cup Tcup A) le r(Wcup T) + 1 = r(W) + 1$ (apply with $W=W_1cup W_2$).

Monotonicity: Suppose $Wcup A subset W'$ for $W,W' in M$. Then by construction $W' supset M_z,$ so $Tsubset W'$. Thus either $Tsubsetoverline{W}$ and $r(Wcup A)=r(Wcup Tcup A)=r(Wcup M_z)$ and we conclude by monotonicity of $r$ on $M$, or otherwise $$r(W) < r(Wcup T) le r(W').$$
Inclusions of the form $Wsubset W'cup A$ are obvious. For inclusions of the form $Wcup A subset W' cup A$, the case $Tsubsetoverline{W}$ reduces again to monotonicity of $r$ on $M$, and the other case is analogous to what we did before.

1-continuity: If $Wcup A lessdot W'$ in the lattice generated by $M$ and $A$, note that if $W lessdot W'$ in $M$ we are done. If not, there is some maximal chain in $M$:
$$ W lessdot W_1 lessdot ldots lessdot W_n lessdot W',$$
where $W' supset A$. Consider the maximal $ile n$ such that $W_i cup A neq W'$. If $i < n-1$, then $W_{n-1}cup A = W_n cup A = W'$, but then $W_n setminus W_{n-1} subset A,$ a contradiction (as $A$ is contained in any set of $M$ it intersects). We need to show $r(W_{n-1}cup A) ge r(W') - 1$. By submodularity, if $r(W_{n-1}cup A) = r(W_{n-1})$ then also $$r(W') = r(W_n cup A) = r(W_n).$$
Therefore $r(W_{n-1} cup A) ge r(W_{n-1})+1 ge r(W_n)ge r(W')-1.$

Now set all elements of $A$ parallel to each other, and continue.

Edit: I forgot to mention at first that I would be interested in your application. It would be nice if you could sketch it.

Extending submodular functions from a sublattice

One Answer

Add your own answers!

Ask a Question