Stable Set Polytopes with Rank $|V(G)|/3$ for the Lov\'{a}sz--Schrijver SDP Operator

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

arxiv: 2501.07413 · v3 · submitted 2025-01-13 · 🧮 math.CO · cs.CC· cs.DM· math.OC

Stable Set Polytopes with Rank |V(G)|/3 for the Lov\'{a}sz--Schrijver SDP Operator

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

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

classification 🧮 math.CO cs.CCcs.DMmath.OC

keywords stable set polytopeLovász–Schrijver operatorlift-and-project ranksemidefinite programminggraph polytopescombinatorial optimizationvertex-transitive graphs

0 comments

The pith

The smallest graph with Lovász–Schrijver rank ℓ has exactly 3ℓ vertices.

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

The paper shows that applying the Lovász–Schrijver SDP operator LS+ to the fractional stable set polytope always produces the integral stable set polytope after at most |V(G)|/3 iterations. For any positive integer ℓ, no graph on fewer than 3ℓ vertices reaches rank ℓ, yet graphs on exactly 3ℓ vertices do achieve rank ℓ. The same paper supplies vertex-transitive examples attaining rank at least ℓ on at most 4ℓ+12 vertices. A reader sees this as determining the precise worst-case number of vertices needed to force a given number of tightening steps.

Core claim

For every positive integer ℓ the smallest possible graph with LS+-rank ℓ contains 3ℓ vertices. This bound is sharp because graphs on 3ℓ vertices exist with rank exactly ℓ, and the result also yields vertex-transitive graphs on at most 4ℓ+12 vertices with rank at least ℓ.

What carries the argument

The Lovász–Schrijver SDP operator LS+ applied iteratively to the fractional stable set polytope, where the rank equals the number of iterations required to reach the integral stable set polytope.

If this is right

The LS+ rank of the stable set polytope is at most |V(G)|/3 for every graph G.
There exist graphs where the LS+ rank equals exactly |V(G)|/3.
Vertex-transitive graphs exist with LS+ rank at least ℓ on a linear number of vertices.
The 2003 conjecture on the minimal order of a graph with given LS+ rank is settled.

Where Pith is reading between the lines

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

The same linear bound may limit the number of iterations needed when LS+ is applied to other 0-1 polytopes.
The explicit constructions on 3ℓ vertices supply concrete test cases for comparing different lift-and-project operators on stable-set instances.
The vertex-transitive examples on O(ℓ) vertices could be used to study symmetry-preserving SDP hierarchies.

Load-bearing premise

The LS+ operator applied to the fractional stable set polytope produces a well-defined finite sequence of relaxations that reaches the integral polytope after finitely many steps.

What would settle it

Any graph on fewer than 3ℓ vertices whose stable set polytope still differs from the integral polytope after ℓ iterations of LS+ would falsify the claim.

read the original abstract

We study the lift-and-project rank of the stable set polytope of graphs with respect to the Lov\'{a}sz--Schrijver SDP operator $\text{LS}_+$ applied to the fractional stable set polytope. In particular, we show that for every positive integer $\ell$, the smallest possible graph with $\text{LS}_+$-rank $\ell$ contains $3\ell$ vertices. This result is sharp and settles a conjecture posed by Lipt\'{a}k and the second author in 2003, as well as answers a generalization of a problem posed by Knuth in 1994. We also show that for every positive integer $\ell$ there exists a vertex-transitive graph on at most $4\ell+12$ vertices with $\text{LS}_+$-rank at least $\ell$.

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

The paper settles the 2003 conjecture by proving that LS+ rank ℓ requires exactly 3ℓ vertices at minimum, with matching constructions.

read the letter

This paper proves that the smallest graph with LS+ rank ℓ has exactly 3ℓ vertices. That settles the Lipták-Tunçel conjecture from 2003 and gives a clean answer to the generalized Knuth question as well. The lower bound shows no smaller graph works, and the upper bound supplies explicit graphs on 3ℓ vertices that achieve the rank. The vertex-transitive constructions on at most 4ℓ+12 vertices are a useful extra piece, even though they sit a bit above the minimum size. The work is new because the exact constant 3ℓ was open before; earlier papers had bounds but not this tight match. The argument uses the standard iterative definition of the LS+ operator on the fractional stable set polytope and tracks how many rounds are needed to reach the integral hull. That approach is consistent with known behavior for 0-1 polytopes. The lower bound appears to rest on a structural count of vertices needed to force one more iteration, which is a reasonable way to get the sharp threshold. One soft spot is the gap in the vertex-transitive case: 4ℓ+12 is not as tight as the main result, so tighter symmetric examples might still exist. The proof details would need checking for small ℓ to confirm the induction base, but nothing in the abstract suggests a load-bearing flaw. The citations cover the relevant prior work on LS ranks without obvious omissions. This is for people working on lift-and-project hierarchies and stable set polytopes. A reader who cares about exact ranks or minimal counterexamples to integrality will get concrete value from the bound. It deserves a serious referee because the claim is precise, falsifiable, and resolves a named open question.

Referee Report

0 major / 2 minor

Summary. The manuscript proves that for every positive integer ℓ, the smallest graph whose stable set polytope has LS+-rank ℓ (under iterative application of the Lovász–Schrijver SDP operator to the fractional stable set polytope) has exactly 3ℓ vertices. This is established via a matching lower bound (no graph on fewer than 3ℓ vertices attains rank ℓ) and explicit constructions achieving rank ℓ on 3ℓ vertices. The bound is shown to be sharp and settles the 2003 conjecture of Lipták and the second author; the paper also constructs vertex-transitive graphs on at most 4ℓ+12 vertices with LS+-rank at least ℓ.

Significance. If the proofs hold, the result gives a definitive, tight characterization of the minimal order of graphs realizing each LS+-rank value for stable set polytopes, resolving a conjecture that has stood since 2003 and answering a generalization of Knuth’s 1994 question. The exact |V(G)|/3 bound is parameter-free and obtained from structural properties of the operator iterations rather than fitted constants. The vertex-transitive constructions further strengthen the contribution for symmetry-aware applications in combinatorial optimization.

minor comments (2)

[Introduction] The introduction would benefit from a one-sentence reminder of the precise starting polytope (the fractional stable set polytope) before stating the rank definition, even though this is standard in the area.
A small table or diagram summarizing the rank and vertex count for the base cases ℓ=1,2,3 would improve readability of the inductive constructions.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept. The summary accurately reflects the paper's contributions and the resolution of the 2003 conjecture.

Circularity Check

0 steps flagged

No significant circularity; proof is self-contained

full rationale

The paper establishes a sharp bound on LS+-rank via explicit constructions for the upper bound and an inductive/structural argument for the lower bound. These steps rely on standard properties of the Lovász–Schrijver operator (finite rank at most n for n-vertex 0-1 polytopes) that are externally known and not derived within the paper. The 2003 conjecture by Lipták and Tunçel is cited only as motivation; the current proof does not invoke it as a premise or reduce any claim to a self-citation chain. No fitted parameters, self-definitional equalities, or ansatzes smuggled via prior work appear in the derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of the LS+ operator and the fractional stable set polytope; no new free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption The Lovász–Schrijver SDP operator LS+ applied iteratively to the fractional stable set polytope produces a well-defined finite rank equal to the number of iterations required to reach the integral stable set polytope.
This is the standard setup assumed throughout the field and invoked by the abstract's definition of rank.

pith-pipeline@v0.9.0 · 5695 in / 1266 out tokens · 38415 ms · 2026-05-23T05:39:24.676158+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/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that for every positive integer ℓ, the smallest possible graph with LS+-rank ℓ contains 3ℓ vertices... stretched cliques obtained by 2-stretching vertices of Kn
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 12... uc⊤x=c0(P)−ϵ[1 χD]∈cone(LSk+1+(P))... rank at least k+2

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.