Lemma 6.1 — separation probability for one chain
ProvedZhangTangLabelCut.LP2.chain_separation_probabilityintegrality-gaplinear-optimizationoperations-researchp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let and be integers in the shutter construction, in either orientation. Fix a nonempty candidate label set , put , and suppose . Choose a chain whose two ground elements are light for , meaning . Under independent uniform permutations,
This is the single-chain probability bound.
Differences from the source:
- encoding: one-based finite label and chain indices → zero-based Fin indices; reason: reindexing preserves every instance and cardinality
- encoding: Section 4 and Section 6 standing positive integer parameters and d > 8a → the same positive regime, enforced by hypotheses and inhabited chain indices, with d > 8a; reason: these are the source construction regime and p. 17 condition; redundant positivity binders are omitted, and 4a stays real
- 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: independent uniform permutations → finite counting probability on the full product of permutation groups; reason: the sample space has cardinality (d!) to the number of chains
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 chain_separation_probability (k d h : ℕ)
(directed : Bool) (S : Finset (Fin k × Fin d)) (hc : 0 < S.card)
(hreg : 8 * average k S.card < (d : ℝ)) (c : Chain k h)
(hμ : c.1.val.1 ∈ light S) (hν : c.1.val.2 ∈ light S) :
probability k d h (chainSeparated directed S c) ≤ chainBound (average k S.card) d := by sorry
end ZhangTangLabelCut.LP2
Source
Zhang and Tang, Minimum Label s-t Cut has Large Integrality Gaps, arXiv:1908.11491v1 (2019), p. 16, Lemma 6.1; p. 17, standing d > 8a; p. 23, Section 7
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Data. Let , a directed/undirected flag, and . Write .
Hypotheses.
- ;
- ;
- is a chain, with and ;
- both and are light for , meaning each has at most elements of with that first coordinate.
The graph. For each sample (a permutation of for every chain ), take the following graph:
- terminals ;
- for each chain , junctions , , , and middles ;
- edges for and . These are traversable only forward if directed, either way if not.
- For , the edges through are labelled , and those through are labelled .
Claim. Let be uniform over all samples. Then
Degenerate cases:
- The existence of forces and .
- forces , and then .
- So and : the real power is an ordinary one, and the right-hand side lies strictly between and .
- No junk values arise.
- may contain labels whose first coordinate is neither nor , and labels with heavy first coordinates. The directed and undirected cases are both covered.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.