Uniqueness in Harper’s vertex-isoperimetric theorem

Abstract For a set A ⊆ Q n = 0 , 1 n the t -neighbourhood of A is N t A = x : d x , A ≤ t , where d denotes the usual graph distance on Q n . Harper’s vertex-isoperimetric theorem states that among the subsets A ⊆ Q n 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 ⊆ Q n is a subset of given size for which the sizes of both N t A and N t A c 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 B x , r ⊆ A ⊆ B x , r + 1 for some x ∈ Q n . We go further to classify all the sets A ⊆ Q n for which the sizes of both N t A and N t A c are minimal for all t > 0 among the subsets of Q n of given size. We also prove that, perhaps surprisingly, if A ⊆ Q n for which the sizes of N A and N A c are minimal among the subsets of Q n of given size, then the sizes of both N t A and N t A c are also minimal for all t > 0 among the subsets of Q n of given size. Hence the same classification also holds when we only require N A and N A c to have minimal size among the subsets A ⊆ Q n of given size.