Theorem 2.3 — N(G) is exactly the solution set of the nonnegativity, edge, and odd hole constraints
ProvedLovaszSchrijver.OddHole.NG_eq_odd_hole_systemLet be a finite graph with no isolated nodes, and let be the relaxation of the stable set polytope obtained by one round of the Lovász–Schrijver operator applied to the fractional stable set polytope . Then is exactly the set of satisfying
- the nonnegativity constraints for each ;
- the edge constraints for each ;
- the odd hole constraints: for every set inducing a chordless odd cycle in ,
The theorem characterizes completely the constraints obtained in one step of the operator without positive semidefiniteness: one round of on adds exactly the odd hole constraints. In particular for every -perfect graph.
Formalization Note Odd holes include triangles () and exclude cycles with chords. The graph is assumed to have no isolated nodes, the paper's standing assumption in Section 2.a.
import Mathlib import Definitions.Def_LovaszSchrijver_OddHole_MatrixCone import Definitions.Def_LovaszSchrijver_OddHole_StableSetCones import Definitions.Def_LovaszSchrijver_OddHole_OddHole
namespace LovaszSchrijver.OddHole
/-- Theorem 2.3 (p. 178): for a finite graph `G` with no isolated nodes, the polytope `N(G)` is
exactly the solution set of the nonnegativity, edge, and odd hole constraints. -/
theorem NG_eq_odd_hole_system {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (hG : ∀ v, ∃ w, G.Adj v w) :
NG G = {x : V → ℝ | (∀ i, 0 ≤ x i) ∧ (∀ i j, G.Adj i j → x i + x j ≤ 1) ∧
∀ C : Finset V, IsOddHole G C → ∑ i ∈ C, x i ≤ ((C.card : ℝ) - 1) / 2} := by sorry
end LovaszSchrijver.OddHole
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix , any finite type with decidable equality (the vertices), and a simple graph on : no loops, symmetric adjacency, adjacency decidable. Assume has no isolated vertices:
The statement asserts a set equality between two subsets of , the real-valued functions .
Left side. The left side is , written NG G in the code. It is defined in the imported module Def_LovaszSchrijver_OddHole_StableSetCones, which is not included here. The theorem depends on that definition exactly as written, and this read-back cannot unfold it. The module name suggests that is built from cones related to stable sets. The auditor must check the definition's actual content separately.
Right side. The right side is the set of all that satisfy all three of the following families of constraints:
- Nonnegativity: for every .
- Edge constraints: for every ordered pair with .
- Odd-hole constraints: for every finite vertex subset with ,
Here is converted to a real number before is subtracted and the result is divided by . There is no natural-number truncation and no integer division.
The predicate comes from the imported module Def_LovaszSchrijver_OddHole_OddHole, also not included. The constraint applies to exactly those vertex sets that this predicate accepts, and to no others. A hole is presumably a chordless cycle, but the code does not say so, so the auditor should verify it. The code does not state whether the predicate requires any minimum size for (for example or ), whether it requires to be odd, or whether it requires the induced subgraph to be a chordless cycle.
The theorem asserts as sets. This means containment in both directions: every point of satisfies all three constraint families, and every point satisfying them lies in .
Degenerate cases. If is empty, the hypothesis of no isolated vertices is vacuously true. The right side is then all of , a single point. The only possible is , and if held, the bound would read , which is false. So the theorem claims is that single point, unless the odd-hole predicate accepts the empty set, in which case it claims .
If has exactly one vertex, the hypothesis cannot be satisfied, because a simple graph has no loops. The theorem is then vacuous.
In general, the hypothesis forces every vertex to have at least one neighbour, so whenever is non-empty.
The odd-hole bound uses real division, so no default values arise from it. Whether it can ever be applied to a set with , giving the right-hand side or , depends entirely on the unseen definition of . If has no sets satisfying , the third family is empty. The claim then reduces to being exactly the nonnegativity-plus-edge polytope.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.