Nonexistence of almost Moore digraphs of diameter three (Q1010813)

Summary: Almost Moore digraphs appear in the context of the degree/diameter problem as a class of extremal directed graphs, in the sense that their order is one less than the unattainable Moore bound \(M(d,k)=1+d+\dots +d^k\), where \(d>1\) and \(k>1\) denote the maximum out-degree and diameter, respectively. So far, the problem of their existence has only been solved when \(d=2,3\) or \(k=2\). In this paper, we prove that almost Moore digraphs of diameter \(k=3\) do not exist for any degree \(d\). The enumeration of almost Moore digraphs of degree \(d\) and diameter \(k=3\) turns out to be equivalent to the search of binary matrices \(A\) fulfilling that \(AJ=dJ\) and \(I+A+A^2+A^3=J+P\), where \(J\) denotes the all-one matrix and \(P\) is a permutation matrix. We use spectral techniques in order to show that such equation has no \((0,1)\)-matrix solutions. More precisely, we obtain the factorization in \({\mathbb Q}[x]\) of the characteristic polynomial of \(A\), in terms of the cycle structure of \(P\), we compute the trace of \(A\) and we derive a contradiction on some algebraic multiplicities of the eigenvalues of \(A\). In order to get the factorization of \(\det(xI-A)\) we determine when the polynomials \(F_n(x)=\Phi_n(1+x+x^2+x^3)\) are irreducible in \({\mathbb Q}[x]\), where \(\Phi_n(x)\) denotes the \(n\)-th cyclotomic polynomial, since in such case they become `big pieces' of \(\det(xI-A)\). By using concepts and techniques from algebraic number theory, we prove that \(F_n(x)\) is always irreducible in \({\mathbb Q}[x]\), unless \(n=1,10\). So, by combining tools from matrix and number theory we have been able to solve a problem of graph theory.