On the Bandwidth of the Kneser Graph

Abstract

Let $G=(V,E)$ be a graph on $n$ vertices and $f:V\to [1,n]$ a one to one map of $V$ onto the integers $1$ through $n$. Let $dilation(f)=$ max$\{|f(v)-f(w)|:vw\in E\}$. Define the {\it bandwidth} $B(G)$ of $G$ to be the minimum possible value of $dilation(f)$ over all such one to one maps $f$. Next define the {\it Kneser Graph} $K(n,r)$ to be the graph with vertex set $\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$, the collection of $r$-subsets of an $n$ element set, and edge set $E=\{vw:v,w\in (\genfrac{}{}{0ex}{}{[n]}{r}),v\cap w=\varnothing \}$. For fixed $r\ge 4$ and $n\to \infty$ we show that $$B(K(n,r))=\left(\genfrac{}{}{0ex}{}{n}{r}\right)-\frac{1}{2}\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)-2\frac{n^{r-2}}{(r-2)!}+(r+2)\frac{n^{r-3}}{(r-3)!}+O(n^{r-4}).$$