Edge complexity of complete bipartite and complete multipartite graphs

Abstract

We study edge complexity, the minimum Fourier $\ell^1/\ell^2$ ratio of a graph's adjacency matrix over cyclic vertex labelings. For $K_{m,n}$, with $1\leq m\leq n$, we reduce the problem to minimizing the Fourier $\ell^1$-norm of indicators of $m$-element subsets of $\mathbb Z_{m+n}$. We prove the sharp bound $\operatorname{FR}_{\min}(K_{m,n})\geq\frac{4n^2}{(m+n)\sqrt{2mn}}$, with equality precisely when $m\mid n$, and classify all labelings attaining it. We determine all Fourier ratios and minimizing labelings for $K_{2,n}$, and all minimizing labelings for $K_{3,n}$. Put $N=n+3$. The optimal three-element sets are precisely the cosets of the subgroup of order $3$ in $\mathbb Z_N$ when $3\mid N$, and precisely the arithmetic progressions with invertible common difference otherwise. The triple classification uses polynomial minorants and additive energies. We prove that attainment of the graph-energy bound is invariant under uniform independent set blow-ups. Edge complexity itself can decrease by an arbitrarily large factor under a twofold blow-up, and we give a finite example. For complete multipartite graphs, we give an exact labeling formula and sharp lower bound, and classify all part sizes and labelings attaining that bound. This bound strictly improves the graph-energy bound when the part sizes are unequal. We prove a lower bound for arbitrary simple graphs in terms of their average degree and maximum absolute degree deviation. For Laplacian projectors, we apply the equality criterion for the multiplicity bound to unbalanced complete bipartite graphs, whose top-projector minimum reduces to the same set minimization. Finally, we apply existing Fourier recovery and sampling theorems to approximate a graph from random adjacency samples under a fixed known labeling with bounded Fourier ratio, bounding the number of incorrectly recovered edges.