Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2510.01509 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912622617559040 |
|---|---|
| author | Füredi, Zoltán Imolay, András Schweitzer, Ádám |
| author_facet | Füredi, Zoltán Imolay, András Schweitzer, Ádám |
| contents | 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 n/k +c(k)$.
Here, the order of magnitude of $c(k)$ is determined to be $Θ\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 $Ω\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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_01509 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Clique number of xor-powers of Kneser graphs Füredi, Zoltán Imolay, András Schweitzer, Ádám Combinatorics 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 n/k +c(k)$. Here, the order of magnitude of $c(k)$ is determined to be $Θ\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 $Ω\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. |
| title | Clique number of xor-powers of Kneser graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2510.01509 |