PaperlayerView exact revision on arXiv

Source-linked AI summary

Integrality Gap Bounds for the Goemans-Linial SDP on Finite Abelian Cayley Graphs

Georgios Stamoulis

arXiv:2609.05368v1math.COcs.DMcs.DS

TL;DR

The paper asks how tightly the Goemans–Linial SDP approximates uniform sparsest cut on finite Abelian Cayley graphs. It analyzes low-order Fourier characters and cyclic averaging, proving exactness in several cases and constructing an infinite family with integrality gap 16/15. The framework gives explicit approximation bounds but does not determine the worst possible gap.

  • Problem

    The paper studies the integrality gap of the Goemans–Linial SDP for uniform sparsest cut on finite Abelian Cayley graphs.

  • Method

    The paper uses Fourier-character geometry, cyclic quotient rounding, and cyclic averaging over each generator’s subgroup to compare SDP and cut values.

  • Results

    The relaxation is exact when a λ2-realizing character has image size at most four, while an infinite connected family has integrality gap exactly 16/15.

  • Takeaways & Limitations

    The framework gives exact solutions for several Abelian Cayley graph families and explicit cyclic-averaging bounds, while showing that the relaxation is not universally exact.

  • Takeaways & Limitations

    The framework does not determine the worst possible Goemans–Linial gap on Abelian Cayley graphs.

Abstract

from arXiv · show

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 $\mathcal{O}(\sqrt{\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= \mathrm{Cayley}(Γ, S)$ is realized by a Fourier character with image size at most four then $λ_2(G)=\mathrm{SDP}_{\mathrm{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 $\pm s$ steps needed to simulate such a move, and let $ρ(S)=\max_{s\in 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=\mathrm{ker}χ^*$ gives \[ ψ(G)\leqψ_G(K)\leq\frac{q^*}{q^*-1} \cdotρ(S)\cdot\mathrm{SDP}_{\mathrm{GL}}(G)\leq 2ρ(S)\cdot\mathrm{SDP}_{\mathrm{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$.

1 Introduction

The paper studies the Goemans–Linial SDP for uniform sparsest cut on finite Abelian Cayley graphs, exploiting Fourier characters and cyclic quotients. It proves exactness for low-order character images, develops cyclic averaging bounds, and constructs an infinite family with gap 16/15.

  • Problem setting: Uniform sparsest cut minimizes the ratio of edges cut to separated vertex pairs, while the Goemans–Linial SDP and ARV rounding give an O(√log n) approximation on general graphs.The paper focuses on uniform demands and finite Abelian Cayley graphs, whose Fourier characters explicitly diagonalize random walks.
  • Fourier-character geometry: A character attaining λ2 need not yield a feasible Goemans–Linial solution because its squared chord distances may violate triangle inequalities.Character images form regular polygons, and the squared chord distance is feasible exactly through the four-vertex threshold.
  • Exact low-order rounding: For a λ2-realizing character with image size q ≤4, kernel rounding is optimal for q ∈ {2, 3}, while a half-circle quotient cut is optimal for q = 4.Thus λ2(G), SDPGL(G), and ψ(G) coincide in these cases.
  • Exact low-order rounding: If exp(Γ) ≤4, every Cayley graph on Γ satisfies λ2(G) = SDPGL(G) = ψ(G).The geometric threshold follows because squared chord distances on a regular q-gon satisfy all triangle inequalities exactly when q ≤4.
  • Cyclic averaging: Cyclic averaging replaces each generator by a uniformly random element of its cyclic subgroup, with ρ(S) measuring the worst transfer cost for the Goemans–Linial objective.The construction removes character phases and supports kernel rounding after selecting a character minimizing the auxiliary eigenvalue.
  • Cyclic averaging: The resulting procedure gives a polynomial-time 2ρ(S)-approximation without solving the SDP, and its metric-comparison loss α(r) is optimal even over cut metrics on Z_r.For prime-exponent vector spaces, the stated bound is ψ(G)/SDPGL(G) ≤ p/(p−1) · α(p) = p+1, independently of degree.
  • Non-exactness and scope: The paper constructs a 10-vertex Abelian Cayley graph with integrality gap 16/15, whose Cartesian powers form an infinite connected family with the same gap.This establishes non-exactness of the relaxation on connected Abelian Cayley graphs while leaving the worst possible gap unresolved.

2 Preliminaries

The preliminaries define finite Abelian Cayley graphs, Fourier characters, uniform sparsity, and the Goemans–Linial SDP. They establish the spectral interpretation of character metrics and the basic relationship among the Laplacian, relaxation, and cut optima.

  • Finite Abelian Cayley graphs use group elements as vertices and multiset elements as allowed random-walk steps.
  • Fourier characters: Fourier characters diagonalize the normalized random-walk operator, giving explicit eigenvalues for Abelian Cayley graphs.
  • Uniform sparsest cut: Uniform sparsity is the ratio of average edge-crossing distance to average all-pairs separation distance, minimized over nontrivial cuts.
  • Goemans–Linial SDP: The Goemans–Linial relaxation replaces cut metrics with squared Euclidean semimetrics that also satisfy triangle inequalities.
  • Character metrics: For every nontrivial character, its metric has normalized edge value 2λχ(G) and all-pairs value 2, so its objective equals the character eigenvalue.
  • Character metrics: A minimizing character certifies SDPGL(G) = λ2(G) when its squared-chord metric satisfies the triangle inequalities.

3 Quotient rounding

Quotient rounding collapses character fibers to a cyclic Cayley quotient and lifts quotient cuts back to the original graph without changing sparsity. The resulting bounds relate the global optimum, quotient optimum, and kernel cut.

  • Character quotient: A character quotient collapses cosets of its kernel into a cyclic Cayley graph on Zq while preserving projected step multiplicities.
  • Character quotient: Quotient subsets are lifted by taking the full preimage under the character map.
  • Exact pullback: Every nonempty proper quotient cut has exactly the same sparsity as its pullback to the original graph.
  • Quotient rounding: The quotient-rounding value is the minimum sparsity of a nontrivial cut in the cyclic quotient.
  • Quotient rounding: For every nontrivial character χ, ψ(G) ≤ Round(χ) ≤ ψG(ker χ).

4 Exactness from low-order characters

Low-order Fourier characters make the Goemans–Linial relaxation exact because their regular-polygon squared-chord metrics are feasible and can be rounded through cyclic quotients without loss. Consequently, exponent-at-most-four Abelian Cayley graphs satisfy equality among spectral, SDP, and cut optima.

  • Geometric threshold: Squared chordal distances on a regular q-gon satisfy all triangle inequalities exactly when q ≤4.For q=4, the only nontrivial inequality is the tight relation 4=2+2; for q≥5, three consecutive vertices violate it.
  • Geometric threshold: A character with image size at most four therefore induces a feasible Goemans–Linial metric.The character image is a regular polygon, so the geometric threshold directly determines feasibility.
  • Lossless quotient rounding: If a bottom nontrivial character has image size at most four, quotient rounding produces a cut with sparsity at most its character eigenvalue.For q=2 or 3 the kernel is optimal; for q=4, the better of two half-circle cuts is sufficient.
  • Exactness theorem: When λ2(G) is realized by such a character, λ2(G)=SDP_GL(G)=ψ(G), and the optimal cut is explicitly obtained from the character quotient.Feasibility gives the SDP upper bound, while the spectral lower bound and quotient cut force equality.
  • Exactness theorem: Every finite Abelian Cayley graph on a group of exponent at most four is exact for the Goemans–Linial relaxation.All character image sizes divide the group exponent and are therefore at most four.
  • Lossless quotient rounding: Kernel rounding alone is not always exact at image size four: on C4 it gives sparsity 4/3, while a half-circle cut has value 1.Thus quotient rounding is strictly stronger than taking the character kernel in this smallest order-four example.

5 Cyclic averaging and approximation

Cyclic averaging replaces each generator by a uniformly random element of its cyclic subgroup, simplifying the Fourier spectrum while controlling metric objectives by the generators’ cyclic orders. Kernel rounding of a minimizing character then yields a constructive approximation whose factor is governed by cyclic averaging costs and character image size.

  • Cyclic averaging: The average shortest-path cost is α(2k)=k/2 for even orders and α(2k+1)=(r^2−1)/(4r) for odd orders, with α(r)=r/4+O(1).The cost is the average number of ±s steps needed to simulate a uniformly random subgroup move.
  • Cyclic averaging: Cyclic averaging samples a generator and a uniformly random multiple, including the identity, producing a subgroup projection that removes nontrivial character phases.For each generator s, the walk moves from x to x+ℓs with ℓ uniform over its cyclic subgroup.
  • Metric comparison: For every metric d, cyclic averaging increases the edge objective by at most ρ(S), and therefore SDP_GL(G♯)≤ρ(S)·SDP_GL(G).The comparison represents each averaged move by a shortest ±s path and averages the resulting triangle inequalities.
  • Approximation guarantee: Choosing a nontrivial character χ* minimizing the averaged eigenvalue and K=ker χ* gives ψ(G)≤ψ_G(K)≤[q*/(q*−1)]ρ(S)·SDP_GL(G)≤2ρ(S)·SDP_GL(G).Here q*=|χ*(Γ)|, and the image-size factor comes from the sparsity of the kernel cut.
  • Algorithm: If every generator has order at most R, the resulting guarantee is an R/2 approximation.The algorithm can enumerate characters and output the minimizing kernel without solving the SDP.
  • Algorithm: The analysis is polynomial in the explicit n-vertex/group-decomposition model, but enumerating all |Γ| characters can be exponential in a succinct description.The runtime claim therefore depends on the explicit representation of the group and generators.

6 Some examples and some consequences

Examples illustrate both exactness and the limitations of the cyclic-order bound, while a ten-vertex Abelian Cayley graph supplies a nontrivial integrality-gap seed. Cartesian powers preserve its gap, yielding an infinite connected family with exact gap 16/15.

  • Examples: Cubelike graphs are exact: λ2(G)=SDP_GL(G)=ψ(G), with an optimal cut given by a bottom-character hyperplane.The result extends the Boolean-character case to finite Abelian groups of exponent three and four.
  • Examples: For cycles, the cyclic-order parameter can overestimate the true GL gap by a linear factor, even though averaging determines the exact relaxation value.Specifically, ρ({−1,+1})=α(n)=Θ(n), while ψ(C_n)/SDP_GL(C_n)=1.
  • Cartesian powers: For fixed r≥5, Cartesian powers of C_r have a degree-independent spectral minimum attained by a one-coordinate character.The minimizing eigenvalue is obtained by setting one character coordinate to ±1 and all others to zero.
  • Gap seed: A ten-vertex Abelian Cayley graph C satisfies λ2(C)=SDP_GL(C)=3/4 but ψ(C)=4/5, giving an integrality gap of 16/15.The graph is combinatorially K5,5 with a perfect matching removed, and the optimum cut has five vertices.
  • Gap seed: The seed graph’s feasible metric is constructed as a nonnegative combination of two character distances and has SDP value 3/4.Its triangle inequalities are verified directly, including the case with longest side 2.
  • Cartesian powers: Cartesian powers preserve the cut optimum’s normalization and scale the feasible GL metric by 1/k.The product identity gives ψ(G_k)=ψ(C), while the tensorized metric yields SDP_GL(G_k)=3/(4k).
  • Cartesian powers: The resulting connected family has a constant integrality gap exactly 16/15, so the GL relaxation is not exact on Abelian Cayley graphs of growing order.In this family, the SDP value equals the spectral lower bound while every cut remains separated by the same constant factor.

7 Discussion and open problems

The paper gives evidence for constant-factor behavior of the Goemans–Linial relaxation on Abelian Cayley graphs through two rounding mechanisms, but does not determine the worst possible gap. It leaves open whether the 2ρ(S) bound can be tight and whether kernel rounding can be improved.

  • A lower-order character yields a valid Goemans–Linial metric that can be rounded without loss in its cyclic quotient.
  • An arbitrary character can be simplified by cyclic averaging and rounded to its kernel.
  • The framework is exact for several families, but it does not determine the worst possible Goemans–Linial gap on Abelian Cayley graphs.
  • Question 7.1 asks whether ψ(G)/SDP_GL(G) can grow with ρ(S), or whether the 2ρ(S) bound is inherently loose.
  • Question 7.2 asks whether analyzing Round(χ*) directly can improve the factor q*/(q*−1) or incorporate the quotient generator distribution.

8 Usage of GenAI in the manuscript

The manuscript reports that GenAI was used for editorial assistance and, more extensively, to organize and reformulate mathematical arguments already developed by the author in Subsections 5.1 and 5.2.

  • GenAI provided editorial assistance throughout the manuscript and more extensive help organizing, reformulating, and presenting already-developed arguments in Subsections 5.1 and 5.2.
Loading 2609.05368v1…