Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.1 — separation probability for one chain

Proved
ZhangTangLabelCut.LP2.chain_separation_probability

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

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

Let k≥2k\ge2k≥2 and d,h>0d,h>0d,h>0 be integers in the shutter construction, in either orientation. Fix a nonempty candidate label set SSS, put a=∣S∣/ka=|S|/ka=∣S∣/k, and suppose d>8ad>8ad>8a. Choose a chain CμνiC^i_{\mu\nu}Cμνi​ whose two ground elements are light for SSS, meaning ∣Jμ∣,∣Jν∣≤4a|J_\mu|,|J_\nu|\le4a∣Jμ​∣,∣Jν​∣≤4a. Under independent uniform permutations,

P[S separates s,t in Cμνi]≤1−(1−8a/d)4a.\mathbb P[S\text{ separates }s,t\text{ in }C^i_{\mu\nu}]\le1-(1-8a/d)^{4a}.P[S separates s,t in Cμνi​]≤1−(1−8a/d)4a.

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 k,d,h∈Nk, d, h \in \mathbb Nk,d,h∈N, a directed/undirected flag, and S⊆{0..k−1}×{0..d−1}S \subseteq \{0..k-1\} \times \{0..d-1\}S⊆{0..k−1}×{0..d−1}. Write a=∣S∣/ka = |S|/ka=∣S∣/k.

Hypotheses.

  • ∣S∣≥1|S| \ge 1∣S∣≥1;
  • 8a<d8a < d8a<d;
  • c=(μ,ν,i)c = (\mu, \nu, i)c=(μ,ν,i) is a chain, with μ<ν<k\mu < \nu < kμ<ν<k and i<hi < hi<h;
  • both μ\muμ and ν\nuν are light for SSS, meaning each has at most 4a4a4a elements of SSS with that first coordinate.

The graph. For each sample σ\sigmaσ (a permutation σc′\sigma_{c'}σc′​ of {0..d−1}\{0..d-1\}{0..d−1} for every chain c′c'c′), take the following graph:

  • terminals s,ts, ts,t;
  • for each chain c′c'c′, junctions Jc′(0)=sJ_{c'}(0) = sJc′​(0)=s, Jc′(1),…,Jc′(d−1)J_{c'}(1), \dots, J_{c'}(d-1)Jc′​(1),…,Jc′​(d−1), Jc′(d)=tJ_{c'}(d) = tJc′​(d)=t, and middles Mc′(j,a′)M_{c'}(j, a')Mc′​(j,a′);
  • edges Jc′(j)→Mc′(j,a′)→Jc′(j+1)J_{c'}(j) \to M_{c'}(j, a') \to J_{c'}(j+1)Jc′​(j)→Mc′​(j,a′)→Jc′​(j+1) for j<dj < dj<d and a′∈{0,1}a' \in \{0, 1\}a′∈{0,1}. These are traversable only forward if directed, either way if not.
  • For c′=(μ′,ν′,i′)c' = (\mu', \nu', i')c′=(μ′,ν′,i′), the edges through Mc′(j,0)M_{c'}(j, 0)Mc′​(j,0) are labelled (μ′,j)(\mu', j)(μ′,j), and those through Mc′(j,1)M_{c'}(j, 1)Mc′​(j,1) are labelled (ν′,σc′(j))(\nu', \sigma_{c'}(j))(ν′,σc′​(j)).

Claim. Let Pr⁡\PrPr be uniform over all (d!)h(k2)(d!)^{h\binom k2}(d!)h(2k​) samples. Then

Pr⁡σ[every simple s–t path using only edges of chain c has an edge labelled in S] ≤ 1−(1−8ad)4a.\Pr_\sigma\big[\text{every simple } s\text{–}t \text{ path using only edges of chain } c \text{ has an edge labelled in } S\big] \ \le\ 1 - \Big(1 - \frac{8a}{d}\Big)^{4a}.σPr​[every simple s–t path using only edges of chain c has an edge labelled in S] ≤ 1−(1−d8a​)4a.

Degenerate cases:

  • The existence of ccc forces k≥2k \ge 2k≥2 and h≥1h \ge 1h≥1.
  • ∣S∣≥1|S| \ge 1∣S∣≥1 forces d≥1d \ge 1d≥1, and then d>8a>0d > 8a > 0d>8a>0.
  • So 1−8a/d∈(0,1)1 - 8a/d \in (0, 1)1−8a/d∈(0,1) and 4a>04a > 04a>0: the real power is an ordinary one, and the right-hand side lies strictly between 000 and 111.
  • No junk values arise.
  • SSS may contain labels whose first coordinate is neither μ\muμ nor ν\nuν, and labels with heavy first coordinates. The directed and undirected cases are both covered.
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