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 Ahlswede and Katona 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-Katona 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 Keough and Radcliffe 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, 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.
@article{10_37236_12043,
author = {Nikola Kuzmanovski and Jamie Radcliffe},
title = {Reflect-push methods. {I:} {Two} dimensional techniques},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {1},
doi = {10.37236/12043},
zbl = {1535.05079},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12043/}
}
TY - JOUR
AU - Nikola Kuzmanovski
AU - Jamie Radcliffe
TI - Reflect-push methods. I: Two dimensional techniques
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/12043/
DO - 10.37236/12043
ID - 10_37236_12043
ER -
%0 Journal Article
%A Nikola Kuzmanovski
%A Jamie Radcliffe
%T Reflect-push methods. I: Two dimensional techniques
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/12043/
%R 10.37236/12043
%F 10_37236_12043
Nikola Kuzmanovski; Jamie Radcliffe. Reflect-push methods. I: Two dimensional techniques. The electronic journal of combinatorics, Tome 31 (2024) no. 1. doi: 10.37236/12043
