Edge complexity of complete bipartite and complete multipartite graphs
Abstract
We study edge complexity, the minimum Fourier ℓ1/ℓ2 ratio of a graph's adjacency matrix over cyclic vertex labelings. For Km,n, with 1≤ m≤ n, we reduce the problem to minimizing the Fourier ℓ1-norm of indicators of m-element subsets of ℤm+n. We prove the sharp bound FRmin(Km,n)≥4n2/((m+n)√(2mn)), with equality precisely when m| n, and classify all labelings attaining it. We determine all Fourier ratios and minimizing labelings for K2,n, and all minimizing labelings for K3,n. Put N=n+3. The optimal three-element sets are precisely the cosets of the subgroup of order $3$ in ℤN when 3| 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.
Related
- Negative edge correlation in complete bipartite graphs
- The Game Chromatic Number of Complete Multipartite Graphs with Singletons and Large Parts
- An e-positive classification for complete multipartite graphs
- Almost Gorenstein edge rings of bipartite graphs and their h-vectors
- Maximal Linear Arrangement is NP complete on Bipartite Graphs
BibTeX
@misc{ferguson2026edge,
title = {{Edge complexity of complete bipartite and complete multipartite graphs}},
author = {S. Ferguson and V. Gupta and A. Iosevich and J. Iosevich and C. Kelly and G. Smith and S. Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36276},
eprint = {2610.36276},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36276},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Edge complexity of complete bipartite and complete multipartite graphs
AU - S. Ferguson
AU - V. Gupta
AU - A. Iosevich
AU - J. Iosevich
AU - C. Kelly
AU - G. Smith
AU - S. Yang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36276
UR - https://arxiv.org/abs/2610.36276
AB - We study edge complexity, the minimum Fourier ℓ^1/ℓ^2 ratio of a graph's adjacency matrix over cyclic vertex labelings. For K_m,n, with 1≤ m≤ n, we reduce the problem to minimizing the Fourier ℓ^1-norm of indicators of m-element subsets of ℤ_m+n. We prove the sharp bound FR_min(K_m,n)≥4n^2/((m+n)√(2mn)), with equality precisely when m| 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 ℤ_N when 3| 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.
ER -