A Variant of the Discrete Isoperimetric Problem

Abstract

We consider a variant of what is known as the discrete isoperimetric problem, namely the problem of minimising the size of the boundary of a family of subsets of a finite set. We use the technique of `shifting’ to provide an alternative proof of a result of Hart. This technique was introduced in the early \(1980s\) by Frankl and Füredi and gave alternative proofs of previously known classical results like the discrete isoperimetric problem itself and the Kruskal-Katona theorem. Hence our purpose is to bring Hart’s result into this general framework.