Theorem 7 — exact two-regular values, gap, unique optimizer, and Stieltjes measure
OpenRankingCertGap.Supplement.theorem_7asymptotic-analysisonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-primal-dualranking-algorithm
On nonempty two-regular bipartite instances,
The unique optimizer over equals on and at , and its Stieltjes measure is
This identifies the entire two-regular certifying gap and shows that it is not caused by a suboptimal monotone profile.
Formalization Note The theorem is over ; the published goal separately establishes the same capacity over the larger class .
Differences from the source:
- encoding: profiles and Stieltjes measures on → total real profiles and probability measures on identified by lower-interval values on ; reason: this matches the published profile representation without changing source values
- encoding: unique optimizer on → equality at every point of ; reason: values outside the source domain are irrelevant
Preamble
import Mathlib import Definitions.Def_RankingCertGap_Supplement_Objects set_option autoImplicit false open MeasureTheory
Formal statement
namespace RankingCertGap.Supplement
/-- **Theorem 7 (Two-regular graphs: exact values and gap).** Xu, arXiv:2610.17545 (held file
sha256 75896dd9…), Theorem 7, p.10, eqs. (26)–(27). The capacity, competitiveness and gap are
exact, `fTilde` is the unique optimizer over `𝒽`, and its Stieltjes measure is the printed two-atom
probability measure.
**Formalization Note.** This theorem is over `classF`; the published Proposition 2 separately gives
the same capacity over the larger class `classA`. Optimizer equality is pointwise on `[0,1]`. -/
theorem theorem_7 :
GammaC classF (regular 2) = 3 / 4 ∧
gammaC (regular 2) = 119 / 144 ∧
gapC classF (regular 2) = 11 / 144 ∧
fTilde ∈ classF ∧
chiC fTilde (regular 2) = GammaC classF (regular 2) ∧
(∀ f : ℝ → ℝ, f ∈ classF →
chiC f (regular 2) = GammaC classF (regular 2) →
∀ y ∈ Set.Icc (0 : ℝ) 1, f y = fTilde y) ∧
HasStieltjesMeasure fTilde
(ENNReal.ofReal (3 / 4) • Measure.dirac (0 : ℝ) +
ENNReal.ofReal (1 / 4) • Measure.dirac (1 : ℝ)) := by sorry
end RankingCertGap.Supplement
Source
Xu, Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking, arXiv:2610.17545 (held file sha256 75896dd9…), Theorem 7, p.10, eqs. (26)–(27)