Bandwidth of graphs resulting from the edge clique covering problem

Abstract

Let $n,k,b$ be integers with $1\le k-1\le b\le n$ and let $G_{n,k,b}$ be the graph whose vertices are the $k$-element subsets $X$ of $\{0,\dots ,n\}$ with $\max (X)-\min (X)\le b$ and where two such vertices $X,Y$ are joined by an edge if $\max (X\cup Y)-\min (X\cup Y)\le b$. These graphs are generated by applying a transformation to maximal $k$-uniform hypergraphs of bandwidth $b$ that is used to reduce the (weak) edge clique covering problem to a vertex clique covering problem. The bandwidth of $G_{n,k,b}$ is thus the largest possible bandwidth of any transformed $k$-uniform hypergraph of bandwidth $b$. For $b\ge \frac{n+k-1}{2}$, the exact bandwidth of these graphs is determined. For $b<\frac{n+k-1}{2}$, the bandwidth is asymptotically determined in the case of $b=o(n)$ and in the case of $b$ growing linearly in $n$ with a factor $\beta \in (0,0.5]$, where for one case only bounds could be found. It is conjectured that the upper bound of this open case is the right asymptotic value.