In combinatorics we often meet two kinds of extremal problems . In one kind , optimal configurations consist of 'objects' , which are somehow uniformly spread in the space under consideration ; and in the other kind , optimal configurations consist of 'objects' , which are somehow compressed . To the first kind belong packing , covering and coding problems , whereas diametric (especially of Erdo ¨ s -Ko -Rado type) , vertexand edge-isoperimetric problems belong to the second kind .
For many problems of the spreading type , the probabilistic method gives good or even asymptotically optimal results but , mostly , strictly optimal configurations are unknown . In contrast , problems of the compressing type can often be solved exactly with pushing techniques ('pushing down' , 'pushing to the left' etc . ; see [14]) . However , the success of pushing operations is linked to the property that there is a 'nested' structure of optimal configurations with respect to some order . When this is not the case , then there are competing configurations (for example , in [6]) and solutions are harder to obtain .
We concentrate here on edge-isoperimetric problems . They can be defined for any graph G ϭ ( ᐂ , Ᏹ ) as follows . For any A ' ᐂ , define the set Ꮾ ( A ) of all boundary edges ; that is ,
(1 . 1) P ROBLEM 1 . For given positive integer m , find a set A ' ᐂ of cardinality m with minimal possible value of ͉ Ꮾ ( A ) ͉ .
A similar problem in this .
P ROBLEM 2 . For given positive integer m , find a set A ' ᐂ of cardinality m with maximal possible value of ͉ ( A ) ͉ , where ( A ) ϭ ͕͕ x , y ͖ Ᏹ : ͕ x , y ͖ ' A ͖ is the set of inner edges of A .
Notice that , for regular graphs G of degree d ,
and in this case Problems 1 and 2 are equivalent in the sense that a solution of one of these problems is at the same time a solution of the other .
Most results in the literature concern graphs the vertex set ᐂ of which is a cartesian product ᐄ n ϭ ͟ n t ϭ 1 ᐄ t of sets ᐄ t ϭ ͕ 0 , 1 , . . . , ␣ t ͖ and the edges of which are pairs of vertices with distance 1 under a specified metric .
For the Hamming metric , Problems 1 and 2 were first solved in the binary case (i . e .
when ␣ 1 ϭ ␣ 2 ϭ и и и ϭ ␣ n ϭ 1) by Harper [16] and for arbitrary finite ␣ t 's by Lindsey [20] . (The results have been rediscovered many times : [8] , [11] , . . . , [18] . ) They proved that for each m the set of the first m vertices of ᐄ n in the lexicographic order gives a 355