Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.1 — a realization with large integral optimum

Proved
ZhangTangLabelCut.LP2.large_integral_optimum

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

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

For each real ϵ>0\epsilon>0ϵ>0 there exist an integer D>0D>0D>0, a real C>0C>0C>0, and an integer k0≥2k_0\ge2k0​≥2, depending only on ϵ\epsilonϵ, with the following property. For every integer k≥k0k\ge k_0k≥k0​ and each orientation there is a permutation realization I^\hat II^ of the Section 4 construction with d=32k2Dd=32k^{2D}d=32k2D and h=kDh=k^Dh=kD. It is a simple connected graph with finite positive LP optimum. Writing n,mn,mn,m for its actual vertex and edge counts,

OPT⁡(I^)≥Ckn1/3−ϵ,n≤48k2+3D,m≤64k2+3D.\operatorname{OPT}(\hat I)\ge Ck n^{1/3-\epsilon},\qquad n\le48k^{2+3D},\qquad m\le64k^{2+3D}.OPT(I^)≥Ckn1/3−ϵ,n≤48k2+3D,m≤64k2+3D.

This is the large-cut witness needed for the integrality-gap theorem, together with its construction and polynomial size control.

Differences from the source:

  • generalization: existence of an appropriate Section 4 realization with the Omega lower bound → the same existence within the integral family delta = beta = D, with explicit polynomial size bounds; reason: choosing integer D ≥ 1/(3epsilon) in the nontrivial range proves the original existential claim and retains every epsilon; these are stronger witness specifications, not restrictions on universal graph inputs
  • encoding: Omega with a constant depending only on epsilon → D, C and k0 are chosen before k and the realization; reason: makes dependencies uniform
  • 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
import Definitions.Def_ZhangTangLabelCut_LP2_Shutter
import Definitions.Def_ZhangTangLabelCut_LP2_Configurations
Formal statement
namespace ZhangTangLabelCut.LP2

theorem large_integral_optimum (ε : ℝ) (hε : 0 < ε) :
    ∃ D : ℕ, 0 < D ∧ ∃ C : ℝ, 0 < C ∧ ∃ k₀ : ℕ, 2 ≤ k₀ ∧
      ∀ k : ℕ, k₀ ≤ k → ∀ directed : Bool,
        ∃ σ : Sample k (32 * k ^ (2 * D)) (k ^ D),
          let I := shutterInstance k (32 * k ^ (2 * D)) (k ^ D) directed σ
          I.Admissible ∧
          C * k * (Fintype.card I.graph.V : ℝ) ^ (1 / 3 - ε) ≤ (I.opt : ℝ) ∧
          Fintype.card I.graph.V ≤ 48 * k ^ (2 + 3 * D) ∧
          Fintype.card I.graph.E ≤ 64 * k ^ (2 + 3 * D) := by sorry

end ZhangTangLabelCut.LP2
Source
Zhang and Tang, Minimum Label s-t Cut has Large Integrality Gaps, arXiv:1908.11491v1 (2019), p. 12, Lemma 5.1; p. 20, restatement; Section 4; p. 23, Section 7
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 natural D≥1D \ge 1D≥1, a real C>0C > 0C>0 and a natural k0≥2k_0 \ge 2k0​≥2 such that, for every natural k≥k0k \ge k_0k≥k0​ and each choice of directed or undirected, some sample σ\sigmaσ yields an instance III with the four properties below. The instance has parameters

d=32k2D,h=kDd = 32k^{2D}, \qquad h = k^Dd=32k2D,h=kD

(natural-number powers).

The instance III. σ\sigmaσ assigns a permutation σc\sigma_cσc​ of {0..d−1}\{0..d-1\}{0..d−1} to each chain c=(μ,ν,i)c = (\mu, \nu, i)c=(μ,ν,i) with μ<ν<k\mu < \nu < kμ<ν<k and i<hi < hi<h. The graph is:

  • terminals s,ts, ts,t;
  • per chain, junctions Jc(0)=sJ_c(0) = sJc​(0)=s, Jc(1..d−1)J_c(1..d-1)Jc​(1..d−1), Jc(d)=tJ_c(d) = tJc​(d)=t, and middles Mc(j,b)M_c(j, b)Mc​(j,b);
  • edges Jc(j)→Mc(j,b)→Jc(j+1)J_c(j) \to M_c(j, b) \to J_c(j+1)Jc​(j)→Mc​(j,b)→Jc​(j+1) for j<dj < dj<d and b∈{0,1}b \in \{0, 1\}b∈{0,1}, one-way if directed and two-way if not;
  • labels in {0..k−1}×{0..d−1}\{0..k-1\} \times \{0..d-1\}{0..k−1}×{0..d−1}: edges through Mc(j,0)M_c(j, 0)Mc​(j,0) get (μ,j)(\mu, j)(μ,j), and edges through Mc(j,1)M_c(j, 1)Mc​(j,1) get (ν,σc(j))(\nu, \sigma_c(j))(ν,σc​(j)).

This gives ∣V∣=2+(3d−1)h(k2)|V| = 2 + (3d - 1)h\binom k2∣V∣=2+(3d−1)h(2k​) and ∣E∣=4dh(k2)|E| = 4dh\binom k2∣E∣=4dh(2k​).

The four properties of III.

  1. Admissible. The graph is simple, at least one simple sss–ttt path exists, and the LP value is some real v>0v > 0v>0. The LP is: minimise ∑lxl\sum_l x_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 each simple sss–ttt path ppp, where Λ(p)\Lambda(p)Λ(p) is ppp's set of labels.
  2. Large optimum. C⋅k⋅∣V∣13−ε≤opt(I)C \cdot k \cdot |V|^{\frac13 - \varepsilon} \le \mathrm{opt}(I)C⋅k⋅∣V∣31​−ε≤opt(I), where opt(I)\mathrm{opt}(I)opt(I) is the minimum number of labels meeting every simple sss–ttt path, and the power is a real power.
  3. Vertex bound. ∣V∣≤48 k2+3D|V| \le 48\,k^{2 + 3D}∣V∣≤48k2+3D.
  4. Edge bound. ∣E∣≤64 k2+3D|E| \le 64\,k^{2 + 3D}∣E∣≤64k2+3D.

Degenerate cases:

  • Since k≥2k \ge 2k≥2 and D≥1D \ge 1D≥1, we have d≥1d \ge 1d≥1, h≥1h \ge 1h≥1 and ∣V∣≥2|V| \ge 2∣V∣≥2, so the real power has a positive base.
  • Because ε\varepsilonε is unrestricted above, for ε≥1/3\varepsilon \ge 1/3ε≥1/3 the exponent is ≤0\le 0≤0. Then ∣V∣13−ε≤1|V|^{\frac13-\varepsilon} \le 1∣V∣31​−ε≤1 and property 2 asks only Ck≤opt(I)C k \le \mathrm{opt}(I)Ck≤opt(I) or less.
  • D,C,k0D, C, k_0D,C,k0​ may depend on ε\varepsilonε. σ\sigmaσ may depend on kkk 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