five_diamond_ramsey_property_iff_sets
A k-colouring of the subsets of Fin d contains a monochromatic induced copy of the j-diamond exactly when it has, in one colour, a set B, a set T with B ⊂ T, and j pairwise incomparable sets M i with B ⊂ M i ⊂ T for all i.
Statement
theorem five_diamond_ramsey_property_iff_sets (j k d : ℕ) :
poset_ramsey_property (DiamondPoset j) k d ↔
∀ c : Finset (Fin d) → Fin k,
∃ (col : Fin k) (B T : Finset (Fin d)) (M : Fin j → Finset (Fin d)),
c B = col ∧ c T = col ∧ (∀ i, c (M i) = col) ∧
B ⊂ T ∧ (∀ i, B ⊂ M i ∧ M i ⊂ T) ∧
∀ i i', i ≠ i' → ¬ (M i ⊆ M i')- Source
- step towards op_270_five_diamond_poset_ramsey_number
- Verified
- 18 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…
- 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…
- 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…
- Used by 2
- five_diamond_ramsey_property_four_mul_minus_oneFor k ≥ 1, the poset Ramsey property for the 5-diamond fails at 4k-1: the level colouring witnesses it, so R_k(D_5) ≥ 4k.
- five_diamond_ramsey_property_four_mul_leIf every k-colouring (k ≥ 1) of the subsets of Fin d contains a monochromatic induced copy of the 5-diamond DiamondPoset 5, then 4 * k ≤…
The proof, explained
The proof establishes an equivalence between the Ramsey property for the j-diamond poset and an explicit set-containment condition. In the forward direction, given a monochromatic order embedding f of the j-diamond, its values at the bottom, top, and middle elements directly satisfy the required strict inclusions and antichain property. In the backward direction, given sets B, T, and M i satisfying the conditions, a piecewise function g is defined; verifying that g preserves and reflects the poset order across all nine combinations of elements allows OrderEmbedding.ofMapLEIff to construct the required monochromatic order embedding.
In the forward direction, assume the Ramsey property holds, fix a colouring c, and define the candidate sets as the images of the diamond poset elements under the given order embedding.
We split the equivalence into two implications. In the forward direction, given the Ramsey property and an arbitrary k-colouring c of the subsets of Fin d, we obtain a monochromatic order embedding f : DiamondPoset j ↪o Finset (Fin d) with colour col. We set B = f(bot), T = f(top), and M i = f(mid i). Each of these sets has colour col because f is monochromatic.
constructor · rintro h c obtain ⟨f, col, hf⟩ := h c refine ⟨col, f DiamondPoset.bot, f DiamondPoset.top, fun i => f (DiamondPoset.mid i), hf _, hf _, fun i => hf _, ?_, ?_, ?_⟩
The chosen sets satisfy the strict inclusions B ⊂ T and B ⊂ M i ⊂ T for each i.
Since f is an order embedding, it reflects and preserves strict inequalities (f.lt_iff_lt). Using lt_iff_le_not_ge, the strict order relations bot < top and bot < mid i < top hold by definition in DiamondPoset j, which implies B ⊂ T and B ⊂ M i ⊂ T for every index i.
uses
lt_iff_le_not_ge,id· exact f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩) · intro i exact ⟨f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩), f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)⟩
The middle sets M i form an antichain under subset inclusion.
For distinct indices i ≠ i', if we had M i ⊆ M i', then f(mid i) ⊆ f(mid i'). Since order embeddings reflect the partial order (f.le_iff_le), this would imply mid i ≤ mid i' in DiamondPoset j. In DiamondPoset j, mid i ≤ mid i' only holds when i = i', which contradicts i ≠ i'.
· intro i i' hne hle exact hne (f.le_iff_le.mp hle)
In the backward direction, assume the set-theoretic condition and define the piecewise map g from DiamondPoset j to Finset (Fin d).
Given a colouring c, the assumption provides a colour col and sets B, T, and M i satisfying the inclusion and antichain conditions, all coloured col. We define g by sending bot to B, mid i to M i, and top to T.
· intro h c obtain ⟨col, B, T, M, hB, hT, hM, hBT, hMid, hInc⟩ := h c let g : DiamondPoset j → Finset (Fin d) := fun x => match x with | .bot => B | .mid i => M i | .top => T
The function g preserves and reflects the partial order: g a ⊆ g b ↔ a ≤ b for all a, b in DiamondPoset j.
We verify this equivalence by case analysis on a and b (9 cases): - If a = bot, g(bot) = B ⊆ g(b) holds because B ⊆ B by reflexivity (le_refl), B ⊂ M i, and B ⊂ T; similarly, bot ≤ b always holds. - If a = mid i: - b = bot: M i ⊆ B is false because B ⊂ M i, and mid i ≤ bot is false. - b = mid i': M i ⊆ M i' implies i = i' by the antichain hypothesis, matching mid i ≤ mid i'; conversely, if i = i', reflexivity (le_refl) gives M i ⊆ M i. - b = top: M i ⊆ T holds because M i ⊂ T, and mid i ≤ top holds. - If a = top: - b = bot or mid i: T ⊆ B and T ⊆ M i are false because B ⊂ T and M i ⊂ T, and top ≤ b is false. - b = top: T ⊆ T holds by reflexivity (le_refl), and top ≤ top holds.
uses
le_reflhave key : ∀ a b : DiamondPoset j, g a ≤ g b ↔ a ≤ b := by intro a b cases a with | bot => cases b with | bot => exact ⟨fun _ => trivial, fun _ => le_refl B⟩ | mid i => exact ⟨fun _ => trivial, fun _ => (hMid i).1.le⟩ | top => exact ⟨fun _ => trivial, fun _ => hBT.le⟩ | mid i => cases b with | bot => exact ⟨(hMid i).1.not_ge, fun h => h.elim⟩ | mid i' => refine ⟨fun hle => ?_, fun heq => ?_⟩ · by_contra hne exact hInc i i' hne hle · subst heq exact le_refl _ | top => exact ⟨fun _ => trivial, fun _ => (hMid i).2.le⟩ | top => cases b with | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩ | mid i => exact ⟨(hMid i).2.not_ge, fun h => h.elim⟩ | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩
The map g lifts to an order embedding, establishing the monochromatic diamond poset.
Using OrderEmbedding.ofMapLEIff g key, g is elevated to an order embedding from DiamondPoset j into Finset (Fin d). By definition of g, evaluating it at bot, mid i, or top yields B, M i, or T, each of which has colour col. This verifies that all points of the embedded diamond have colour col, proving the Ramsey property.
uses
OrderEmbedding.ofMapLEIffrefine ⟨OrderEmbedding.ofMapLEIff g key, col, fun x => ?_⟩ cases x with | bot => exact hB | mid i => exact hM i | top => exact hT
lt_iff_le_not_ge- In a preorder, strict inequality a < b is equivalent to a ≤ b and ¬(b ≤ a).
id- The identity function, which returns its input unchanged.
le_refl- The reflexivity of the order relation ≤ in a preorder: a ≤ a for every element a.
OrderEmbedding.ofMapLEIff- Constructs an order embedding from a map between a partial order and a preorder, given that the map reflects and preserves ≤.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Unfolds poset_ramsey_property for DiamondPoset j into an explicit bottom/top/antichain condition on the sets. -/theorem five_diamond_ramsey_property_iff_sets (j k d : ℕ) : poset_ramsey_property (DiamondPoset j) k d ↔ ∀ c : Finset (Fin d) → Fin k, ∃ (col : Fin k) (B T : Finset (Fin d)) (M : Fin j → Finset (Fin d)), c B = col ∧ c T = col ∧ (∀ i, c (M i) = col) ∧ B ⊂ T ∧ (∀ i, B ⊂ M i ∧ M i ⊂ T) ∧ ∀ i i', i ≠ i' → ¬ (M i ⊆ M i') := by constructor · rintro h c obtain ⟨f, col, hf⟩ := h c refine ⟨col, f DiamondPoset.bot, f DiamondPoset.top, fun i => f (DiamondPoset.mid i), hf _, hf _, fun i => hf _, ?_, ?_, ?_⟩ · exact f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩) · intro i exact ⟨f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩), f.lt_iff_lt.mpr (by rw [lt_iff_le_not_ge]; exact ⟨trivial, id⟩)⟩ · intro i i' hne hle exact hne (f.le_iff_le.mp hle) · intro h c obtain ⟨col, B, T, M, hB, hT, hM, hBT, hMid, hInc⟩ := h c let g : DiamondPoset j → Finset (Fin d) := fun x => match x with | .bot => B | .mid i => M i | .top => T have key : ∀ a b : DiamondPoset j, g a ≤ g b ↔ a ≤ b := by intro a b cases a with | bot => cases b with | bot => exact ⟨fun _ => trivial, fun _ => le_refl B⟩ | mid i => exact ⟨fun _ => trivial, fun _ => (hMid i).1.le⟩ | top => exact ⟨fun _ => trivial, fun _ => hBT.le⟩ | mid i => cases b with | bot => exact ⟨(hMid i).1.not_ge, fun h => h.elim⟩ | mid i' => refine ⟨fun hle => ?_, fun heq => ?_⟩ · by_contra hne exact hInc i i' hne hle · subst heq exact le_refl _ | top => exact ⟨fun _ => trivial, fun _ => (hMid i).2.le⟩ | top => cases b with | bot => exact ⟨hBT.not_ge, fun h => h.elim⟩ | mid i => exact ⟨(hMid i).2.not_ge, fun h => h.elim⟩ | top => exact ⟨fun _ => trivial, fun _ => le_refl T⟩ refine ⟨OrderEmbedding.ofMapLEIff g key, col, fun x => ?_⟩ cases x with | bot => exact hB | mid i => exact hM i | top => exact hT