{"id":"arxiv/2609.23842","url":"https://arxiv.org/abs/2609.23842","tags":["math.CO"],"score":0,"title":"Edge complexity of weighted graphs: involutory symmetries and NP-hardness","domain":"math.CO","source":"arxiv","authors":["Vishal Gupta","Alex Iosevich"],"reviews":0,"subject":"math.CO","summary":"The edge complexity of a weighted graph is the smallest ratio of the Fourier $\\ell^1$ and $\\ell^2$ norms of its adjacency matrix over all vertex labelings. We study the difficulty of finding this minimum by relating it to a graph symmetry. Adding a universal vertex with sufficiently large incident weight produces an explicit Fourier $\\ell^1$ lower bound. We show that equality holds exactly when the source graph has a fixed-point-free involutory automorphism. Two-sided estimates compare the excess above this bound with the squared Frobenius distance to the nearest weighted graph having such a…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-20","reactions":{}}