Spectral and Combinatorial Properties of Some Algebraically Defined Graphs

08/25/2017
by   Sebastian M. Cioabă, et al.
0

Let k> 3 be an integer, q be a prime power, and F_q denote the field of q elements. Let f_i, g_i∈F_q[X], 3< i< k, such that g_i(-X) = - g_i(X). We define a graph S(k,q) = S(k,q;f_3,g_3,...,f_k,g_k) as a graph with the vertex set F_q^k and edges defined as follows: vertices a = (a_1,a_2,...,a_k) and b = (b_1,b_2,...,b_k) are adjacent if a_1 b_1 and the following k-2 relations on their components hold: b_i-a_i = g_i(b_1-a_1)f_i(b_2-a_2/b_1-a_1) , 3< i< k. We show that graphs S(k,q) generalize several recently studied examples of regular expanders and can provide many new such examples.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset