Cslib.infinite_graph_ramsey
theoremverifiedformalizationimported Lean
If the edges of an infinite complete graph is assigned a finite number of colors, then there must exist a color c and an infinite set s of vertices such that the edge between any two vertices of s is assigned the same color c.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Function Set in variable {Vertex Color : Type*} [Finite Color] (color : Finset Vertex → Color) in variable [Infinite Vertex] in theorem Cslib.infinite_graph_ramsey : ∃ c : Color, ∃ s : Set Vertex, s.Infinite ∧ ∀ e : Finset Vertex, e.card = 2 → ↑e ⊆ s → color e = c
- Formalizes
- CSLib, `Cslib.infinite_graph_ramsey`
- Lean proof
- By Ching-Tsun Chou, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2026 Ching-Tsun Chou. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.infinite_graph_ramsey← Cslib.infinite_graph_ramsey (Cslib/Foundations/Combinatorics/InfiniteGraphRamsey.lean:123): verbatim
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- Cslib.infinite_pigeonhole_principleAn infinite pigeonhole principle.
- Cslib.good_selections_existThere exist an infinite sequence
vsof vertex sets, an infinite sequencevof vertices, and an infinite sequencecof colors such…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inopen Function Set invariable {Vertex Color : Type*} [Finite Color] (color : Finset Vertex → Color) invariable [Infinite Vertex] in/-- If the edges of an infinite complete graph is assigned a finite number of colors, then there must exist a color `c` and an infinite set `s` of vertices such that the edge between any two vertices of `s` is assigned the same color `c`. -/theorem Cslib.infinite_graph_ramsey : ∃ c : Color, ∃ s : Set Vertex, s.Infinite ∧ ∀ e : Finset Vertex, e.card = 2 → ↑e ⊆ s → color e = c := by classical obtain ⟨vs, v, c, h_sel⟩ := good_selections_exist color simp only [forall_and] at h_sel obtain ⟨h_vs, h_v, h_c⟩ := h_sel have : ∀ m n, m < n → v n ∈ vs m := by intro m n h_mn suffices h1 : (⋂ m < n, vs m) ⊆ vs m by grind exact biInter_subset_of_mem h_mn obtain ⟨c', s', h_s'_inf, h_s'_col⟩ : ∃ c' : Color, ∃ s' : Set ℕ, s'.Infinite ∧ ∀ n ∈ s', c n = c' := by obtain ⟨c', s', h_s'_inf, _, h_s'col⟩ := infinite_pigeonhole_principle c infinite_univ use c', s' use c', (v '' s') have h_v_inj : Injective v := by intro _ _ grind split_ands · exact Infinite.image (injOn_of_injective h_v_inj (s := s')) h_s'_inf · simp only [Finset.card_eq_two] grind [Finset.pair_comm, Finset.coe_insert, Finset.coe_singleton]