EUVIMEDEUVIMED entdecken
Crossref

Clique Number of XOR-Powers of Kneser Graphs

Zoltán Füredi, András Imolay, Ádám Schweitzer

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →