Primeness of tensor products of complete graphs
Question 4.31 · arXiv:2401.06062
Status open high confidence
Question 4.31 from arXiv:2401.06062 asks for a characterization of when the tensor product $\prod_{i=1}^d K_{n_i}$ (vertices are $d$-tuples, adjacent iff differing in every coordinate) is prime. The source paper was published in the Journal of Combinatorics (2026, vol. 17, no. 2, pp. 223–252), where the question appears as an open problem. No follow-up paper specifically resolving this combinatorial question was found in a targeted literature search.
Reviewer notes. The source paper itself was published in the Journal of Combinatorics (2026). Question 4.31 arises as the combinatorial core of the semisimple ring case of a broader open problem (Question 4.28) about primality of ring Cayley graphs. No follow-up paper resolving or partially resolving this question was found after 5 web queries.
Context
For a semisimple ring $R = \prod_{i=1}^d k_i$ (a product of finite fields of sizes $q_i$), the associated Cayley graph satisfies $X_R \cong \prod_{i=1}^d K_{q_i}$, reducing Question 4.28 for the semisimple case to this combinatorial question about tensor products (Kronecker products) of complete graphs. The vertex set of $\prod_{i=1}^d K_{n_i}$ consists of $d$-tuples $(s_1,\ldots,s_d)$ with two vertices adjacent iff they differ in every coordinate.
Notes. This question is addressed by Theorem 4.35 within the paper; it is the combinatorial core to which the algebraic problem of Question 4.28 is reduced.
Source paper
On prime Cayley graphs
Maria Chudnovsky, Michal Cizek, Logan Crew, Ján Mináč, Tung T. Nguyen, Sophie Spirkl, Nguyên Duy Tân · 2024-01-11
https://arxiv.org/abs/2401.06062