Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
Abstract
In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an 𝒪(√(log n)) approximation on arbitrary graphs on n vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of G= Cayley(Γ, S) is realized by a Fourier character with image size at most four then λ2(G)=SDPGL(G)=ψ(G). Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator s of S by a uniformly random element of its cyclic subgroup (including identity). If rs is the order of s, we let α(rs) to be the average number of ± s steps needed to simulate such a move, and let ρ(S)=maxs∈ Sα(rs) be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character χ* minimizing the auxiliary eigenvalue and taking K=kerχ* gives ψ(G)≤ψG(K)≤q*/(q*−1) ·ρ(S)·SDPGL(G)≤ 2ρ(S)·SDPGL(G), where q*=|χ*(Γ)|. If all generator orders are at most R, this is an R/2 approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly 16/15.
Related
- Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups
- Integrality, smoothness and normality bounds for cube-truncated Hadamard simplices
- Integrality-Gap Bounds for Weighted Matchoids and Matroid Intersection
- Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
- Explicit lower bounds on the conductors of elliptic curves and abelian varieties over number fields
BibTeX
@misc{stamoulis2026integrality,
title = {{Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs}},
author = {Georgios Stamoulis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05368},
eprint = {2609.05368},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05368},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs
AU - Georgios Stamoulis
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05368
UR - https://arxiv.org/abs/2609.05368
AB - In the uniform sparsest cut problem we are asked to find a vertex set that cuts few edges relative to the number of vertex pairs it separates. The Goemans-Linial SDP coupled with the Arora-Rao-Vazirani rounding gives an 𝒪(√(log n)) approximation on arbitrary graphs on n vertices. We study this relaxation on finite Abelian Cayley graphs. First we show that when the second normalized Laplacian eigenvalue of G= Cayley(Γ, S) is realized by a Fourier character with image size at most four then λ_2(G)=SDP_GL(G)=ψ(G). Geometrically, a character maps the vertices onto a regular polygon where the squared chord distance satisfies the triangle inequalities exactly when the polygon has at most four vertices. Grouping equal character fibers gives a cyclic quotient where the optimal cut can be found exactly and so the relaxation is exact on finite Abelian Cayley graphs on groups of exponent at most four. Second, we replace each generator s of S by a uniformly random element of its cyclic subgroup (including identity). If r_s is the order of s, we let α(r_s) to be the average number of ± s steps needed to simulate such a move, and let ρ(S)=max_s∈ Sα(r_s) be its worst case. Full cyclic averaging eliminates character phases and choosing a nontrivial character χ^* minimizing the auxiliary eigenvalue and taking K=kerχ^* gives ψ(G)≤ψ_G(K)≤q^*/(q^*−1) ·ρ(S)·SDP_GL(G)≤ 2ρ(S)·SDP_GL(G), where q^*=|χ^*(Γ)|. If all generator orders are at most R, this is an R/2 approximation. Finally, we construct an infinite family of finite Abelian Cayley graphs with Goemans-Linial integrality gap exactly 16/15.
ER -