On a problem by Shapozenko on Johnson graphs

Abstract

The Johnson graph $J(n,m)$ has the $m$--subsets of $\{1,2,\dots ,n\}$ as vertices and two subsets are adjacent in the graph if they share $m-1$ elements. Shapozenko asked about the isoperimetric function ${\mu }_{n,m}(k)$ of Johnson graphs, that is, the cardinality of the smallest boundary of sets with $k$ vertices in $J(n,m)$ for each $1\le k\le \left(\genfrac{}{}{0ex}{}{n}{m}\right)$. We give an upper bound for ${\mu }_{n,m}(k)$ and show that, for each given $k$ such that the solution to the Shadow Minimization Problem in the Boolean lattice is unique, and each sufficiently large $n$, the given upper bound is tight. We also show that the bound is tight for the small values of $k\le m+1$ and for all values of $k$ when $m=2$.

15 pages, 1 figure. Improved version with the comments from the referees