Theorem 1.1 — nearly cube-root gap in the edge budget
ProvedZhangTangLabelCut.LP2.edge_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 edge 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 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
import Definitions.Def_ZhangTangLabelCut_LP2_FiniteGraph import Definitions.Def_ZhangTangLabelCut_LP2_CoveringLP import Definitions.Def_ZhangTangLabelCut_LP2_LabelCut
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every real number there exist a real constant and a natural number such that the following holds. For every natural number , and for each of the two values of a Boolean flag , there exists a label-cut instance with:
- the graph of has directedness flag equal to ;
- is admissible (defined below);
- the number of edges satisfies ;
- the ratio of is large:
The exponent is a real number, and is the real power of the positive real . The quantifier order matters. and depend only on , and the same pair must work for both values of . The instance may depend on , and . enters only as an upper bound on the edge count, and the lower bound on the ratio is stated in terms of , not in terms of .
The graph. A finite graph consists of:
- a finite vertex type and a finite edge type ;
- maps ;
- a Boolean flag "directed".
An edge traverses from to if either:
- and ; or
- the graph is undirected (flag false), and .
is simple if both of the following hold:
- no edge has ;
- any two edges are equal whenever they have the same tail and the same head, or whenever the graph is undirected and , .
So in the directed case, two edges and are both permitted.
Paths. An – path consists of:
- a length ;
- vertices that are pairwise distinct, with and ;
- edges such that each traverses from to .
The instance. A label-cut instance consists of:
- a finite graph as above;
- a finite label type and a labelling map ;
- two vertices with .
The label set of a path is
A finite set is a cut if every – path has some edge with .
is the infimum, over the natural numbers, of the cardinalities of cuts .
The linear program. The LP of has one real variable per label . A vector is feasible if:
- for all (there are no upper bounds);
- for every subset that equals for at least one – path , the covering constraint holds:
There is one constraint per distinct label set, not one per path. The objective is .
The value of the LP is the infimum, in the extended reals , of the objective over all feasible . It is if no is feasible.
is this value converted to a real number. That conversion sends to .
The ratio is the real quotient
Admissibility. is admissible if all of the following hold:
- is simple;
- at least one – path exists;
- the LP value equals some real number with .
In that case .
Degenerate cases.
- Small or zero sizes. Since , the case never arises. A graph with no edges is excluded by . Since there is an edge and maps edges to labels, is nonempty, but it may have a single element. Since , has at least two vertices.
- Paths. Every – path has length , so every label set is nonempty.
- The infimum defining . The full label set is always a cut, so the set of cut sizes is never empty and 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 .
- The LP value. The defaults (the value for an infeasible LP, and the conversion of to ) are excluded by the admissibility requirement that the value be a finite positive real. Hence the division in is never by zero, and .
- Large . The statement places no upper bound on . For the factor equals . For the exponent is negative, so and the factor decreases as grows. In those cases the required inequality asks only that be at least the constant , respectively at least a quantity no larger than , which can be chosen as small as desired.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.