A Computational Search for Minimal Obstruction Graphs for the Lov\'{a}sz--Schrijver SDP Hierarchy

Levent Tun\c{c}el; Yu Hin Au

arxiv: 2505.24735 · v2 · submitted 2025-05-30 · 🧮 math.CO · cs.DM· math.OC

A Computational Search for Minimal Obstruction Graphs for the Lov\'{a}sz--Schrijver SDP Hierarchy

Yu Hin Au , Levent Tun\c{c}el This is my paper

Pith reviewed 2026-05-19 12:55 UTC · model grok-4.3

classification 🧮 math.CO cs.DMmath.OC

keywords Lovász-Schrijver hierarchySDP relaxationsstable set polytopeminimal obstruction graphslift-and-project operatorscomputational enumerationinteger certificates

0 comments

The pith

A computational search using new certificate packages finds at least 49 non-isomorphic 3-minimal graphs and 4,107 4-minimal graphs for the Lovász-Schrijver LS+ hierarchy.

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

The paper develops LS+ certificate packages to certify exact ranks in the Lovász-Schrijver SDP hierarchy using only integer arithmetic. It then runs an exhaustive search over graphs on 3ℓ vertices to locate the smallest examples that require exactly ℓ rounds of the operator to reach the stable set polytope. This yields substantially larger collections of 3-minimal and 4-minimal graphs than earlier enumerations, along with the smallest vertex-transitive graphs for each rank up to 4. The new examples show that stretched cliques are central yet incomplete, that clique number guides but does not determine rank, and that some minimal graphs display novel minor and density properties.

Core claim

We prove that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs, improving the previously known counts of 14 and 588, respectively. The LS+ certificate packages make lower-bound proofs transparent by reducing verification to simple integer calculations.

What carries the argument

LS+ certificate packages: modular certificates that verify membership in successive LS+ relaxations of the stable set polytope using only integer arithmetic and concise calculations.

If this is right

Stretched cliques remain central but are not exhaustive among extremal graphs.
Clique number is informative but not decisive for determining LS+ rank.
Some extremal graphs exhibit previously unseen minor and edge-density behavior.
The smallest vertex-transitive graphs of LS+ rank ℓ are now known for every ℓ ≤ 4.

Where Pith is reading between the lines

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

The rapid growth from 14 to 49 (and 588 to 4,107) suggests the number of minimal graphs increases sharply with rank, which may guide future asymptotic bounds.
The certificate framework could be ported to other lift-and-project operators to obtain comparable rigorous computational results.
The structural variety among the new examples indicates that a complete classification of minimal graphs will require more than clique-based constructions.

Load-bearing premise

The computational enumeration procedure correctly generates and checks all non-isomorphic graphs on 3ℓ vertices and the implemented certificate packages accurately verify LS+ rank without software or arithmetic errors.

What would settle it

Discovery of a graph on nine vertices with LS+ rank exactly three that is non-isomorphic to all 49 enumerated examples, or an independent verification that one of the reported 4-minimal graphs actually has LS+ rank less than four.

read the original abstract

We study the lift-and-project relaxations of the stable set polytope of graphs generated by $\text{LS}_+$, the SDP lift-and-project operator devised by Lov\'{a}sz and Schrijver. Our focus is on $\ell$-minimal graphs: graphs on $3\ell$ vertices with $\text{LS}_+$-rank $\ell$, i.e., the smallest graphs realizing rank $\ell$. This manuscript makes two complementary contributions. First, we introduce $\text{LS}_+$ certificate packages, a modular framework for certifying membership in $\text{LS}_+$-relaxations using only integer arithmetic and simple, concise calculations, thereby making numerical lower-bound proofs more transparent, reliable, and easier to verify. Second, we apply this framework to a computational search for extremal graphs. We prove that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs, improving the previously known counts of 14 and 588, respectively. Beyond the increase in counts, the new examples sharpen the emerging structural picture: stretched cliques remain central but are not exhaustive, clique number is informative but not decisive, and some extremal graphs exhibit previously unseen graph minor and edge density behaviour. We also determine the smallest vertex-transitive graphs of $\text{LS}_+$-rank $\ell$ for every $\ell \leq 4$.

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.

Desk Editor's Note private letter to a colleague

This paper raises the lower bounds on 3- and 4-minimal graphs for the LS+ hierarchy and supplies an integer-arithmetic certificate method that makes the rank claims easier to check than typical SDP work.

read the letter

The main thing to know is that the authors improve the known lower bounds on minimal obstruction graphs for the Lovász-Schrijver SDP hierarchy and give a cleaner way to certify the exact ranks. They report at least 49 non-isomorphic 3-minimal graphs and 4,107 for rank 4, up from the earlier 14 and 588. The new LS+ certificate packages let you verify that a graph sits outside the previous level of the hierarchy using only integer steps and explicit dual multipliers, which removes the usual floating-point worries from numerical SDP computations. They also extract some structural observations, such as the continuing importance of stretched cliques alongside new examples that show different minor and density patterns, and they identify the smallest vertex-transitive graphs achieving each rank up to 4. That part of the work is useful because the certificates are modular and concise enough that a reader can follow the arithmetic without re-running a solver. The soft spot is the computational enumeration itself. The counts rest on generating all non-isomorphic graphs on exactly 3ℓ vertices and then applying the certificates to each. Without a machine-checked proof of the enumeration or the certificate generator, a labeling error or an off-by-one in the arithmetic routine could inflate the numbers. The integer approach makes such bugs easier to catch than in black-box SDP output, but independent reimplementation would still be needed to confirm the exact figures. This is a paper for people working on lift-and-project methods and the stable-set polytope. Readers who care about concrete obstruction sets or about making SDP rank proofs more transparent will get direct value from the new examples and the certificate format. It deserves a serious referee because the framework addresses a real verification gap in the area and the updated counts are concrete data even if they require checking.

Referee Report

2 major / 2 minor

Summary. The paper introduces LS+ certificate packages, a modular framework for certifying membership in Lovász-Schrijver SDP relaxations of the stable set polytope using only integer arithmetic and concise calculations. It applies this framework to a computational enumeration of minimal obstruction graphs, proving that there are at least 49 non-isomorphic 3-minimal graphs and at least 4,107 non-isomorphic 4-minimal graphs (improving on prior counts of 14 and 588), while also determining the smallest vertex-transitive graphs of LS+-rank ℓ for every ℓ ≤ 4. The new examples are used to sharpen structural observations about stretched cliques, clique number, graph minors, and edge density.

Significance. If the enumeration and certifications hold, the work substantially expands the catalog of extremal examples for the LS+ hierarchy and provides new structural insights. The LS+ certificate packages are a clear strength: by relying on integer arithmetic rather than floating-point SDP solvers, they make lower-bound proofs more transparent, reliable, and easier to verify independently. This addresses a common weakness in computational SDP-based results and could serve as a template for similar hierarchies.

major comments (2)

[§5] §5, Theorems 5.1 and 5.2: the lower bounds of 49 and 4,107 rest on the claim that the enumeration procedure generates all non-isomorphic graphs on exactly 3ℓ vertices and that each certificate package correctly witnesses a violation at level ℓ-1. The manuscript should include a brief but explicit argument or reference showing that the canonical labeling step and the arithmetic verification routine are free of the kinds of implementation errors that could produce spurious examples or duplicate isomorphs.
[§3.2] §3.2, definition of certificate packages: while the integer-arithmetic approach is correctly motivated, the paper does not supply a fully worked small example (e.g., for a known 2-minimal graph) that walks through every matrix and inequality in the package. Such an example is load-bearing for readers who wish to replicate or audit the 3- and 4-minimal certificates.

minor comments (2)

[§6] The abstract and §1 state that stretched cliques remain central but are not exhaustive; a short table or paragraph in §6 summarizing how many of the new 4-minimal graphs are stretched cliques versus other families would make this claim easier to assess.
[§4] A few sentences in §4 on the precise version of nauty or other tools used for isomorphism-free generation would improve reproducibility without lengthening the paper.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. We address each major comment below.

read point-by-point responses

Referee: [§5] §5, Theorems 5.1 and 5.2: the lower bounds of 49 and 4,107 rest on the claim that the enumeration procedure generates all non-isomorphic graphs on exactly 3ℓ vertices and that each certificate package correctly witnesses a violation at level ℓ-1. The manuscript should include a brief but explicit argument or reference showing that the canonical labeling step and the arithmetic verification routine are free of the kinds of implementation errors that could produce spurious examples or duplicate isomorphs.

Authors: We agree that an explicit discussion of correctness would strengthen the presentation. In the revised manuscript we will add a short paragraph in §5 describing the canonical labeling procedure (via nauty) that produces unique representatives for each isomorphism class, together with the fact that the verification routine performs only exact integer arithmetic on the certificate packages. Because the arithmetic steps are finite and exact, they admit direct hand or machine verification independent of the enumeration code; we will also note that the source code is available for inspection. revision: yes
Referee: [§3.2] §3.2, definition of certificate packages: while the integer-arithmetic approach is correctly motivated, the paper does not supply a fully worked small example (e.g., for a known 2-minimal graph) that walks through every matrix and inequality in the package. Such an example is load-bearing for readers who wish to replicate or audit the 3- and 4-minimal certificates.

Authors: We accept the suggestion. The revised version of §3.2 will contain a complete, step-by-step example for the 2-minimal graph C5, explicitly constructing each matrix and inequality in its LS+ certificate package and verifying the violation at level 1 using only integer arithmetic. This concrete illustration should make the framework transparent for readers auditing the larger enumerations. revision: yes

Circularity Check

0 steps flagged

No significant circularity; computational enumeration and new certificates are independent

full rationale

The paper establishes its lower bounds on the number of 3-minimal and 4-minimal graphs via direct computational search over non-isomorphic graphs on 3ℓ vertices together with newly introduced LS+ certificate packages that certify exact rank ℓ using integer arithmetic. These steps do not reduce any claimed count or rank to a fitted parameter, self-defined quantity, or load-bearing self-citation; prior counts (14 and 588) appear only for comparison and are not invoked to justify the new enumeration or certificates. The derivation chain is therefore self-contained and externally falsifiable through the exhibited certificates and search procedure.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on standard domain assumptions from SDP theory and polyhedral combinatorics. It introduces a new framework rather than new mathematical entities or fitted parameters.

axioms (1)

domain assumption Standard properties of the Lovász-Schrijver LS+ operator and the stable set polytope.
Invoked in the definition of LS+-rank and minimal graphs throughout the study.

invented entities (1)

LS+ certificate packages no independent evidence
purpose: Modular framework for certifying membership in LS+ relaxations via integer arithmetic.
New verification tool introduced to make numerical lower-bound proofs transparent and reliable.

pith-pipeline@v0.9.0 · 5803 in / 1282 out tokens · 66740 ms · 2026-05-19T12:55:51.698912+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

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

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking echoes

?

echoes
ECHOES: this paper passage has the same mathematical shape or conceptual pattern as the Recognition theorem, but is not a direct formal dependency.

graphs on 3ℓ vertices with LS+-rank ℓ, i.e., the smallest graphs realizing rank ℓ

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.