The exact isoperimetric inequality for ternary and quaternary cubes

AbstractWe extend the well-known edge-isoperimetric inequality of Harper, Bernstein and Hart to ternary and quaternary cubes. More generally, let Q be the graph with vertex set V=∏i=1n[ki] in which x∈V is joined to y∈V if for some i we have |xi−yi|=1 and xj=yj for all j≠i. If k1⩾⋯⩾kn and k2⩽4, we prove that for any 0⩽m⩽|V|, no m-set of vertices of Q is joined to the rest of Q by fewer edges than the set of the first m vertices of Q in the lexicographic ordering on V