Challenge 3: the Caccetta–Häggkvist conjecture at parameter
DefinitionTenChallenges_Challenge_03The scaled form of Challenge 3. For a natural number , is the Caccetta–Häggkvist statement at minimum out-degree :
It is the predicate of the companion definition, unchanged. Known rungs are ; is open.
import Definitions.Def_TenChallenges_CaccettaHaggkvist namespace TenChallenges /-- The Caccetta–Häggkvist conjecture at minimum out-degree `r`. -/ def statement_03 (r : ℕ) : Prop := CaccettaHaggkvistFor r end TenChallenges
Read-back
What the Lean code literally says, in plain math · claude-fable-5-1
For every natural number , the proposition is defined to be, with no change whatsoever, the proposition (CaccettaHaggkvistFor r) from the imported file. Unfolded completely, asserts:
If , then for every type in the lowest type universe, every finiteness structure on (so is a finite type), every witness that is nonempty, and every digraph on -- a digraph being merely a binary relation on ("there is an arc from to ") with no axioms -- the following holds. If
- for every vertex , (no loops), and
- for every vertex , , where is the natural-number cardinality of a set (the number of elements of a finite set; junk value for an infinite set, which cannot occur here because is finite),
then there exists a natural number such that
where is the number of elements of , the arithmetic is on natural numbers (only multiplication and addition, no truncation), and means: there is an injective map (so are pairwise distinct) such that for every the arc is present; that is, distinct vertices joined by arcs in that direction, with nothing required about other arcs among them.
Edge cases carried over from the definition: is true unconditionally because fails. For , the inequality is equivalent to , i.e. . Looplessness bounds every out-degree by , so when hypothesis 2 is unsatisfiable and the claim holds vacuously for that . The clause excludes the length- "cycle" (which every digraph has vacuously) and the length- cycle (a loop); a length- cycle is a pair of distinct vertices with arcs in both directions. The digraph may contain, for distinct , both arcs and ; in-degrees are unconstrained.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.