five_diamond_step_of_colour_free_copy
theoremverified
Assembly: if the induction hypothesis holds at (k, 4k) and every D5-free (k+1)-colouring of the subsets of Fin(4(k+1)) has an order-embedded copy of the Boolean lattice B_{4k} on which one colour is never used, then the (k+1)-colour Ramsey property holds at dimension 4(k+1).
Statement
theorem five_diamond_step_of_colour_free_copy (k : ℕ) (hk : 2 ≤ k)
(ih : poset_ramsey_property (DiamondPoset 5) k (4 * k))
(hc : ∀ (c : Finset (Fin (4 * (k + 1))) → Fin (k + 1)),
(∀ (f : DiamondPoset 5 ↪o Finset (Fin (4 * (k + 1)))) (col : Fin (k + 1)),
∃ x : DiamondPoset 5, c (f x) ≠ col) →
∃ (e : Finset (Fin (4 * k)) ↪o Finset (Fin (4 * (k + 1)))) (a : Fin (k + 1)),
∀ A : Finset (Fin (4 * k)), c (e A) ≠ a) :
poset_ramsey_property (DiamondPoset 5) (k + 1) (4 * (k + 1))- Source
- step towards five_diamond_ramsey_property_step
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- DiamondPosetFor a natural number j, DiamondPoset j is the type consisting of a bottom element bot, a top element top, and j middle elements indexed by…
- inst_partial_order_diamond_posetThe partial order on DiamondPoset j where bot is less than or equal to every element, every element is less than or equal to top, and two…
- poset_ramsey_propertyFor a preordered type P and natural numbers k and d, poset_ramsey_property P k d asserts that for every coloring c : Finset (Fin d) → Fin…
Lean source view module on GitHub
/-- Reduction of the induction step to a single combinatorial crux: a D5-free (k+1)-colouring misses a colour on some order-embedded B_{4k}. -/ theorem five_diamond_step_of_colour_free_copy (k : ℕ) (hk : 2 ≤ k) (ih : poset_ramsey_property (DiamondPoset 5) k (4 * k)) (hc : ∀ (c : Finset (Fin (4 * (k + 1))) → Fin (k + 1)), (∀ (f : DiamondPoset 5 ↪o Finset (Fin (4 * (k + 1)))) (col : Fin (k + 1)), ∃ x : DiamondPoset 5, c (f x) ≠ col) → ∃ (e : Finset (Fin (4 * k)) ↪o Finset (Fin (4 * (k + 1)))) (a : Fin (k + 1)), ∀ A : Finset (Fin (4 * k)), c (e A) ≠ a) : poset_ramsey_property (DiamondPoset 5) (k + 1) (4 * (k + 1)) := by classical intro c by_cases hfree : ∃ (f : DiamondPoset 5 ↪o Finset (Fin (4 * (k + 1)))) (col : Fin (k + 1)), ∀ x : DiamondPoset 5, c (f x) = col · exact hfree · push Not at hfree obtain ⟨e, a, he⟩ := hc c hfree have hcard : Fintype.card {b : Fin (k + 1) // b ≠ a} = k := by rw [Fintype.card_subtype] simp only [Finset.filter_ne'] rw [Finset.card_erase_of_mem (Finset.mem_univ a), Finset.card_univ, Fintype.card_fin] omega let φ : {b : Fin (k + 1) // b ≠ a} ≃ Fin k := Fintype.equivFinOfCardEq hcard let c' : Finset (Fin (4 * k)) → Fin k := fun A => φ ⟨c (e A), he A⟩ obtain ⟨g, col, hg⟩ := ih c' refine ⟨g.comp e, (φ.symm col).val, ?_⟩ intro x have h1 : φ.symm col = ⟨c (e (g x)), he (g x)⟩ := by rw [← hg x] exact φ.symm_apply_apply _ show c (e (g x)) = (φ.symm col).val rw [h1]