Uniqueness in Harper’s vertex-isoperimetric theorem

• Published in: Discrete mathematics 2020-04, Vol.343 (4), p.111696, Article 111696
• Main Author: Räty, Eero
• Format: Article
• Language: English
• Subjects: Harper’s theorem; Isoperimetric inequality
• ISSN: 0012-365X; 1872-681X
• DOI: 10.1016/j.disc.2019.111696

For a set A⊆Qn=0,1n the t-neighbourhood of A is NtA=x:dx,A≤t, where d denotes the usual graph distance on Qn. Harper’s vertex-isoperimetric theorem states that among the subsets A⊆Qn of given size, the size of the t-neighbourhood is minimised when A is taken to be an initial segment of the simplicial order. Aubrun and Szarek asked the following question: if A⊆Qn is a subset of given size for which the sizes of both NtA and NtAc are minimal for all t>0, does it follow that A is isomorphic to an initial segment of the simplicial order? Our aim is to give a counterexample. Surprisingly it turns out that there is no counterexample that is a Hamming ball, meaning a set that lies between two consecutive exact Hamming balls, i.e. a set A with Bx,r⊆A⊆Bx,r+1 for some x∈Qn. We go further to classify all the sets A⊆Qn for which the sizes of both NtA and NtAc are minimal for all t>0 among the subsets of Qn of given size. We also prove that, perhaps surprisingly, if A⊆Qn for which the sizes of NA and NAc are minimal among the subsets of Qn of given size, then the sizes of both NtA and NtAc are also minimal for all t>0 among the subsets of Qn of given size. Hence the same classification also holds when we only require NA and NAc to have minimal size among the subsets A⊆Qn of given size.