petersen_ramsey_red_graph
def
The red graph G_R on 20 vertices, defined as the disjoint union of two complete graphs of order 9 and one complete graph of order 2.
Statement
def petersen_ramsey_red_graph : SimpleGraph (Fin 20)- Defined in
- arXiv:2611.09347 Section 3
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 1
- petersen_ramsey_blue_graphThe blue graph G_B on 20 vertices, defined as the graph complement of the red graph G_R, isomorphic to the join graph K_{9,9} ∨ K_2ᶜ.
Read back from the Lean
Definition of petersen_ramsey_red_graph as the SimpleGraph on vertex type Fin 20 where two vertices u and v are adjacent if and only if u ≠ v and at least one of the following holds:
1. u.val < 9 and v.val < 9,
2. 9 ≤ u.val < 18 and 9 ≤ v.val < 18, or
3. 18 ≤ u.val and 18 ≤ v.val.
(Equivalently, the disjoint union of complete graphs $K_9$, $K_9$, and $K_2$ on $\{0, \dots, 8\}$, $\{9, \dots, 17\}$, and $\{18, 19\}$.)
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The red graph on 20 vertices for the Petersen Ramsey lower bound, formed by the disjoint union of two copies of K_9 and one copy of K_2. -/ def petersen_ramsey_red_graph : SimpleGraph (Fin 20) := { Adj := fun u v => u ≠ v ∧ ((u.val < 9 ∧ v.val < 9) ∨ (9 ≤ u.val ∧ u.val < 18 ∧ 9 ≤ v.val ∧ v.val < 18) ∨ (18 ≤ u.val ∧ 18 ≤ v.val)) symm := ⟨fun u v h => by rcases h with ⟨hne, h | h | h⟩ · exact ⟨hne.symm, Or.inl ⟨h.2, h.1⟩⟩ · exact ⟨hne.symm, Or.inr (Or.inl ⟨h.2.2.1, h.2.2.2, h.1, h.2.1⟩)⟩ · exact ⟨hne.symm, Or.inr (Or.inr ⟨h.2, h.1⟩)⟩⟩ loopless := ⟨fun u h => h.1 rfl⟩ }