Background: In machine learning, we often work with graphical models to represent high dimensional probability density functions. If we discard the constraint that a density integrates (sums) to 1, we get an unnormalized graph-structured energy function.
Suppose we have such an energy function, $E$, defined on a graph $G = (\mathcal{V}, \mathcal{E})$. There is one variable $x$ for each vertex of the graph, and there are real-valued unary and pairwise functions, $\theta_i(x_i) : i \in \mathcal{V}$ and $\theta_{ij}(x_i, x_j) : ij \in \mathcal{E}$, respectively. The full energy is then
$$E(\mathbf{x}) = \sum_{i \in \mathcal{V}} \theta_i(x_i) + \sum_{ij \in \mathcal{E}} \theta_{ij}(x_i, x_j)$$
If all $x \in \mathbf{x}$ are binary, we can think of an $x$ as indicating set membership and with just a small abuse of terminology talk about submodularity. In this case, an energy function is submodular iff $\theta_{ij}(0, 0) + \theta_{ij}(1, 1) \le \theta_{ij}(0, 1) + \theta_{ij}(1, 0)$. We are typically interested in finding the configuration that minimizes the energy, $\mathbf{x}^* = \arg \min_{\mathbf{x}} E(\mathbf{x})$.
There seems to be a connection between minimizing a submodular energy function and monotone boolean functions: if we lower the energy of some $\theta_i(x_i=1)$ for any $x_i$ (i.e., increase its preference to be "true"), then the optimal assignment of any variable $x_i^* \in \mathbf{x}^*$ can only change from 0 to 1 ("false" to "true"). If all $\theta_i$ are restricted to be either 0 or 1, then we have $|\mathcal{V}|$ monotone boolean functions:
$$f_i(\mathbf{\theta}) = x_i^*$$
where as above, $\mathbf{x^*} = \arg \min_{\mathbf{x}} E(\mathbf{x})$.
Question: Can we represent all monotone boolean functions using this setup by varying the pairwise terms, $\theta_{ij}$? What if we allow $E$ to be an arbitrary submodular energy function? Conversely, can we represent all submodular minimization problems as a set of $|\mathcal{V}|$ monotone boolean functions?
Can you suggest references that will help me towards better understanding these connections? I'm not a theoretical computer scientist, but I'm trying to understand if there are insights about monotone boolean functions that are not captured by thinking in the submodular minimization terms.
