Clique number of xor-powers of Kneser graphs

Abstract

Let $f_{\ell }(n,k)$ denote the clique number of the xor-product of $\ell$ isomorphic Kneser graphs KG(n,k). Alon and Lubetzky investigated the case of complete graphs as a coding theory problem and showed $f_{\ell }(n,1)\le \ell n+1$. Imolay, Kocsis, and Schweitzer proved that $f_2(n,k)\le n/k+c(k)$. Here, the order of magnitude of $c(k)$ is determined to be $\Theta \left(k\left(\genfrac{}{}{0ex}{}{2k}{k}\right)\right)$. By explicit constructions and by an algebraic proof, it is shown that $\ell n-2\ell -1\le f_{\ell }(n,1)\le \ell n-\ell +1$ (for all $n\ge 1$ and $\ell \ge 3$). Finally, it is proved that the order of magnitude of $f$ lies between $\Omega \left(n^{\lfloor {\log }_2(\ell +1)\rfloor }\right)$ and $O\left(n^{\lfloor \frac{\ell +1}{2}\rfloor }\right)$ (as $\ell$, $k$ are given and $n\to \infty$). We conjecture that the lower bound gives the correct exponent.

11 pages