Prove2Me
Navigate
DiscoverFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Three-colored tournaments and monochromatic reachability

Definition
opg1808_colored_tournaments

by hao jia · Sep 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsdirected-graphsgraph-theoryopen-problemtournaments

This 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 sss monochromatically reaches ttt when some one color supports a directed path from sss to ttt. Reachability is reflexive, so the path may have length zero when s=ts=ts=t. A monochromatic source reaches every target in this sense, and the chosen path color may depend on the target.

Definition code
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 OPG1808
Source
Open Problem Garden, Monochromatic reachability versus rainbow triangles, https://www.openproblemgarden.org/op/monochromatic_reachability_vs_rainbow_triangles
Read-back

What the Lean code literally says, in plain math · gpt-5.6-luna

For any type VVV, a digraph on VVV is a binary relation DDD assigning a proposition D(u,v)D(u,v)D(u,v) to each ordered pair of vertices. An arc coloring on VVV is a function assigning to every ordered pair (u,v)(u,v)(u,v) one of the three colors in Fin(3)\mathrm{Fin}(3)Fin(3).

For a digraph DDD on VVV, IsTournament(D)\mathrm{IsTournament}(D)IsTournament(D) asserts that no vertex has a loop, and that for every pair of distinct vertices u,vu,vu,v, at least one of D(u,v)D(u,v)D(u,v) and D(v,u)D(v,u)D(v,u) holds while they do not both hold. Thus exactly one directed arc is present between every pair of distinct vertices.

For a digraph DDD and coloring color\mathrm{color}color, HasRainbowDirectedTriangle(D,color)\mathrm{HasRainbowDirectedTriangle}(D,\mathrm{color})HasRainbowDirectedTriangle(D,color) asserts that there exist vertices a,b,ca,b,ca,b,c such that a≠ba\ne ba=b, b≠cb\ne cb=c, and c≠ac\ne ac=a, with directed arcs a→ba\to ba→b, b→cb\to cb→c, and c→ac\to ac→a, and with the three colors color(a,b)\mathrm{color}(a,b)color(a,b), color(b,c)\mathrm{color}(b,c)color(b,c), and color(c,a)\mathrm{color}(c,a)color(c,a) pairwise distinct.

MonochromaticallyReaches(D,color,s,t)\mathrm{MonochromaticallyReaches}(D,\mathrm{color},s,t)MonochromaticallyReaches(D,color,s,t) asserts that there exists a color k∈Fin(3)k\in\mathrm{Fin}(3)k∈Fin(3) and a directed path from sss to ttt consisting of zero or more steps, every step x→yx\to yx→y satisfying D(x,y)D(x,y)D(x,y) and having color(x,y)=k\mathrm{color}(x,y)=kcolor(x,y)=k. Because zero steps are allowed, every vertex reaches itself monochromatically for any available color.

IsMonochromaticSource(D,color,s)\mathrm{IsMonochromaticSource}(D,\mathrm{color},s)IsMonochromaticSource(D,color,s) asserts that for every vertex t∈Vt\in Vt∈V, the vertex sss monochromatically reaches ttt in the preceding sense. The color and path may be chosen separately for each target ttt.

Human review
  • Endorsed by Shuze Chen · Sep 7, 2026

  • Endorsed by hao jia · Sep 7, 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.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me