Spectral and Combinatorial Properties of Some Algebraically Defined Graphs
Spectral and Combinatorial Properties of Some Algebraically Defined Graphs
复制标题
DOI：
10.37236/7950
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
S. Cioabă;F. Lazebnik;Shuying Sun
中科院分区：
文献类型：
--
作者：
S. Cioabă;F. Lazebnik;Shuying Sun
设$k\ge 3$为整数，$q$为素数幂，$\mathbb{F}_q$表示$q$元素的域。设$f_i，g_i\in\mathbb{F}_q[X]$，$3\le i\le k$，使得$g_i(-X)=-\，g_i(X)$。定义了图$S(k，q)=S(k，q；图F_3，g_3，f_k，g_k)$具有顶点集$\mathbb{F}_q^k$，边定义如下：顶点$a=(a_1，a_2，a_k)$和$b=(b_1，b_2，\ldots，B_k)$是相邻的，如果$a_1\ne b_1$和它们的分量上的下列$k-2$关系成立：$$b_i-a_i=g_i(b_1-a_1)f_i\Bigl(\frac{b_2-a_2}{b_1-a_1}\Bigr)\；，Quad 3\le i\le k.$$我们证明了图$S(k，q)$推广了最近研究的几个正则扩张器的例子，并且可以提供许多新的例子。
Let $k\ge 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\le i\le k$, such that $g_i(-X) = -\, g_i(X)$. We define a graph $S(k,q) = S(k,q;f_3,g_3,\cdots,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,\ldots,a_k)$ and $b = (b_1,b_2,\ldots,b_k)$ are adjacent if $a_1\ne b_1$ and the following $k-2$ relations on their components hold:$$b_i-a_i = g_i(b_1-a_1)f_i\Bigl(\frac{b_2-a_2}{b_1-a_1}\Bigr)\;,\quad 3\le i\le k.$$ We show that the graphs $S(k,q)$ generalize several recently studied examples of regular expanders and can provide many new such examples.