Primeness of tensor products of complete graphs
Question 4.31 · arXiv:2401.06062
Status solved high confidence
With prime meaning module-prime, and apart from convention-dependent graphs of order at most two, the product is prime exactly when d is at least two, every n_i is at least two, and at most one n_i equals two.
Cited literature (1)
-
With prime meaning module-prime, and apart from convention-dependent graphs of order at most two, the product is prime exactly when d is at least two, every n_i is at least two, and at most one n_i equals two.
Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The only ambiguity concerns whether graphs on one or two vertices are called prime.
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