Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.1 — nearly cube-root gap in the vertex budget

Proved
ZhangTangLabelCut.LP2.vertex_integrality_gap

by Shuze Chen · Oct 29, 2026 · Mathlib 0df444a (Lean v4.33.1)

integrality-gaplinear-optimizationoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-v1

For every real ϵ>0\epsilon>0ϵ>0, there are a real Cϵ>0C_\epsilon>0Cϵ​>0 and an integer N0≥2N_0\ge 2N0​≥2, depending only on ϵ\epsilonϵ, such that for every integer N≥N0N\ge N_0N≥N0​ and for each of the directed and undirected graph conventions, there exists a finite simple label-cut instance III with distinct connected terminals and 2≤n≤N2\le n\le N2≤n≤N, where nnn is its actual vertex count. Its LP2 optimum is finite and positive, and

OPT⁡(I)OPT⁡f(LP2(I))≥CϵN1/3−ϵ.\frac{\operatorname{OPT}(I)}{\operatorname{OPT}_f(\mathrm{LP2}(I))}\ge C_\epsilon N^{1/3-\epsilon}.OPTf​(LP2(I))OPT(I)​≥Cϵ​N1/3−ϵ.

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
Preamble
import Definitions.Def_ZhangTangLabelCut_LP2_FiniteGraph
import Definitions.Def_ZhangTangLabelCut_LP2_CoveringLP
import Definitions.Def_ZhangTangLabelCut_LP2_LabelCut
Formal statement
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
Source
Zhang and Tang, Minimum Label s-t Cut has Large Integrality Gaps, arXiv:1908.11491v1 (2019), p. 13, Theorem 5.1; p. 23, directed extension
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Hypothesis. ε>0\varepsilon > 0ε>0, with no upper bound on ε\varepsilonε.

Claim. There exist a real C>0C > 0C>0 and a natural N0≥2N_0 \ge 2N0​≥2 such that, for every natural N≥N0N \ge N_0N≥N0​ and each choice of directed or undirected, there is a label-cut instance III satisfying four conditions.

What an instance is. III consists of:

  • an arbitrary finite graph with named edges (tail,head:E→V\mathrm{tail}, \mathrm{head} : E \to Vtail,head:E→V) whose directed flag equals the chosen one;
  • an arbitrary finite label set LLL;
  • an arbitrary labelling E→LE \to LE→L;
  • terminals s≠ts \ne ts=t.

The four conditions.

  1. 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 sss–ttt path exists.
    • The LP value is a real v>0v > 0v>0. The LP is: minimise ∑l∈Lxl\sum_{l \in L} x_l∑l∈L​xl​ over x≥0x \ge 0x≥0 with ∑l∈Λ(p)xl≥1\sum_{l \in \Lambda(p)} x_l \ge 1∑l∈Λ(p)​xl​≥1 for every simple sss–ttt path ppp, where Λ(p)\Lambda(p)Λ(p) is ppp's set of distinct labels.
  2. Vertex count. 2≤∣V∣≤N2 \le |V| \le N2≤∣V∣≤N. Every element of VVV counts, including isolated vertices.
  3. Ratio bound.
C⋅N13−ε ≤ opt(I)v,C\cdot N^{\frac13 - \varepsilon} \ \le\ \frac{\mathrm{opt}(I)}{v},C⋅N31​−ε ≤ vopt(I)​,

where opt(I)\mathrm{opt}(I)opt(I) is the minimum number of labels such that every simple sss–ttt 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 v>0v > 0v>0, so the ratio is an ordinary quotient and not the "division by zero gives 0" junk value.
  • N≥N0≥2N \ge N_0 \ge 2N≥N0​≥2 makes N13−εN^{\frac13 - \varepsilon}N31​−ε an ordinary positive real power.
  • Because ε\varepsilonε is unrestricted above, for ε≥1/3\varepsilon \ge 1/3ε≥1/3 the exponent is ≤0\le 0≤0. Then the required lower bound CN13−εC N^{\frac13 - \varepsilon}CN31​−ε is at most CCC.
  • CCC and N0N_0N0​ may depend on ε\varepsilonε. III may depend on NNN and on the directed flag.
Human review
  • Endorsed by Community (Bot) · Oct 29, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 29, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me