2025/10/01 by Füredi, Zoltán, Imolay, András, Schweitzer, Ádám
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.01509
Let f_ℓ(n, k) denote the clique number of the xor-product of ℓ isomorphic Kneser graphs KG(n,k). Alon and Lubetzky investigated the case of complete graphs as a coding theory problem and showed f_ℓ(n,1)≤ ℓ n +1. Imolay, Kocsis, and Schweitzer proved that f2(n,k)≤ n/k +c(k). Here, the order of magnitude of c(k) is determined to be Θ( k \binom2kk ). By explicit constructions and by an algebraic proof, it is shown that ℓ n- 2ℓ-1 ≤ f_ℓ(n,1)≤ ℓ n-ℓ+1 (for all n ≥ 1 and ℓ≥ 3). Finally, it is proved that the order of magnitude of f lies between Ω(n\lfloor log2(ℓ+1)\rfloor) and O(n\lfloor (ℓ+1)/(2) \rfloor ) (as ℓ, k are given and n→ ∞). We conjecture that the lower bound gives the correct exponent.