2
$\begingroup$

We define a set function $f:2^E \rightarrow \mathbb{R}$ to be submodular if for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $.

How could I extend this concept to a Cartesian product of two sets? For example, would the following definition make sense?

We define a set function $f:2^{E_1 \times E_2} \rightarrow \mathbb{R}$ to be submodular if for every $ S_1,T_1\subseteq E_1 $ with $ S_1\subseteq T_1 $ and $ S_2,T_2\subseteq E_2 $ with $ S_2\subseteq T_2 $ for every $ p\in E_1\setminus T_1$ and $q\in E_2\setminus T_2 $, it holds that $f((S_1\cup \{p\}) \times (S_2\cup \{q\}))-f(S_1 \times S_2)\geq f((T_1\cup \{p\}) \times (T_2\cup \{q\})) - f(T_1 \times T_2) $.

If yes, then how can I prove this holds if submodularity holds for individual set functions $f_1:2^{E_1} \rightarrow \mathbb{R}$ and $f_2:2^{E_2} \rightarrow \mathbb{R}$?

Any help and hints will be greatly appreciated.

$\endgroup$
1
  • $\begingroup$ How i this related to convex analysis? $\endgroup$
    – copper.hat
    Jun 2, 2017 at 22:42

1 Answer 1

1
$\begingroup$

Submodularity is really a property of functions on what are called lattices.

A lattice is a set $L$ with a partial order $\succeq$, along with the property that for all $a, b \in L$, $ a \vee b = l.u.b. \{a,b\} \in L$ and $ a \wedge b = g.l.b. \{a,b \} \in L$. For you, $L$ is almost a power set, $\vee$ is set union, and $\wedge$ is set intersection, and the partial order $\succeq$ is set inclusion. So the "real" definition of submodular is that for all sets $S$ and $ T$ in $L$, $f(S\cup T) + f(S\cap T) \le f(S) + f(T)$. The definitions you wrote are just to avoid introducing the idea of the lattice, order, and $\vee$ and $\wedge$.

But you want to look at Cartesian products of lattices. You have a lattice $L_1$ and a lattice $L_2$, set functions $f_1$ on $L_1$ and $f_2$ on $L_2$, and you want to combine things together.

If you define $(S_1, S_2) \vee (T_1, T_2) = (S_1\cup S_2, T_1 \cup T_2)$ and $(S_1, S_2) \wedge (T_1, T_2) = (S_1\cap S_2, T_1 \cap T_2)$, the glb and lub properties still hold for $L_1 \times L_2$. Now, if you take any submodular function $g$ on $\mathbb{R}^2$ --- $g(\max\{a,b\})+g(\min\{a,b\}) \le g(a) + g(b)$ --- you have $$ g( f_1(S_1\vee S_2), f_2(T_1\vee T_2)) + g( f_1(S_1\wedge S_2), f_2(T_1\wedge T_2)) \le g(f_1(S_1),f_2(S_2))+g(f_1(T_1),f_2(T_2)) $$ and you get a submodular set function on the product of the two lattices if $f_1$ and $f_2$ are submodular.

To extend this to $L_1 \times L_2 \times ... \times L_N$, make $g$ an argument of $N$ numbers so that $g(y) = g((y_1, ..., y_N))$ with the same submodularity property, so that $$ g(y \vee y') + g(y \wedge y') \le g(y) + g(y'). $$ where $\vee$ is coordinatewise maximization and $\wedge$ is coordinatewise minimization.

$\endgroup$
1
  • $\begingroup$ Thanks. Using your example, I begin with $f(S\cup T) + f(S\cap T) \le f(S) + f(T)$. By moving some terms, this becomes $ f(S) - f(S\cap T) \ge f(S\cup T) - f(T)$. Could you explain how is this same as the submodularity defined by $f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $? Here, $S,T\subseteq E $ with $ S\subseteq T $ and $ x\in E\setminus T$. $\endgroup$
    – ryan80
    Apr 16, 2020 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.