pith. sign in

arxiv: 2505.10548 · v4 · submitted 2025-05-15 · 🧮 math.OC · math.CO

Semidefinite programming bounds on fractional cut-cover and maximum 2-SAT for highly regular graphs

Henrique Assump\c{c}\~ao , Gabriel Coutinho This is my paper

Pith reviewed 2026-05-22 14:23 UTC · model grok-4.3

classification 🧮 math.OC math.CO
keywords semidefinite programmingfractional cut-coverassociation schemesmaximum 2-SATdistance-regular graphsGoemans-Williamson algorithmspectral graph theory
0
0 comments X

The pith

Semidefinite programming bounds the fractional cut-cover of graphs in association schemes by their smallest eigenvalue.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that for graphs belonging to association schemes or coherent configurations, a semidefinite program yields an upper bound on the fractional cut-cover parameter expressed directly in terms of the graph's smallest eigenvalue. It extends equality cases from the Goemans-Williamson primal-dual analysis of the MAXCUT SDP to these algebraically structured graphs and derives analogous spectral bounds for the MAX 2-SAT problem on symmetric association schemes. The work further computes the exact optimum of the gauge dual of the underlying quadratic-programming SDP when the graph is distance-regular. A sympathetic reader would care because these connections supply algebraic shortcuts for bounding two hard covering and satisfiability parameters on highly regular graphs that arise in coding theory and combinatorial designs.

Core claim

For graphs in an association scheme, semidefinite programming produces a bound on the fractional cut-cover number that depends only on the smallest eigenvalue of the adjacency matrix; the same algebraic framework extends the known equality cases of the Goemans-Williamson SDP to coherent configurations and supplies explicit spectral bounds for MAX 2-SAT, with the gauge dual of the approximating SDP attaining a closed-form optimum on distance-regular graphs.

What carries the argument

The association scheme (or coherent configuration) that supplies the common eigenspaces and intersection numbers needed to formulate the SDP and tie its value to the smallest eigenvalue.

If this is right

  • The fractional cut-cover number of any graph in an association scheme is at most a simple function of its smallest eigenvalue.
  • Equality holds in the Goemans-Williamson primal-dual gap for the MAXCUT SDP on a larger family of coherent configurations.
  • MAX 2-SAT on symmetric association schemes admits spectral upper bounds obtained from a fixed quadratic-programming SDP.
  • The gauge dual of that quadratic SDP has an explicit optimum when the underlying graph is distance-regular.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same SDP construction may furnish approximation ratios for other quadratic Boolean problems on distance-regular graphs.
  • The eigenvalue bound could be compared with classical ratio bounds or Lovász theta to obtain tighter estimates for strongly regular graphs.
  • Explicit dual optima on distance-regular graphs open the possibility of certifying optimality for small-diameter instances without solving the SDP numerically.

Load-bearing premise

The graph must belong to an association scheme or coherent configuration so that the SDP can exploit its algebraic structure and relate the bound to the smallest eigenvalue.

What would settle it

A concrete graph in a known association scheme whose fractional cut-cover value lies strictly above the SDP bound derived from its smallest eigenvalue.

read the original abstract

We use semidefinite programming to bound the fractional cut-cover parameter of graphs in association schemes in terms of their smallest eigenvalue. We also extend the equality cases of a primal-dual inequality involving the Goemans-Williamson semidefinite program, which approximates MAXCUT, to graphs in certain coherent configurations. Moreover, we obtain spectral bounds for MAX 2-SAT when the underlying graphs belong to a symmetric association scheme by means of a certain semidefinite program used to approximate quadratic programs, and we further develop this technique in order to explicitly compute the optimum value of its gauge dual in the case of distance-regular graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript develops semidefinite programming bounds for the fractional cut-cover parameter on graphs belonging to association schemes or coherent configurations, reducing the SDP via the Bose-Mesner algebra to an expression involving the smallest eigenvalue. It extends the primal-dual equality cases of the Goemans-Williamson SDP for MAXCUT to such structured graphs. The work further derives spectral bounds for MAX 2-SAT on symmetric association schemes using an SDP relaxation of the associated quadratic program and explicitly computes the optimum value of the gauge dual for distance-regular graphs.

Significance. If the algebraic reductions hold, the paper supplies a parameter-free method for obtaining SDP-based bounds on combinatorial parameters for highly regular graphs, with explicit eigenvalue expressions and reproducible computations for distance-regular graphs. This strengthens the toolkit for analyzing approximation algorithms and extremal problems on association schemes, building directly on the Bose-Mesner algebra without ad-hoc fitting.

minor comments (2)
  1. The notation for the intersection numbers and eigenvalues in the association scheme setup could be summarized in a single table for easier reference when reading the SDP reductions.
  2. In the section deriving the gauge dual for distance-regular graphs, a brief remark on how the algebraic reduction compares to a generic SDP solver on a small example (e.g., the Petersen graph) would aid verification.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending minor revision. The referee's description accurately captures our use of the Bose-Mesner algebra to reduce SDPs for fractional cut-cover on association schemes, the extension of Goemans-Williamson primal-dual equality cases, and the spectral bounds plus gauge-dual computations for MAX 2-SAT on symmetric schemes and distance-regular graphs. No major comments were listed in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation relies on the algebraic structure of association schemes and coherent configurations to reduce the SDP formulation for fractional cut-cover directly to a linear combination of eigenvalues, yielding a bound in terms of the smallest eigenvalue. This reduction follows from the Bose-Mesner algebra properties stated in the setup and standard SDP duality, without any parameter fitting to target quantities, self-definitional loops, or load-bearing self-citations. Extensions to Goemans-Williamson equality cases and gauge-dual computations for distance-regular graphs are obtained via the same explicit algebraic steps, keeping the central claims independent of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the domain assumption that the input graphs possess the algebraic structure of association schemes or coherent configurations; no free parameters or invented entities are indicated in the abstract.

axioms (1)
  • domain assumption Graphs belong to association schemes or coherent configurations
    This structure is invoked to express the fractional cut-cover bound in terms of the smallest eigenvalue and to extend the Goemans-Williamson equality cases.

pith-pipeline@v0.9.0 · 5635 in / 1240 out tokens · 55519 ms · 2026-05-22T14:23:11.754873+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

32 extracted references · 32 canonical work pages

  1. [1]

    P. Austrin. Balanced max 2-sat might not be the hardest. InProceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC ’07, page 189–197, New York, NY, USA, 2007. Association for Computing Machinery

    work page 2007

  2. [2]

    N. B. Proença, M. K. de Carli Silva, C. M. Sato, and L. Tunçel. A primal-dual extension of the Goemans–Williamson algorithm for the weighted fractional cut-covering problem.Mathematical Programming, pages 1–56, 2025

    work page 2025

  3. [3]

    Bachoc, D

    C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin. Invariant semidefinite programs. In M. F. Anjos and J. B. Lasserre, editors,Handbook on Semidefinite, Conic and Polynomial Optimization, pages 219–269. Springer US, New York, NY, 2012

    work page 2012

  4. [4]

    Bailey.Association Schemes: Designed Experiments, Algebra, and Combi- natorics

    R. Bailey.Association Schemes: Designed Experiments, Algebra, and Combi- natorics. Cambridge studies in advanced mathematics. Cambridge University Press, 2004. 15

    work page 2004

  5. [5]

    E. Bannai. An introduction to association schemes.Methods of Discrete Mathematics (eds. S. Löwe, F. Mazzocca, N. Melone and U. Ott), Quaderni di Mathematica, 5:1–70, 1999

    work page 1999

  6. [6]

    Biggs.Algebraic Graph Theory

    N. Biggs.Algebraic Graph Theory. Cambridge Mathematical Library. Cambridge University Press, 1993

    work page 1993

  7. [7]

    Brakensiek, N

    J. Brakensiek, N. Huang, and U. Zwick. Tight approximability of max 2-sat and relatives, under ugc, 2023

    work page 2023

  8. [8]

    Brouwer, A.M

    A.E. Brouwer, A.M. Cohen, and A. Neumaier.Distance-Regular Graphs. Ergeb- nisse der Mathematik und ihrer Grenzgebiete. 3. Folge / A Series of Modern Surveys in Mathematics. Springer Berlin Heidelberg, 2011

    work page 2011

  9. [9]

    P. J. Cameron. Coherent configurations, association schemes and permutation groups. InGroups, Combinatorics and Geometry: DURHAM 2001, pages 55–71. World Scientific, 2003

    work page 2001

  10. [10]

    Cohen and D

    N. Cohen and D. V. Pasechnik. Implementing brouwer’s database of strongly regular graphs.Designs, Codes and Cryptography, 84(1–2):223–235, August 2016

    work page 2016

  11. [11]

    Dalfó, M

    C. Dalfó, M. A. Fiol, and E. Garriga. Onk-walk-regular graphs.Electron. J. Comb., 16(1):R47, April 2009

    work page 2009

  12. [12]

    M. K. de Carli Silva, G. Coutinho, C. Godsil, and D. E. Roberson. Alge- bras, graphs and thetas.Electronic Notes in Theoretical Computer Science, 346:275–283, August 2019

    work page 2019

  13. [13]

    de Klerk, C

    E. de Klerk, C. Dobre, and D. V. Pasechnik. Numerical block diagonalization of matrix *-algebras with application to semidefinite programming.Mathematical Programming, 129(1):91–111, Sep 2011

    work page 2011

  14. [14]

    Delsarte.An Algebraic Approach to the Association Schemes of Coding Theory

    P. Delsarte.An Algebraic Approach to the Association Schemes of Coding Theory. Philips journal of research / Supplement. N.V. Philips’ Gloeilampenfabrieken, 1973

    work page 1973

  15. [15]

    D. R. Fulkerson. Blocking and anti-blocking pairs of polyhedra.Mathematical Programming, 1(1):168–194, Dec 1971

    work page 1971

  16. [16]

    M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified np-complete problems. InProceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC ’74, page 47–63, New York, NY, USA, 1974. Association for Computing Machinery

    work page 1974

  17. [17]

    Godsil and B.D

    C.D. Godsil and B.D. McKay. Feasibility conditions for the existence of walk- regular graphs.Linear Algebra and its Applications, 30:51–61, 1980

    work page 1980

  18. [18]

    M. X. Goemans and F. Rendl. Semidefinite programs and association schemes. Computing, 63(4):331–340, Dec 1999. 16

    work page 1999

  19. [19]

    M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.J. ACM, 42(6):1115–1145, November 1995

    work page 1995

  20. [20]

    D. G. Higman. Coherent configurations.Geom. Dedicata, 4(1), May 1975

    work page 1975

  21. [21]

    Lewin, D

    M. Lewin, D. Livnat, and U. Zwick. Improved rounding techniques for the max 2-sat and max di-cut problems. In W. J. Cook and A. S. Schulz, editors,Integer Programming and Combinatorial Optimization, pages 67–82, Berlin, Heidelberg,

    work page

  22. [22]

    Springer Berlin Heidelberg

    work page

  23. [23]

    R. Loulou. Minimal cut cover of a graph with an application to the testing of electronic boards.Operations Research Letters, 12(5):301–305, 1992

    work page 1992

  24. [24]

    Motwani and J

    R. Motwani and J. S. Naor. On exact and approximate cut covers of graphs. Technical report, Stanford, CA, USA, 1994

    work page 1994

  25. [25]

    Neto and W

    J. Neto and W. Ben-Ameur. On fractional cut covers.Discrete Applied Mathe- matics, 265:168–181, 2019

    work page 2019

  26. [26]

    N. B. Proença, M. K. de Carli Silva, and G. Coutinho. Dual Hoffman bounds for the stability and chromatic numbers based on semidefinite programming. SIAM Journal on Discrete Mathematics, 35(4):2880–2907, 2021

    work page 2021

  27. [27]

    R. T. Rockafellar.Convex analysis, volume 28. Princeton university press, 1997

    work page 1997

  28. [28]

    Rowlinson

    P. Rowlinson. Linear algebra. InGraph Connections: Relationships between Graph Theory and other Areas of Mathematics. Oxford University Press, 01 1997

    work page 1997

  29. [29]

    Stein et al.Sage Mathematics Software (Version 9.5)

    W.A. Stein et al.Sage Mathematics Software (Version 9.5). The Sage Develop- ment Team, 2022.http://www.sagemath.org

    work page 2022

  30. [30]

    Tung-Yang and H

    H. Tung-Yang and H. Lih-Hsing. A note on the minimum cut cover of graphs. Operations Research Letters, 15(4):193–194, 1994

    work page 1994

  31. [31]

    E. R. van Dam and R. Sotirov. Semidefinite programming and eigenvalue bounds for the graph partition problem.Mathematical Programming, 151(2):379–404, September 2014

    work page 2014

  32. [32]

    R. Šámal. Fractional covering by cuts.Electronic Notes in Discrete Mathematics, 22:455–459, 2005. 7th International Colloquium on Graph Theory. 17

    work page 2005