Section 3 — if a sink exists, the king is unique and equal to the sink
ProvedRvsCert.sink_unique_kingp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexitytournaments
Let be a tournament on and let be a sink of (it beats every other vertex). Then is a king, and every king of equals .
This lets the king-finding algorithm of Mande, Paraashar and Saurabh replace a sink-finding algorithm in the second stage of Lemma 5.
Differences from the source:
- encoding: an orientation of the complete graph, arcs from loser to winner → bits per pair (u < v) with
beats: bit 1 means u beats v; reason: the arc bits of the SINK input; one fixed convention
Preamble
import Mathlib import Definitions.Def_RvsCert_IsSink import Definitions.Def_RvsCert_IsKing
Formal statement
namespace RvsCert
/-- **Section 3, second stage** (p.4 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "In a general input, a king is
not unique; however, if a sink exists, then the king is unique and equal to the sink." In every
tournament on `Fin m` with a sink `s`, `s` is a king and every king equals `s`. -/
theorem sink_unique_king (m : ℕ) (x : TPair m → Bool) (s : Fin m) (hs : IsSink x s) :
IsKing x s ∧ ∀ v : Fin m, IsKing x v → v = s := by sorry
end RvsCert
Source
Ben-David–Kothari, Randomized query complexity can beat certificate complexity, arXiv:2609.15063v1, Section 3, second stage, p.4
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.