Bandwidth of graphs resulting from the edge clique covering problem (Q668017)

Summary: Let \(n,k,b\) be integers with \(1 \leq k-1 \leq b \leq 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) \leq b\) and where two such vertices \(X,Y\) are joined by an edge if \(\max(X \cup Y)-\min(X \cup Y) \leq 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\geq \frac{n+k-1}{2}\), the exact bandwidth of these graphs is determined. Moreover, the bandwidth is determined asymptotically for \(b=o(n)\) and for \(b\) growing linearly in \(n\) with a factor \(\beta \in (0,1]\), 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.