% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all commands that change parameters such as % margins or page sizes. % Packages amssymb and amsthm are already loaded. % We recommend these AMS packages: \usepackage{amsmath,amssymb} % We recommend the graphicx package for importing figures: \usepackage{graphicx} % Use this command to create hyperlinks (optional and recommended): \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % Theorem-like environments that are declared in the style file are: % theorem, lemma, corollary, proposition, fact, observation, claim, % definition, example, conjecture, open, problem, question, remark, note \newcommand{\ch}{{\rm char}} \newcommand{\al}{\ensuremath{\alpha}} \newcommand{\be}{\ensuremath{\beta}} \newcommand{\ld}{\ensuremath{\lambda}} \newcommand{\Ga}{\ensuremath{\Gamma}} \newcommand{\rank}{{\rm rank}} \newcommand{\tr}{{\rm tr}} \newcommand{\ex}{{\rm ex}} \newcommand{\F}{\mathbb{F}} \allowdisplaybreaks \theoremstyle{plain} \newtheorem{thm}{Theorem}[section] %\newtheorem{corollary}[theorem]{Corollary} \newtheorem{conj}[thm]{Conjecture} \newtheorem{exa}{Example}[section] \newtheorem{lem}[thm]{Lemma} %\newtheorem{proposition}[theorem]{Proposition} %\newtheorem{claim}{Claim} %\newtheorem{definition}[theorem]{Definition} \newtheorem{rk}{Remark}[section] %%%%%%%%%%%%%METADATA%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Give the submission and acceptance dates in the format shown. % The editors will insert the publication date in the third argument. \dateline{June 2, 2018}{December 3, 2018}{TBD} % Give one or more subject codes separated by commas. % Codes are available from http://www.ams.org/mathscinet/freeTools.html \MSC{05C88, 05C89} % Uncomment exactly one of the following copyright statements. Alternatively, % you can write your own copyright statement subject to the approval of the journal. % See https://creativecommons.org/licenses/ for a full explanation of the % Creative Commons licenses. % % We strongly recommend CC BY-ND or CC BY. Both these licenses allow others % to freely distribute your work while giving credit to you. The difference between % them is that CC BY-ND only allows distribution unchanged and in whole, while % CC BY also allows remixing, tweaking and building upon your work. % % One author: %\Copyright{The author.} %\Copyright{The author. Released under the CC BY license (International 4.0).} %\Copyright{The author. Released under the CC BY-ND license (International 4.0).} % More than one author: %\Copyright{The authors.} %\Copyright{The authors. Released under the CC BY license (International 4.0).} \Copyright{ The authors. Released under the CC BY-ND license (International 4.0).} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % If needed, include a line break (\\) at an appropriate place in the title. \title{Spectral and Combinatorial Properties of Some Algebraically Defined Graphs} % Input author, affiliation, address and support information as follows; % The address should include the country, but does not have to include % the street address. Give at least one email address. \author{Sebastian M. Cioab\u{a}\thanks{The research of the first author was supported by the grants NSF DMS-1600768 and CIF-1815922. .}\\ \small Department of Mathematical Sciences\\[-0.8ex] \small University of Delaware\\[-0.8ex] \small Newark, U.S.A.\\ \small\tt cioaba@udel.edu\\ \and Felix Lazebnik\thanks{The second author was supported by the Simons Foundation grant \#426092.}\\ \small Department of Mathematical Sciences\\[-0.8ex] \small University of Delaware\\[-0.8ex] \small Newark, U.S.A.\\ \small\tt cioaba@udel.edu\\ \and Shuying Sun\\ \small Department of Mathematical Sciences\\[-0.8ex] \small University of Delaware\\[-0.8ex] \small Newark, U.S.A.\\ \small\tt shuying@udel.edu} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract may be distributed without the rest of the % paper so it must be entirely self-contained. Try to include all words % and phrases that someone might search for when looking for your paper. \begin{abstract} 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 $\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 graphs $S(k,q)$ generalize several recently studied examples of regular expanders and can provide many new such examples.\end{abstract} \section{Introduction and Motivation}\label{Intro} All graphs in this paper are simple, i.e., undirected, with no loops and no multiple edges. See, e.g., Bollob\'as \cite{Bol98} for standard terminology. Let $\Gamma = (V,E)$ be a graph with vertex set $V$ and edge set $E$. We refer to $|V|$ and $|E|$ as the order and the size of $\Gamma$, respectively. For a subset of vertices $A$ of $V$, $\partial A$ denotes the set of edges of $\Gamma$ with one endpoint in $A$ and the other endpoint in $V\setminus A$. The Cheeger constant $h(\Gamma)$ (also known as the edge-isoperimetric number) of $\Gamma$, is defined by $h(\Gamma) := \min\Bigl\{\frac{|\partial{A}|}{|A|} : A \subseteq V, 0 < |A| \le \frac{1}{2}|V| \Bigr\}.$ The graph $\Gamma$ is $d$-regular if each vertex is adjacent to exactly $d$ others. An infinite family of expanders is an infinite family of regular graphs whose Cheeger constants are uniformly bounded away from 0. More precisely, for $n\geq 1$, let $\Gamma_n = (V_n, E_n)$ be a sequence of graphs such that each $\Gamma_n$ is $d_n$-regular and $|V_n| \rightarrow \infty$ as $n\rightarrow\infty$. We say that the members of the sequence form a family of expanders if the corresponding sequence $\bigl(h(\Gamma_n)\bigr)_{n\geq 1}$ is bounded away from zero, i.e., there exists a real number $c > 0$ such that $h(\Gamma_n) \ge c$ for all $n\geq 1$. In general, one would like the valency sequence $(d_n)_{n\geq 1}$ to be growing slowly with $n$, and ideally, to be bounded above by a constant. For examples of families of expanders, their theory and applications, see Davidoff, Sarnak and Valette \cite{DSV}, Hoory, Linial and Wigderson \cite{HLW}, and Krebs and Shaheen \cite{KS11}. The adjacency matrix $A=A(\Gamma)$ of a graph $\Gamma=(V,E)$ has its rows and columns labeled by $V$ and $A(x,y)$ equals the number of edges between $x$ and $y$. When $\Gamma$ is simple, the matrix $A$ is symmetric and therefore, its eigenvalues are real numbers. For $j$ between $1$ and $|V|$, let $\lambda_j=\lambda_j(\Gamma)$ denote the $j$-th eigenvalue of $A$. In general, it is hard to compute $h(\Gamma)$, but the second-largest eigenvalue $\lambda_2(\Gamma)$ can be used to get an estimate for $h(\Gamma)$. If $\Gamma$ is a connected $d$-regular graph, then $\frac{1}{2}\big(d-\lambda_2\big) \le h(\Gamma) \le \sqrt{d^2-\lambda_2^2}$. The lower bound was proved by Dodziuk \cite{Dod84} and independently by Alon-Milman \cite{ALM85} and by Alon \cite{AL86}. In both \cite{ALM85} and \cite{AL86}, an upper bound of $\sqrt{2d(d-\lambda_2)}$ was provided. Mohar \cite{Mo89} improved the upper bound to the one indicated above. See Brouwer and Haemers \cite{BH11}, \cite{HLW}, \cite{KS11} for terminology and results on spectral graph theory and connections between eigenvalues and expansion properties of graphs. The difference $d- \lambda_2$ which is present in both sides of the inequalities above, also known as the spectral gap of $\Gamma$, provides an estimate on the expansion ratio of the graph. In particular, for an infinite family of $d$-regular graphs $\Gamma_n$, the sequence $\bigl(h(\Gamma_n)\bigr)$ is bounded away from zero if and only if the sequence $\bigl(d-\lambda_2(\Gamma_n)\bigr)$ is bounded away from zero. A connected $d$-regular graph $\Gamma$ is called {\it Ramanujan} if $\lambda_2(\Gamma)\le 2\sqrt{d-1}$. Alon and Boppana \cite{Nil91} proved that this bound is best possible and their results imply that for any infinite family of connected $d$-regular graphs $\Gamma_n$, $\lambda_2(\Gamma_n) \ge 2\sqrt{d-1} - o_n(1)$, where $o_n(1)$ is a term that goes to $0$ as $n$ goes to infinity. For functions $f, g : \mathbb{N}\rightarrow \mathbb{R}^+$, we write $f = o_n(g)$ if $f(n)/g(n) \rightarrow 0$ as $n\rightarrow \infty$. For the rest of the paper, let $q=p^e$, where $p$ is a prime and $e$ is a positive integer. For a sequence of prime powers $(q_m)_{m\ge 1}$, we always assume that $q_m = p_m^{e_m}$, where $p_m$ is a prime and $e_m\ge 1$. Let $\F_q$ be the finite field of $q$ elements and $\F_q^k$ be the cartesian product of $k$ copies of $\F_q$. Clearly, $\F_q^k$ is a vector space of dimension $k$ over $\F_q$. For $2\leq i\leq k$, let $h_i$ be an arbitrary polynomial in $2i-2$ indeterminants over $\F_q$. We define the bipartite graph $B\Gamma_k = B\Gamma (q;h_2,\ldots, h_k)$, $k\ge 2$, as follows. The vertex set of $B\Gamma_k$ is the disjoint union of two copies of $\F_q^k$, one denoted by $P_k$ and the other by $L_k$. We define edges of $B\Gamma_k$ by declaring vertices $p=(p_1,p_2,\ldots,p_k)\in P_k$ and $l=(l_1,l_2,\ldots,l_k)\in L_k$ to be adjacent if the following $k-1$ equations are satisfied: \begin{equation}\label{Bipmain} p_i + l_i = h_i(p_1,l_1,p_2,l_2, \ldots, p_{i-1},l_{i-1}), \;i=2,\ldots, k. \end{equation} The graphs $B\Gamma_k$ were introduced by Lazebnik and Woldar \cite{LW01}, as generalizations of graphs introduced by Lazebnik and Ustimenko in \cite{LazUst} and \cite{LazUstDkq}. For surveys on these graphs and their applications, see Lazebnik and Woldar \cite{LW01}, and Lazebnik, Sun and Wang \cite{LaSuWa17}. An important property of graphs $B\Gamma_k$ \cite{LW01} is that for every vertex $v$ of $B\Gamma_k$ and every $\alpha \in \F_q$, there exists a unique neighbor of $v$ whose first coordinate is $\alpha$. This implies that each $B\Gamma_k$ is $q$-regular of order $2q^k$ and size $q^{k+1}$. The spectral and combinatorial properties of three specializations of graphs $B\Gamma_k$ have received particular attention in recent years. Cioab\u{a}, Lazebnik and Li \cite{CiLaLi14} determined the complete spectrum of the {\it Wenger} graphs $W_{k}(q) = B\Gamma (q;h_2,\ldots, h_{k+1})$ with $h_i= p_1l_1^{i-1}$, $2\le i \le k+1$. Cao, Lu, Wan, Wang and Wang \cite{Liping15} determined the eigenvalues of the {\it linearized Wenger} graphs $L_{k}(q) = B\Gamma (q;h_2,\ldots, h_{k+1})$ with $h_i= p_1^{p^{i-2}}l_1$, $2\le i \le k+1$, and Yan and Liu \cite{YanLiu17} determined the multiplicities of these eigenvalues. Moorhouse, Sun and Williford \cite{MoorSunWil16} studied the spectra of graphs $D(4,q) = B\Gamma (q; p_1l_1, p_1l_2, p_2l_1)$, and in particular, proved that the second largest eigenvalues of these graphs are bounded from above by $2\sqrt{q}$ (so $D(4,q)$ is `close' to being Ramanujan). Let $V_1$ and $V_2$ denote the partite sets or color classes of the vertex set of a bipartite graph $\Gamma$. The distance-two graph $\Gamma^{(2)}(V_1)$ of $\Gamma$ induced on $V_1$ (also known as the halved graph of $\Gamma$ induced on $V_1$) is the graph having $V_1$ as its vertex set with the adjacency defined as follows: two vertices $x\neq y\in V_1$ are adjacent if $x$ and $y$ are at distance two in $\Gamma$. One can define the distance-two graph or halved graph $\Gamma^{(2)}(V_2)$ of $\Gamma$ induced on $V_2$ in a similar way. Depending on the context, the halved graphs $\Gamma^{(2)}(V_1)$ and $\Gamma^{(2)}(V_2)$ are sometimes called the point graph and the block graph of $\Gamma$, respectively (see \cite[p.127]{BH11} for example). If $\Gamma$ is $d$-regular and contains no 4-cycles, then $\Gamma^{(2)}(V_1)$ is a $d(d-1)$-regular simple graph. There is a simple connection between the eigenvalues of $\Gamma$ and the eigenvalues of $\Gamma^{(2)}(V_j)$ (see, e.g., \cite{CiLaLi14}): every eigenvalue $\lambda$ of $\Gamma^{(2)}(V_j)$ with multiplicity $m$ corresponds to a pair of eigenvalues $\pm\sqrt{\lambda + d}$ of $\Gamma$, each with multiplicity $m$ (or a single eigenvalue $0$ of multiplicity $2m$ in the case $\lambda=-d)$. This relation between the spectra of $q$-regular bipartite graph $\Gamma$ and its $q(q-1)$-regular distance-two graphs $\Gamma^{(2)}(V_1)$ or $\Gamma^{(2)}(V_2)$ has been utilized in each of the papers \cite{CiLaLi14,Liping15,MoorSunWil16} in order to find or to bound $\lambda_2(\Gamma)$ and use this information to assert the expansion property of $\Gamma$. In each of these cases, the distance-two graph of one of the color classes turned out to be a Cayley graph of a group which allowed the use of representation theory to compute its spectrum. In \cite{Liping15,CiLaLi14} the group turned out be abelian, while in \cite{MoorSunWil16} it was not abelian for odd $q$. The main motivation behind the construction below is to directly generalize the defining systems of equations for some of the distance-two graphs of $W_k(q)$ and $L_k(q)$, thereby obtaining a family of $q(q-1)$-regular Cayley graphs of abelian groups. By the adverb {\em directly} used in the previous sentence, we mean to stress that the graphs we build are {\em not necessarily distance-two graphs of $q$-regular bipartite graphs~$\Gamma$}. Such examples will be discussed in Remark \ref{NonBip} of Section \ref{CONREM}. \section{Main Results}\label{MR} In this section, we define the main object of this paper, the family of graphs $S(k,q),$ and we describe our main results. Let $k$ be an integer, $k\ge 3$. Let $f_i, g_i\in\mathbb{F}_q[X]$, $3\le i\le k$, be $2(k-2)$ homogeneous polynomials of degrees at most $q-1$ such that $g_i(-X) = -\,g_i(X)$ for each $i$. %07-13 we decided to erase the following sentence, and change the previous one. %We may assume that $f_i$ and $g_i$ are polynomials of degree at most $q-1$ since $a^q=a$ for all $a\in \F_q$. %Let $V_k$ be the $k$-dimensional vector space over the finite field $\mathbb{F}_q$. We define $S(k,q) = S(k,q; f_3,g_3,\cdots,f_k,g_k)$ as the graph with the vertex set $\F_q^k$ and edges defined as follows: $a = (a_1,a_2,\ldots,a_k)$ is adjacent to $b = (b_1,b_2,\ldots,b_k)$ if $a_1\ne b_1$ and the following $k-2$ relations on their coordinates hold: \begin{equation}\label{S2SS1:relation} 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. \end{equation} Clearly, the requirement $g_i(-X)= -\, g_i(X)$ is to ensure that adjacency in $S(k,q)$ be symmetric. One can easily see that $S(k,q)$ is a Cayley graph with the underlying group $G$ being the additive group of the vector space $\F_q^k$ with generating set $$ \left\{ \bigl(a, au, g_3(a)f_3(u), \cdots, g_k(a)f_k(u)\bigr) \ |\ a\in\F_q^*, u\in\F_q\right\}. $$ This implies that $S(k,q)$ is a vertex transitive $q(q-1)$-regular graph. Note that for $f_i= X^{i-1}$ and $g_i= X$, $3\le i\le k+1$, $S(k+1,q)$ coincides with the distance-two graph of the Wenger graphs $W_k(q)$ induced on lines and for $f_i=X^{p^{i-2}}$ and $g_i= X$, $3\le i\le k+1$, $S(k+1,q)= L^{(2)}_k(q)$ coincides with distance-two graph of the linearized Wenger graphs $L_k(q)$ also induced on lines. In order to present our results, we need a bit more notation. For any $\alpha\in\F_q$, let $Tr(\alpha) = \alpha+ \alpha^p + \cdots +\alpha^{p^{e-1}}$ be the {\em trace of $\alpha$ over $\F_p$}. It is known that $Tr(\alpha)\in \F_p$. For any element $\beta\in \F_p$, let $\beta^*$ denote the unique integer such that $0\le \beta^* 1$, then $(d_g-1)\sqrt{q}+1 < q-1$ as $d_g < p$. Therefore, $\lambda_w < q(q-1)$. For $e = 1$, we consider the following two cases: $q = p = 2$ and $q = p\ge 3$. If $q = p = 2$, then $d_g = 1$ as $d_g < p$, and hence $|S_w| = 0$. Therefore, $\lambda_w < q(q-1)$. If $q= p \ge 3$, then, as $\lambda_w$ is a real number and $|z_u| \le p-1$, we have $$\lambda _w \le |\lambda_w| = |\sum_{u\in\F_p} z_u| \le \sum_{u\in\F_p} |z_u| \le p(p-1),$$ and $\lambda _w = p(p-1)$ if and only if $z_u=p-1$ for all $u\in\F_p$. The latter condition is equivalent to $$Tr\Big( a\bigl[w_1+uw_2+\sum\limits_{i=3}^{k}c_{i,1}f_{i}(u)w_{i}\bigr] +a^2\sum\limits_{i=3}^{k}c_{i,2}f_{i}(u)w_{i}+ \cdots+a^{d_g}\sum\limits_{i=3}^{k}c_{i,d_g}f_{i}(u)w_{i} \Big)=0 $$ for all $u\in\F_p$. For $x\in \F_p$, $Tr(x) = 0$ if and only if $x=0$. This implies that $$a\bigl[w_1+uw_2+\sum\limits_{i=3}^{k}c_{i,1}f_{i}(u)w_{i}\bigr] +a^2\sum\limits_{i=3}^{k}c_{i,2}f_{i}(u)w_{i}+\cdots+a^{d_g}\sum\limits_{i=3}^{k}c_{i,d_g}f_{i}(u)w_{i} =0$$ for any $a\in \F_p^*$. Therefore, the polynomial $$X\bigl[w_1+uw_2+\sum\limits_{i=3}^{k}c_{i,1}f_{i}(u)w_{i}\bigr] +X^2\sum\limits_{i=3}^{k}c_{i,2}f_{i}(u)w_{i}+\cdots+X^{d_g}\sum\limits_{i=3}^{k}c_{i,d_g}f_{i}(u)w_{i},$$ which is over $\F_p$, has $p$ distinct roots in $\F_p$ and is of degree at most $d_g$, $d_g< p$. Hence, it must be zero polynomial, and so $N_p=p$, a contradiction. Hence, $\lambda_w