Clique Number of XOR-Powers of Kneser Graphs
The Electronic Journal of Combinatorics · 05.06.2026 · 33 (2)
DOI: 10.37236/14969 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Electronic Journal of Combinatorics, online erschienen am 05.06.2026. Verfasst von Zoltán Füredi und 2 weiteren Autor:innen.
Abstract (Originalsprache)
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)\leq \ell n +1$. Imolay, Kocsis, and Schweitzer proved that $f_2(n,k)\leq \left\lfloor\frac{n}{k}\right\rfloor+c(k)$. Here, the order of magnitude of $c(k)$ is determined to be $\Theta\left( k \binom{2k}{k}\right)$. By explicit constructions and by an algebraic proof, it is shown that $\ell n- 2\ell-1 \leq f_\ell(n,1)\leq \ell n-\ell+1$ (for all $n\geq 1$ and $\ell\geq 3$). Finally, it is proved that the order of magnitude of $f$ lies between $\Omega\left(n^{\left\lfloor \log_2(\ell+1)\right\rfloor}\right)$ and $O\left(n^{\left\lfloor \frac{\ell+1}{2} \right\rfloor} \right)$ (as $\ell$, $k$ are given and $n\to \infty$). We conjecture that the lower bound gives the correct exponent.
Zitieren
APA
Füredi, Z., Imolay, A., & Schweitzer, Á. (2026). Clique Number of XOR-Powers of Kneser Graphs. The Electronic Journal of Combinatorics, 33(2). https://doi.org/10.37236/14969
Vancouver
Füredi Z, Imolay A, Schweitzer Á. Clique Number of XOR-Powers of Kneser Graphs. The Electronic Journal of Combinatorics. 2026;33(2). doi:10.37236/14969
BibTeX
@article{Fredi2026,
author = {Füredi, Zoltán and Imolay, András and Schweitzer, Ádám},
title = {Clique Number of XOR-Powers of Kneser Graphs},
journal = {The Electronic Journal of Combinatorics},
year = {2026},
volume = {33},
number = {2},
doi = {10.37236/14969}
}
EUVIMED