A New Family of Algebraically Defined Graphs with Small Automorphism Group

Abstract

Let $p$ be an odd  prime, $q=p^e$, $e \geq 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).$$The following question  appeared in Nassau: 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_1p_2(p_1 + p_2 + p_1p_2))$ provide such an example for $p \equiv 1 \pmod{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)$.