Three-colored tournaments and monochromatic reachability
Definitionopg1808_colored_tournamentsThis module models a tournament as a loopless binary relation with exactly one directed arc between every two distinct vertices. An arc coloring has three labeled colors; only colors of actual arcs matter.
A rainbow directed triangle is a cyclically oriented triangle whose three arc colors are pairwise distinct. A vertex monochromatically reaches when some one color supports a directed path from to . Reachability is reflexive, so the path may have length zero when . A monochromatic source reaches every target in this sense, and the chosen path color may depend on the target.
import Mathlib.Data.Fintype.Card
import Mathlib.Logic.Relation
namespace OPG1808
universe u
abbrev Digraph (V : Type u) := V → V → Prop
abbrev ArcColoring (V : Type u) := V → V → Fin 3
/-- A loopless orientation of every pair of distinct vertices. -/
def IsTournament {V : Type u} (D : Digraph V) : Prop :=
(∀ v : V, ¬ D v v) ∧
∀ ⦃u v : V⦄, u ≠ v →
(D u v ∨ D v u) ∧ ¬ (D u v ∧ D v u)
/-- A rainbow directed triangle follows the displayed cyclic orientation and
uses three pairwise distinct arc colors. -/
def HasRainbowDirectedTriangle {V : Type u} (D : Digraph V)
(color : ArcColoring V) : Prop :=
∃ a b c : V,
a ≠ b ∧ b ≠ c ∧ c ≠ a ∧
D a b ∧ D b c ∧ D c a ∧
color a b ≠ color b c ∧
color b c ≠ color c a ∧
color c a ≠ color a b
/-- There is a directed path from `s` to `t` whose arcs all have one color.
The chosen color may depend on the ordered pair. -/
def MonochromaticallyReaches {V : Type u} (D : Digraph V)
(color : ArcColoring V) (s t : V) : Prop :=
∃ k : Fin 3,
Relation.ReflTransGen (fun x y => D x y ∧ color x y = k) s t
/-- A vertex reaches every vertex by a monochromatic directed path; different
targets may use different colors. -/
def IsMonochromaticSource {V : Type u} (D : Digraph V)
(color : ArcColoring V) (s : V) : Prop :=
∀ t : V, MonochromaticallyReaches D color s t
end OPG1808Read-back
What the Lean code literally says, in plain math · gpt-5.6-luna
For any type , a digraph on is a binary relation assigning a proposition to each ordered pair of vertices. An arc coloring on is a function assigning to every ordered pair one of the three colors in .
For a digraph on , asserts that no vertex has a loop, and that for every pair of distinct vertices , at least one of and holds while they do not both hold. Thus exactly one directed arc is present between every pair of distinct vertices.
For a digraph and coloring , asserts that there exist vertices such that , , and , with directed arcs , , and , and with the three colors , , and pairwise distinct.
asserts that there exists a color and a directed path from to consisting of zero or more steps, every step satisfying and having . Because zero steps are allowed, every vertex reaches itself monochromatically for any available color.
asserts that for every vertex , the vertex monochromatically reaches in the preceding sense. The color and path may be chosen separately for each target .
Confirmed by the mission captain (proposal self-audit).