Pith Number

pith:D5RWDYOU

pith:2025:D5RWDYOUZK3RFPJCR3GEG4VZI5

not attested not anchored not stored refs resolved

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

Gabriel Coutinho, Henrique Assump\c{c}\~ao

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

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

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{D5RWDYOUZK3RFPJCR3GEG4VZI5}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

We use semidefinite programming to bound the fractional cut-cover parameter of graphs in association schemes in terms of their smallest eigenvalue.

C2weakest assumption

The graphs under consideration belong to an association scheme or coherent configuration, which supplies the algebraic structure needed to formulate the SDP and relate it to the smallest eigenvalue.

C3one line summary

SDP techniques bound fractional cut-cover and MAX 2-SAT on association scheme graphs and distance-regular graphs, extending Goemans-Williamson equality cases and computing gauge duals.

References

32 extracted · 32 resolved · 0 Pith anchors

[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 2007

[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, p 2025

[3] 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, page 2012

[4] Bailey.Association Schemes: Designed Experiments, Algebra, and Combi- natorics 2004

[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 1999

Formal links

2 machine-checked theorem links

Receipt and verification

First computed	2026-06-08T01:03:44.358693Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

1f6361e1d4cab712bd228ecc4372b9477a8bbb9e15b0c8ceb219b22f626af1e7

Aliases

arxiv: 2505.10548 · arxiv_version: 2505.10548v4 · doi: 10.48550/arxiv.2505.10548 · pith_short_12: D5RWDYOUZK3R · pith_short_16: D5RWDYOUZK3RFPJC · pith_short_8: D5RWDYOU

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/D5RWDYOUZK3RFPJCR3GEG4VZI5 \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: 1f6361e1d4cab712bd228ecc4372b9477a8bbb9e15b0c8ceb219b22f626af1e7

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "46c342f25d485b89197a368b17be68e7a2024a85a1006f7248d6aea1ef68fb72",
    "cross_cats_sorted": [
      "math.CO"
    ],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "math.OC",
    "submitted_at": "2025-05-15T17:56:11Z",
    "title_canon_sha256": "bcabc3a70ea93c5e66f0bdd1bcdaedbeed65cb3c91daf2ec6287e81b962603ff"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2505.10548",
    "kind": "arxiv",
    "version": 4
  }
}