Edge complexity of weighted graphs: involutory symmetries and NP-hardness
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.23842
curl -X POST /api/v1/records/arxiv/2609.23842/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.23842/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'