Algebraic Cayley graphs over finite local rings (Q2406686)

\(R\) denotes a finite commutative local ring, with maximal ideal \(M\), the residue field \(k=R/M\) and the reduction map \(^-:R\longrightarrow k\). The authors examine various aspects of the Cayley graph \(G_d(R,f)\), for a regular (\(\overline f\neq 0\)), non-unit polynomial \(f\in R[x]\) and parameters \(1\leq d<n\). Here \(n\) is the degree of a monic irreducible polynomial \(\pi(x)\in R[x]\), such that the residue \(\overline\pi(x)\) is irreducible in \(k[x]\). Such a \(\pi\) comes by way of Hensel's Lemma: \(f(x)=\delta(x)\pi(x)^s+\beta(x)\), \(s\in\mathbb N\). One of the results asserts that \(G_d(R,f)\) is connected if \(ns<(|M||R|)^{d/2}+1\). With the same restriction on \(ns\), an upper bound for the diameter of \(G_d(R,f)\) is given. It is also shown that the graph is an expander graph. In case the local ring has nilpotency two, additional insight into the graph is obtained by way of lifting the graph over its residue field.