Reflect-push methods. Part I: Two dimensional techniques (Q6194254)

Summary: We determine all maximum weight downsets in the product of two chains, where the weight function is a strictly increasing function of the rank. Many discrete isoperimetric problems can be reduced to the maximum weight downset problem. Our results generalize Lindsay's edge-isoperimetric theorem in two dimensions in several directions. They also imply and strengthen (in several directions) a result of \textit{R. Ahlswede} and \textit{G. O. H. Katona} [Acta Math. Acad. Sci. Hung. 32, 97--120 (1978; Zbl 0386.05036)] concerning graphs with maximal number of adjacent pairs of edges. We find all optimal shifted graphs in the Ahlswede-Katona problem. Furthermore, the results of Ahlswede and Katona [loc. cit.] are extended to posets with a rank increasing and rank constant weight function. Our results also strengthen a special case of a recent result by \textit{L. Keough} and \textit{A. J. Radcliffe} [Combinatorica 36, No. 6, 703--723 (2016; Zbl 1399.05109)] concerning graphs with the fewest matchings. All of these results are achieved by applications of a key lemma that we call the reflect-push method. This method is geometric and combinatorial. Most of the literature on edge-isoperimetric inequalities focuses on finding a solution, and there are no general methods for finding all possible solutions. Our results give a general approach for finding all compressed solutions for the above edge-isoperimetric problems. By using the Ahlswede-Cai local-global principle [\textit{R. Ahlswede} and \textit{N. Cai}, Eur. J. Comb. 18, No. 4, 355--372 (1997; Zbl 0940.05067)], one can conclude that lexicographic solutions are optimal for many cases of higher dimensional isoperimetric problems. With this and our two dimensional results we can prove Lindsay's edge-isoperimetric inequality in any dimension. Furthermore, our results show that lexicographic solutions are the unique solutions for which compression techniques can be applied in this general setting.