General edge-isoperimetric inequalities. II: A local-global principle for lexicographical solutions (Q1362991)

The lexicographic order \({\mathcal L}\) on a sequence space \({\mathcal H}^n=\{0,1,\ldots,\alpha\}\) is defined by \(x^n<y^n\) iff there exists a \(t\) such that \(x_t<y_t\) and \(x_s=y_s\) for \(s<t\). There are two kinds of edge-isoperimetric problems (EIP) that can be represented as extremal problems in graph theory. For a graph \(G=(V,E)\), for any \(A\subset V\) the sets of all boundary and inner edges are defind by \({\mathcal B}(A)=\{xy\in E:|\{x,y\}\cap A|=1\}\) and \({\mathcal I}(A)=\{xy\in E:x,y\in A\}\), respectively. The boundary-edge-isoperimetric problem (BEIP) and inner-edge-isoperimetric problem (IEIP) are defined as follows: for a given graph and positive integer \(m\), find a set \(A\subset V\) of cardinality \(m\) with minimal (maximal) possible value of \(|{\mathcal B}(A)|\) (\(|{\mathcal I}(A)|\)). In this paper the following problem is considered: ``Is \({\mathcal L}\) optimal for an EIP in \(G^n\)?'' (\(G^n\) denotes the \(n\)th power of \(G\) relatively to the Cartesian sum of graphs.) If \(N=\{1,2,\ldots,n\}\), for any \(A\subset{\mathcal H}^n={\mathcal H}^N\), \(A_T(x^{N\setminus J})\) is defined as \(\{x^J\in{\mathcal H}^J:x^N\in A\}\) for \(x^{N\setminus J}\in{\mathcal H}^{N\setminus J}\) and for any set function \(\phi\) on \(2^{{\mathcal H}}\), \(\phi^n(A)=\sum_{t=1}^n\sum_{x^{N\setminus\{t\}}\in{\mathcal H}^{N\setminus\{t\}}}\phi(A_t(x^{N\setminus\{t\}}))\). The main result of the paper is the following one: Let \(|{\mathcal H}|\geq 3\), \(n\) be any integer \(\geq 2\) and \(\phi\) be any set function \(\phi:2^{{\mathcal H}}\rightarrow\mathbb{R}\) satisfying: I (nestedness): for all \(k\in{\mathcal H}=\{0,1,\ldots,\alpha\}\), \(A\subset{\mathcal H}\) with \(|A|=k+1\) implies \(\phi(A)\leq\phi(\{0,1,\ldots,k\})\); II (submodularity): for \(A,B\subset{\mathcal H}\), \(\phi(A)+\phi(B)\leq\phi(A\cup B)+\phi(A\cap B)\); III: \(\phi(\varnothing)=0\). Then \({\mathcal L}\) on \(X^n\) is optimal for \(\phi^n\) iff \({\mathcal L}\) on \({\mathcal H}^2\) is optimal for \(\phi^2\). (Condition I says that \({\mathcal L}\) is an optimal order for \(\phi\).) Notice that this family of set functions on \(G^n\) includes ``boundary-edge'' and ``inner-edge'' functions. Finally, as an example demonstrating the power of this local-global principle, an edge-isoperimetric theorem for the powers of complete bipartite graphs \(C_{m,m}\) is given: the first segments in lexicographical order \({\mathcal L}\) give optimal sets for the (inner and boundary) edge-isoperimetric problems for \(C^2_{m,m}\), and therefore for \(C^n_{m,m}\). Notice that \(C_{m,m}\) being a regular graph, BEIP and IEIP are equivalent.