A New Family of Algebraically Defined Graphs With Small Automorphism Group

Abstract

Let $p$ be an odd prime, $q=p^e$, $e\ge 1$, and $\mathbb{F}={\mathbb{F}}_q$ denote the finite field of $q$ elements. Let $f:{\mathbb{F}}^2\to \mathbb{F}$ and $g:{\mathbb{F}}^3\to \mathbb{F}$ be functions, and let $P$ and $L$ be two copies of the 3-dimensional vector space ${\mathbb{F}}^3$. Consider a bipartite graph ${\Gamma }_{\mathbb{F}}(f,g)$ with vertex partitions $P$ and $L$ and with edges defined as follows: for every $(p)=(p_1,p_2,p_3)\in P$ and every $[l]=[l_1,l_2,l_3]\in L$, $\{(p),[l]\}=(p)[l]$ is an edge in ${\Gamma }_{\mathbb{F}}(f,g)$ if $$p_2+l_2=f(p_1,l_1)\text{and}{p}_3+l_3=g(p_1,p_2,l_1).$$ Given ${\Gamma }_{\mathbb{F}}(f,g)$, is it always possible to find a function $h:{\mathbb{F}}^2\to \mathbb{F}$ such that the graph ${\Gamma }_{\mathbb{F}}(f,h)$ with the same vertex set as ${\Gamma }_{\mathbb{F}}(f,g)$ and with edges $(p)[l]$ defined in a similar way by the system $$p_2+l_2=f(p_1,l_1)\text{and}{p}_3+l_3=h(p_1,l_1),$$ is isomorphic to ${\Gamma }_{\mathbb{F}}(f,g)$ for infinitely many $q$? In this paper we show that the answer to the question is negative and the graphs ${\Gamma }_{{\mathbb{F}}_p}(p_1{\ell }_1,p_1{\ell }_1{p}_2(p_1+p_2+p_1{p}_2))$ provide such an example for $p\equiv 1(\mathrm{mod}3)$. Our argument is based on proving that the automorphism group of these graphs has order $p$, which is the smallest possible order of the automorphism group of graphs of the form ${\Gamma }_{\mathbb{F}}(f,g)$.

25 pages