General edge-isoperimetric inequalities. I: Information-theoretical methods (Q1357262)

The authors consider extremal problems on subsets of finite sets and their Cartesian products. A typical example of such a problem is the edge-isoperimetric problem. Given a graph \(G= (V,E)\) and an integer \(m\) the problem is to find a set \(A\subseteq V\) with \(|A|= m\) such that the induced subgraph \(G[A]\) has a maximum number of edges. Very often a solution of this problem for the underlying graph \(G\) is not difficult and the main question is how this information helps to derive a solution for the Cartesian product \(G\times\cdots\times G\) (\(n\) times). If we assume additionally that the extremal subsets for \(G\) are nested, then the standard approach to this problem on \(G\times G\) is to use compressions and to get a downset in some partial order with no decrease in the number of induced edges. It is observed that this technique is applied to the maximization of more general functions if these functions defined on the Cartesian products of the domains are submodular and in a sense additive. Under such assumptions the authors derive a closed formula for the value of such a function of a downset and, using some facts from information theory, obtain an upper bound for this function. The derived upper bounds are compared with one for the edge-isoperimetric problem on the Cartesian product of paths and cycles, where an exact solution is known. Moreover, an asymptotically optimal solution of this problem for the Shannon product of graphs is obtained. To get the Shannon product of two graphs one has to complete the graphs with a loop in each vertex and then take the Cartesian products of the resulting graphs. The proofs use the powerful technique of probability theory and involve some strong information-theoretic results obtained by one of the authors.