On an Equivalence in Discrete Extremal Problems

We introduce some equivalence relations on graphs and posets and prove that they are closed under the cartesian product operation. These relations concern the edge-isoperimetric problem on graphs and the shadow minimization problems on posets. For a long time these problems have been considered quite independently. We present close connections between them. In particular we show that a number of known results concerning the edge-isoperimetric problem for concrete families of graphs are direct consequences of the Macauleyness of appropriate posets. Keywords: Isoperimetric problem, Macaulay poset, compression, cartesian product. 1 Introduction Let G = (VG ; EG ) be a graph. We consider the following general problem: given a function F : 2 VG 7! IR and a number m (1 m jV G j), find an m- element subset A ` VG with maximum (or minimum) value of F (A) among all the m-element subsets of VG . Such subsets are called optimal . Similar problems arise in a number of practical situations. W..