Theorem 5.1 — nearly cube-root gap in the vertex budget
ProvedZhangTangLabelCut.LP2.vertex_integrality_gapFor every real , there are a real and an integer , depending only on , such that for every integer and for each of the directed and undirected graph conventions, there exists a finite simple label-cut instance with distinct connected terminals and , where is its actual vertex count. Its LP2 optimum is finite and positive, and
The LP uses real nonnegative weights, sums distinct labels along each simple terminal path, and has no coordinate upper bounds. This asserts the full asymptotic worst-case gap in the vertex budget, including arbitrarily large budgets and every positive epsilon.
Differences from the source:
- encoding: Omega of the worst-case ratio as a function of instance size → one positive constant and threshold followed by a witness for every integer size budget; reason: this is the quantified asymptotic worst-case meaning, with the budget at least the witness size
- encoding: undirected construction, with the directed extension in Section 7 → a Boolean orientation quantified over both cases; reason: both source graph orientations are preserved
- encoding: connected construction instances and the usual fractional optimum → simple connected witnesses with a finite strictly positive extended-real LP value; reason: rules out undefined ratios; LP2 has an attained finite optimum and connected instances have value at least one
import Definitions.Def_ZhangTangLabelCut_LP2_FiniteGraph import Definitions.Def_ZhangTangLabelCut_LP2_CoveringLP import Definitions.Def_ZhangTangLabelCut_LP2_LabelCut
namespace ZhangTangLabelCut.LP2
theorem vertex_integrality_gap (ε : ℝ) (hε : 0 < ε) :
∃ C : ℝ, 0 < C ∧ ∃ N₀ : ℕ, 2 ≤ N₀ ∧
∀ N : ℕ, N₀ ≤ N → ∀ directed : Bool, ∃ I : LabelCut,
I.graph.directed = directed ∧ I.Admissible ∧
2 ≤ Fintype.card I.graph.V ∧ Fintype.card I.graph.V ≤ N ∧
C * (N : ℝ) ^ (1 / 3 - ε) ≤ I.ratio := by sorry
end ZhangTangLabelCut.LP2
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Hypothesis. , with no upper bound on .
Claim. There exist a real and a natural such that, for every natural and each choice of directed or undirected, there is a label-cut instance satisfying four conditions.
What an instance is. consists of:
- an arbitrary finite graph with named edges () whose directed flag equals the chosen one;
- an arbitrary finite label set ;
- an arbitrary labelling ;
- terminals .
The four conditions.
- Admissible.
- The graph is simple: no loops, and no two distinct edges with equal tails and heads. In the undirected case, also none with tail and head swapped.
- Some simple – path exists.
- The LP value is a real . The LP is: minimise over with for every simple – path , where is 's set of distinct labels.
- Vertex count. . Every element of counts, including isolated vertices.
- Ratio bound.
where is the minimum number of labels such that every simple – path has an edge with one of those labels, and the power is a real power.
Not constrained. The statement places no bound on the number of edges or labels.
Degenerate cases:
- Admissibility makes , so the ratio is an ordinary quotient and not the "division by zero gives 0" junk value.
- makes an ordinary positive real power.
- Because is unrestricted above, for the exponent is . Then the required lower bound is at most .
- and may depend on . may depend on and on the directed flag.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.