Spectral and combinatorial properties of some algebraically defined graphs (Q668032)

Summary: Let \(k\geq 3\) be an integer, \(q\) be a prime power, and \(\mathbb{F}_q\) denote the field of \(q\) elements. Let \(f_i, g_i\in\mathbb{F}_q[X]\), \(3\leq i\leq k\), such that \(g_i(-X) = -\, g_i(X)\). We define a graph \(S(k,q) = S(k,q;f_3,g_3,\dots,f_k,g_k)\) as a graph with the vertex set \(\mathbb{F}_q^k\) and edges defined as follows: vertices \(a = (a_1,a_2,\dots,a_k)\) and \(b = (b_1,b_2,\dots,b_k)\) are adjacent if \(a_1\neq b_1\) and the following \(k-2\) relations on their components hold: \[ b_i-a_i = g_i(b_1-a_1)f_i\bigg(\frac{b_{2}-a_{2}}{b_{1}-a_{1}}\bigg),\quad 3\leq i\leq k. \] We show that the graphs \(S(k,q)\) generalize several recently studied examples of regular expanders and can provide many new such examples.