Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.1 — nearly cube-root gap in the edge budget

Proved
ZhangTangLabelCut.LP2.edge_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 M0≥1M_0\ge 1M0​≥1, depending only on ϵ\epsilonϵ, such that for every integer M≥M0M\ge M_0M≥M0​ and for each of the directed and undirected graph conventions, there exists a finite simple label-cut instance III with distinct connected terminals and 1≤m≤M1\le m\le M1≤m≤M, where mmm is its actual edge count. Its LP2 optimum is finite and positive, and

OPT⁡(I)OPT⁡f(LP2(I))≥CϵM1/3−ϵ.\frac{\operatorname{OPT}(I)}{\operatorname{OPT}_f(\mathrm{LP2}(I))}\ge C_\epsilon M^{1/3-\epsilon}.OPTf​(LP2(I))OPT(I)​≥Cϵ​M1/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 edge 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 edge_integrality_gap (ε : ℝ) (hε : 0 < ε) :
    ∃ C : ℝ, 0 < C ∧ ∃ M₀ : ℕ, 1 ≤ M₀ ∧
      ∀ M : ℕ, M₀ ≤ M → ∀ directed : Bool, ∃ I : LabelCut,
        I.graph.directed = directed ∧ I.Admissible ∧
        1 ≤ Fintype.card I.graph.E ∧ Fintype.card I.graph.E ≤ M ∧
        C * (M : ℝ) ^ (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. 4, Theorem 1.1; p. 13, restatement; p. 23, directed extension
Read-back

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

For every real number ε>0\varepsilon > 0ε>0 there exist a real constant C>0C > 0C>0 and a natural number M0≥1M_0 \ge 1M0​≥1 such that the following holds. For every natural number M≥M0M \ge M_0M≥M0​, and for each of the two values of a Boolean flag d∈{true,false}d \in \{\text{true}, \text{false}\}d∈{true,false}, there exists a label-cut instance III with:

  1. the graph of III has directedness flag equal to ddd;
  2. III is admissible (defined below);
  3. the number of edges satisfies 1≤∣E∣≤M1 \le |E| \le M1≤∣E∣≤M;
  4. the ratio of III is large:
C⋅M 1/3−ε  ≤  ratio⁡(I).C \cdot M^{\,1/3 - \varepsilon} \;\le\; \operatorname{ratio}(I).C⋅M1/3−ε≤ratio(I).

The exponent 1/3−ε1/3 - \varepsilon1/3−ε is a real number, and M1/3−εM^{1/3-\varepsilon}M1/3−ε is the real power of the positive real MMM. The quantifier order matters. CCC and M0M_0M0​ depend only on ε\varepsilonε, and the same pair must work for both values of ddd. The instance III may depend on ε\varepsilonε, MMM and ddd. MMM enters only as an upper bound on the edge count, and the lower bound on the ratio is stated in terms of MMM, not in terms of ∣E∣|E|∣E∣.

The graph. A finite graph GGG consists of:

  • a finite vertex type VVV and a finite edge type EEE;
  • maps tail⁡,head⁡:E→V\operatorname{tail}, \operatorname{head} : E \to Vtail,head:E→V;
  • a Boolean flag "directed".

An edge eee traverses from uuu to vvv if either:

  • tail⁡(e)=u\operatorname{tail}(e) = utail(e)=u and head⁡(e)=v\operatorname{head}(e) = vhead(e)=v; or
  • the graph is undirected (flag false), head⁡(e)=u\operatorname{head}(e) = uhead(e)=u and tail⁡(e)=v\operatorname{tail}(e) = vtail(e)=v.

GGG is simple if both of the following hold:

  • no edge has tail⁡(e)=head⁡(e)\operatorname{tail}(e) = \operatorname{head}(e)tail(e)=head(e);
  • any two edges e,fe, fe,f are equal whenever they have the same tail and the same head, or whenever the graph is undirected and tail⁡(e)=head⁡(f)\operatorname{tail}(e) = \operatorname{head}(f)tail(e)=head(f), head⁡(e)=tail⁡(f)\operatorname{head}(e) = \operatorname{tail}(f)head(e)=tail(f).

So in the directed case, two edges u→vu \to vu→v and v→uv \to uv→u are both permitted.

Paths. An sss–ttt path consists of:

  • a length n∈Nn \in \mathbb{N}n∈N;
  • vertices v0,…,vnv_0, \dots, v_nv0​,…,vn​ that are pairwise distinct, with v0=sv_0 = sv0​=s and vn=tv_n = tvn​=t;
  • edges e0,…,en−1e_0, \dots, e_{n-1}e0​,…,en−1​ such that each eje_jej​ traverses from vjv_jvj​ to vj+1v_{j+1}vj+1​.

The instance. A label-cut instance III consists of:

  • a finite graph GGG as above;
  • a finite label type LLL and a labelling map λ:E→L\lambda : E \to Lλ:E→L;
  • two vertices s,ts, ts,t with s≠ts \ne ts=t.

The label set of a path ppp is

Λ(p)={λ(ej):0≤j<n}⊆L.\Lambda(p) = \{\lambda(e_j) : 0 \le j < n\} \subseteq L.Λ(p)={λ(ej​):0≤j<n}⊆L.

A finite set S⊆LS \subseteq LS⊆L is a cut if every sss–ttt path ppp has some edge eje_jej​ with λ(ej)∈S\lambda(e_j) \in Sλ(ej​)∈S.

opt⁡(I)∈N\operatorname{opt}(I) \in \mathbb{N}opt(I)∈N is the infimum, over the natural numbers, of the cardinalities ∣S∣|S|∣S∣ of cuts SSS.

The linear program. The LP of III has one real variable xℓx_\ellxℓ​ per label ℓ∈L\ell \in Lℓ∈L. A vector xxx is feasible if:

  • xℓ≥0x_\ell \ge 0xℓ​≥0 for all ℓ\ellℓ (there are no upper bounds);
  • for every subset R⊆LR \subseteq LR⊆L that equals Λ(p)\Lambda(p)Λ(p) for at least one sss–ttt path ppp, the covering constraint holds:
∑ℓ∈Rxℓ≥1.\sum_{\ell \in R} x_\ell \ge 1.ℓ∈R∑​xℓ​≥1.

There is one constraint per distinct label set, not one per path. The objective is ∑ℓ∈Lxℓ\sum_{\ell \in L} x_\ell∑ℓ∈L​xℓ​.

The value of the LP is the infimum, in the extended reals [−∞,+∞][-\infty, +\infty][−∞,+∞], of the objective over all feasible xxx. It is +∞+\infty+∞ if no xxx is feasible.

frac⁡(I)\operatorname{frac}(I)frac(I) is this value converted to a real number. That conversion sends ±∞\pm\infty±∞ to 000.

The ratio is the real quotient

ratio⁡(I)=opt⁡(I)frac⁡(I).\operatorname{ratio}(I) = \frac{\operatorname{opt}(I)}{\operatorname{frac}(I)}.ratio(I)=frac(I)opt(I)​.

Admissibility. III is admissible if all of the following hold:

  • GGG is simple;
  • at least one sss–ttt path exists;
  • the LP value equals some real number vvv with v>0v > 0v>0.

In that case frac⁡(I)=v>0\operatorname{frac}(I) = v > 0frac(I)=v>0.

Degenerate cases.

  • Small or zero sizes. Since M≥M0≥1M \ge M_0 \ge 1M≥M0​≥1, the case M=0M = 0M=0 never arises. A graph with no edges is excluded by ∣E∣≥1|E| \ge 1∣E∣≥1. Since there is an edge and λ\lambdaλ maps edges to labels, LLL is nonempty, but it may have a single element. Since s≠ts \ne ts=t, VVV has at least two vertices.
  • Paths. Every sss–ttt path has length n≥1n \ge 1n≥1, so every label set Λ(p)\Lambda(p)Λ(p) is nonempty.
  • The infimum defining opt⁡\operatorname{opt}opt. The full label set LLL is always a cut, so the set of cut sizes is never empty and opt⁡\operatorname{opt}opt is a genuine minimum, never the default value of an empty infimum. Under admissibility a path exists, so the empty set is not a cut and opt⁡(I)≥1\operatorname{opt}(I) \ge 1opt(I)≥1.
  • The LP value. The defaults (the value +∞+\infty+∞ for an infeasible LP, and the conversion of ±∞\pm\infty±∞ to 000) are excluded by the admissibility requirement that the value be a finite positive real. Hence the division in ratio⁡\operatorname{ratio}ratio is never by zero, and ratio⁡(I)>0\operatorname{ratio}(I) > 0ratio(I)>0.
  • Large ε\varepsilonε. The statement places no upper bound on ε\varepsilonε. For ε=1/3\varepsilon = 1/3ε=1/3 the factor M1/3−εM^{1/3-\varepsilon}M1/3−ε equals 111. For ε>1/3\varepsilon > 1/3ε>1/3 the exponent is negative, so M1/3−ε≤1M^{1/3-\varepsilon} \le 1M1/3−ε≤1 and the factor decreases as MMM grows. In those cases the required inequality asks only that ratio⁡(I)\operatorname{ratio}(I)ratio(I) be at least the constant CCC, respectively at least a quantity no larger than CCC, which can be chosen as small as desired.
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