The motivation for this question is to find, for a fixed odd $p$ and large $n$, sets $A\subset (\mathbb Z/p\mathbb Z)^n$ with $|A|> cp^n$ for some fixed $c$, where the difference set $A-A:=\{a-a': a, a'\in A\}$ lacks structure (in a way I will not specify here). The aim is to imitate Ruzsa's niveau set construction for $(\mathbb Z/2\mathbb Z)^n$ (cf. Theorem 9.4 of Ben Green's Finite Field Models in Additive Combinatorics).
The objects I'm interested in are Hamming balls $H(k,n,p)$ of radius $k$ around $\mathbf 1 = (1,\dots,1)\in(\mathbb Z/p\mathbb Z)^n$, meaning $H(k,n,p)$ is the set of $(x_1,\dots,x_n)\in (\mathbb Z/p\mathbb Z)^n$ where at most $k$ of the $x_i$ are not equal to $1$. More precisely, I'm interested in the corresponding Cayley graph $\mathcal G_{k,n,p}$ having vertex set $(\mathbb Z/p\mathbb Z)^n$ where two elements $\mathbf x, \mathbf y$ are joined by an edge if $\mathbf x-\mathbf y$ or $\mathbf y-\mathbf x \in H(k,n,p)$.
Question: If $k(n)\to\infty$ as $n\to\infty$, does the chromatic number $\chi(\mathcal G_{k(n),n,3}) $ tend to $\infty$?
I'm mainly interested in $k(n) \approx c\sqrt{n}$ for fixed $c$, but this seems like a natural starting point. I'm also interested the same question about $\chi(\mathcal G_{k(n),n,p})$ for any odd prime $p$.
Useful lower bounds for the chromatic number of $\mathcal G_{k,n,2}$ are known: Igor Kriz and Imre Ruzsa (independently) observed that the Kneser graph $K(n,\lfloor n/2\rfloor -k)$ is a subgraph of $\mathcal G_{2k+1, n,2}$ (cf. Lemma 2.5 here), so Lovász's identification of the chromatic numbers of Kneser graphs proves that $\chi(\mathcal G_{2k+1, n,2})\geq 2k+1$. With this in mind, a natural approach to my question is to identify Kneser graphs with large chromatic number as subgraphs of $\mathcal G_{k,n,3}$. But such Kneser graphs do not seem to be present, at least not in a natural way.
I've looked through the literature that extends and generalizes Lovász's result, hoping to find a result which applies directly to the Cayley graphs in question. I haven't found one yet, or perhaps I'm unable to recognize the connection. One natural approach is to bound the connectivity of the neighborhood complexes corresponding to $\mathcal G_{2k+1,n,3}$, following Lovász's proof. I can't yet do that computation, but I hope that reading Matousek's book on the subject will help.
