Proof of a conjecture on monomial graphs

Abstract

Let $e$ be a positive integer, $p$ be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of $q$ elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G=G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. Motivated by some questions in finite geometry and extremal graph theory, Dmytrenko, Lazebnik and Williford conjectured in 2007 that if $f$ and $g$ are both monomials and $G$ has no cycle of length less than eight, then $G$ is isomorphic to the graph $G_q(XY,X{Y}^2)$. They proved several instances of the conjecture by reducing it to the property of polynomials $A_k=X^k[(X+1{)}^k-X^k]$ and $B_k=[(X+1{)}^{2k}-1]X^{q-1-k}-2X^{q-1}$ being permutation polynomials of ${\mathbb{F}}_q$. In this paper we prove the conjecture by obtaining new results on the polynomials $A_k$ and $B_k$, which are also of interest on their own.

22 pages