Edge complexity of graphs

Abstract

Gupta and Iosevich introduced the edge complexity of a graph as the minimum Fourier ratio of its adjacency matrix over all vertex labelings and bounded it below by graph energy divided by the square root of twice the number of edges. We characterize equality for a fixed labeling: the Fourier transform of the adjacency matrix must have at most one nonzero entry in each row and column. This implies regularity, circulancy of every positive even power of an extremizing adjacency matrix, and a parity restriction on connected components, and it gives equality results for certain Laplacian spectral projectors. We construct equality cases from affine involutions on cyclic groups. Singer difference sets yield, for every prime power $q$, an equality-attaining $(q+1)$-regular graph that is not an abelian Cayley graph. We also establish Fourier-ratio estimates for weak, Cartesian, and strong graph products, including preservation of equality under weak products of coprime orders. We use Fourier-ratio recovery as a coding theorem to obtain entropy upper bounds for low-complexity adjacency matrices and complement them with a lower bound obtained by perturbing complete graphs. Finally, a concentration argument shows that if $Np_N/\log N\to\infty$ and $\limsup_{N\to\infty}p_N<1$, then $\operatorname{FR}_{\min}(G(N,p_N))$ is of order $N$ with probability tending to one.