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,\ldots\right\} $. A function $f:L\to \mathbb{N}$ is said to be

• submodular if it satisfies $f\left( a\right) +f\left( b\right) \geq f\left( a\wedge b\right) +f\left( a\vee b\right) $ for all $a,b\in L$.

• isotone if it satisfies $f\left( a\right) \leq f\left( b\right) $ whenever $a,b\in L$ satisfy $a\leq b$.

• 1-continuous if it satisfies $f\left( b\right) -f\left( a\right) \in\left\{ 0,1\right\} $ whenever $a,b\in L$ satisfy $a\lessdot b$ (that is, $a<b$ but there exists no $c\in 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:L\to\mathbb{N}$ satisfying $f\left( \varnothing\right) =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 "$a\lessdot 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:M\to\mathbb{N}$ be a function. An extension of $g$ to $L$ will mean a function $f:L\to\mathbb{N}$ such that $f\mid_{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:L\to\mathbb{N}$ of $g$ to $L$ by setting \begin{align} f\left( y\right) =\min\left\{ g\left( x\right) \ \mid\ x\in L\text{ satisfying }x\geq y\right\} \label{darij1.eq.pf.thm1.1} \tag{1} \end{align} for all $y\in 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}$.

For the sake of curiosity, let me mention a related result:

Corollary 4. If $g$ is a submodular function on $M$, then there exists a submodular extension of $g$ to $L$.

(This is just Theorem 1 with the words "isotone" removed.) An easy way to prove Corollary 4 is by piggybacking on our proof of Theorem 1: Namely, let $g$ be a submodular function on $M$, and let $\operatorname{rank} : L \to \mathbb{N}$ be the function that sends each set $a \in L$ to its size $\left|a\right|$. Pick any integer $n > \max\left\{g\left(b\right) - g\left(a\right) \mid a \lessdot b \text{ in } M\right\}$. Then, the function $g' := g + n \operatorname{rank}$ (where we add and scale functions pointwise -- so this function sends each $a \in M$ to $g\left(a\right) + n\left|a\right|$) is isotone (by the choice of $n$) and submodular (since $g$ is submodular and since $\left|a\right| + \left|b\right| = \left|a \wedge b\right| + \left|a \vee b \right|$ for any $a, b \in L$). Thus, applying Theorem 1 to $g'$ instead of $g$, we obtain an isotone submodular extension $f'$ of $g'$ defined via \eqref{darij1.eq.pf.thm1.1}. Now, it is easy to see that $f := f' - n \operatorname{rank}$ is a submodular extension of $g$. (To check this, make sure to prove that all values of $f$ are nonnegative; this relies on the specific formula \eqref{darij1.eq.pf.thm1.1}, which guarantees that the multiple of $n$ added at any given point of $M$ is larger or equal to the multiple of $n$ subtracted afterwards.)

Answer 1

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:

1. 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.
2. If all inclusion-minimal subsets in $M$ are singletons (i.e. $\{x\}$ for some $x\in E$,) find some $S\in M$ which is not a union of singletons in $M$, and extend $M$ by $S \setminus T$ for $T = \{x\in E\mid \{x\}\in M, x\in 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 a\in A\}$, $$r(S) = \begin{cases}r(S) & S\cap A=\emptyset \\ r(S\cup 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_{x\in S \in M} S$$ for each $x \in E \setminus U$. The family $\{M_x\}_{x\in 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=U\cap 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 $A\cap S \ni y$ but $A\cap S \not\ni y'$ for some $y,y' \in M_z$ and some subset $S\in 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 $A\cup W$ to be $$\begin{cases} r(W)+1 & T\not\subset \overline{W} \\ r(W \cup (T\cup A)) & T \subset \overline{W}, \end{cases}$$

where $\overline{W}$ is the closure, i.e. $T\subset\overline{W}$ iff $r(W)=r(W\cup T)$ (note that in the second case, the rank is already defined, since $W, (T\cup 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 $W\in 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 T\cup 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 \not\subset \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 T\cup 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 T\cup A) \le r(W\cup T) + 1 = r(W) + 1$ (apply with $W=W_1\cup W_2$).

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

• 1-continuity: Suppose $W,W'\in M$ and $W\cup A \lessdot W'$ in the lattice generated by $M$ and $A$. We need to verify that $|r(W')- r(W \cup A)|\le 1$. Note that if $W \lessdot W'$ in $M$ we are done: we already have $|r(W')- r(W \cup A)|\le 1$ (because $W \le W\cup A \lessdot W'$ and $W \lessdot W'$ together imply $W=W\cup A\in M$, so this follows from 1-continuity in $M$). 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 $i\le 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} \subsetneq A,$ a contradiction (as $A$ is contained in any set of $M$ it intersects).
  If $i=n-1$ then in particular $W\cup A \subseteq W_{n-1}\cup A \subsetneq W'$, but $W\cup A$ is covered by $W'$, so $W=W_{n-1}$ (and $i=n$ doesn't occur because it implies $W=W_n$, but we assumed $W$ is not covered by $W'$, whereas $W_n \lessdot W'$.)
  Thus 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),$$ but $W_n \cup A = W'$ since $i=n-1$, and therefore $r(W_n)=r(W')$, contradicting $W_n \lessdot W'$. Therefore $r(W_{n-1} \cup A) \ge r(W_{n-1})+1 \ge r(W_n)\ge r(W')-1.$
  
  There is another case to check: for $W,W' \in M$ we need to verify that $|r(W'\cup A) - r(W\cup A)|\le 1$ if $W\cup A \lessdot W'\cup A$ in the lattice generated by $M$ and $A$. If $A\subseteq W'$ we reduce to the previous case; if not, such a covering relation implies $W\lessdot W'$. Now:

  • If $T \subseteq \overline{W}$ then $r(W)=r(W\cup A)$ and $r(W')=r(W'\cup A)$, so 1-continuity follows from 1-continuity in $M$.
  • Otherwise, if $T\subseteq \overline{W'}$ then $r(W\cup A)=r(W)+1 \ge r(W') = r(W'\cup A)$ and 1-continuity is satisfied.
  • Finally, if $T \not\subseteq \overline{W'}$ then $r(W\cup A)=r(W)+1$ and $r(W' \cup A)=r(W')+1$, so again 1-continuity follows from 1-continuity in $M$.

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.

Another edit: I added some details to the verification of 1-continuity and tried to make it a bit more readable.