# Submodularity for Cartesian product

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.

• How i this related to convex analysis? Jun 2, 2017 at 22:42

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.
• 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$. Apr 16, 2020 at 21:46