five_diamond_ramsey_property_four_mul_le
If 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 ≤ d. Equivalently, the colouring A ↦ min (k-1) (|A| / 4) of the Boolean lattice on fewer than 4k points has no monochromatic induced 5-diamond.
Statement
theorem five_diamond_ramsey_property_four_mul_le (k d : ℕ) (hk : 1 ≤ k)
(hd : poset_ramsey_property (DiamondPoset 5) k d) : 4 * k ≤ d- Source
- step towards five_diamond_poset_ramsey_number_ge
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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…
- 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…
- five_diamond_ramsey_property_iff_setsA 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,…
- five_diamond_level_coloringFor k ≥ 1, the colouring of the subsets of Fin d that sends A to the minimum of k-1 and |A| divided by 4 (as an element of Fin k).
- five_diamond_level_coloring_interval_card_le_threeLet k ≥ 1 and d ≤ 4k-1. If B ⊂ T are subsets of Fin d with min (k-1) (|B|/4) = min (k-1) (|T|/4), then |T \ B| ≤ 3.
- Used by 1
- five_diamond_poset_ramsey_number_geFor every natural number k with 1 ≤ k, the k-color poset Ramsey number of the 5-diamond DiamondPoset 5 is at least 4 * k.
The proof, explained
We prove the contrapositive by contradiction: assuming d < 4k, the level colouring A ↦ min(k - 1, ⌊|A| / 4⌋) on the Boolean lattice of Fin d must contain a monochromatic induced 5-diamond by the Ramsey property. In this monochromatic diamond, the top set T and bottom set B have the same colour, forcing |T \ B| ≤ 3. The five middle sets M(i) then yield five subsets M(i) \ B ⊆ T \ B that inherit pairwise incomparability from the M(i). But by Sperner's theorem, an antichain in a set of size at most 3 can have size at most 3, so any five subsets must contain a comparable pair, yielding a contradiction.
The subtype restriction map from subsets of X to subsets of the subtype X is injective on 𝒜, so |𝒜| equals the size of its image.
Because every set S in 𝒜 is a subset of X, mapping S to the subtype X via Finset.subtype preserves S, which shows injectivity using Finset.subtype_map_of_mem. By Finset.card_image_of_injOn, the cardinality of 𝒜 equals the cardinality of its image under this restriction.
uses
Finset.subtype_map_of_mem,Finset.card_image_of_injOnlet p := fun a => a ∈ X have hinj : Set.InjOn (Finset.subtype p) 𝒜 := by intro S hS T hT hST have h1 := Finset.subtype_map_of_mem (fun x hx => hsub S hS hx) have h2 := Finset.subtype_map_of_mem (fun x hx => hsub T hT hx) rw [← h1, ← h2, hST] have hcard : 𝒜.card = (𝒜.image (Finset.subtype p)).card := (Finset.card_image_of_injOn hinj).symm
The image of 𝒜 under subtype restriction is an antichain of subsets of the subtype X.
Given distinct sets in the image arising from S, T in 𝒜, any inclusion between them would imply S ⊆ T by checking elements. Since 𝒜 is an antichain and S ≠ T, this is impossible.
uses
Finset.mem_coe,Finset.mem_image,Finset.mem_subtypehave hantiB : IsAntichain (· ⊆ ·) ((𝒜.image (Finset.subtype p) : Finset (Finset (Subtype p))) : Set (Finset (Subtype p))) := by intro A hA B hB hne rw [Finset.mem_coe, Finset.mem_image] at hA hB obtain ⟨S, hS, rfl⟩ := hA obtain ⟨T, hT, rfl⟩ := hB intro hle have hST_ne : S ≠ T := by rintro rfl; exact hne rfl have hST_le : S ⊆ T := by intro x hx have hx_sub : (⟨x, hsub S hS hx⟩ : Subtype p) ∈ Finset.subtype p S := by rw [Finset.mem_subtype]; exact hx have := hle hx_sub rw [Finset.mem_subtype] at this exact this exact hanti (Finset.mem_coe.mpr hS) (Finset.mem_coe.mpr hT) hST_ne hST_le
The cardinality of 𝒜 is at most 3.
By Sperner's theorem (IsAntichain.sperner), the size of the restricted antichain is at most the central binomial coefficient of |X|. Since |X| ≤ 3, a finite case check shows this binomial coefficient is at most 3, so |𝒜| ≤ 3.
uses
IsAntichain.sperner,Fintype.card_coehave hsperner := IsAntichain.sperner hantiB have hFcard : Fintype.card (Subtype p) = X.card := Fintype.card_coe X rw [hFcard] at hsperner have h3 : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> decide omega
If no two sets among M(0), ..., M(4) are comparable, then M is injective and its image has size 5.
If M(i) = M(j) for distinct i and j, then M(i) ⊆ M(j), which contradicts incomparability. Thus M is injective, so its image 𝒜 on the 5-element domain Fin 5 has size 5.
uses
subset_rfl,Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finby_contra! h have hinj : Function.Injective M := by intro i j hij by_contra hne exact (h i j hne).1 (hij ▸ subset_rfl) let 𝒜 := Finset.image M Finset.univ have hcard : 𝒜.card = 5 := by rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]
Incomparability of all five subsets M(i) of X yields a contradiction.
The image 𝒜 consists of subsets of X and forms an antichain by the assumed incomparability. By five_diamond_ramsey_property_four_mul_le_antichain_card_le_three, |𝒜| ≤ 3, which contradicts |𝒜| = 5.
uses
Finset.mem_image,Finset.mem_coe,five_diamond_ramsey_property_four_mul_le_antichain_card_le_threehave hsub : ∀ S ∈ 𝒜, S ⊆ X := by intro S hS rw [Finset.mem_image] at hS obtain ⟨i, -, rfl⟩ := hS exact hM i have hanti : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α)) := by intro A hA B hB hne hle rw [Finset.mem_coe, Finset.mem_image] at hA hB obtain ⟨i, -, rfl⟩ := hA obtain ⟨j, -, rfl⟩ := hB have hij : i ≠ j := by rintro rfl; exact hne rfl exact (h i j hij).1 hle have := five_diamond_ramsey_property_four_mul_le_antichain_card_le_three hX 𝒜 hsub hanti omega
Assuming d < 4k, the level colouring yields a monochromatic induced 5-diamond.
We argue by contradiction. If d < 4k, then d ≤ 4k - 1. Applying the Ramsey property for the 5-diamond to the level colouring c(A) = min(k - 1, ⌊|A| / 4⌋) gives a bottom set B, top set T, and five middle sets M(i) all sharing the same colour, with B ⊂ M(i) ⊂ T and the M(i) pairwise incomparable.
uses
five_diamond_ramsey_property_iff_sets,five_diamond_level_coloringclassical by_contra! h have hd_le : d ≤ 4 * k - 1 := by omega have hprop := (five_diamond_ramsey_property_iff_sets 5 k d).mp hd (five_diamond_level_coloring k d hk) obtain ⟨col, B, T, M, hcB, hcT, hcM, hBT, hBMT, hincomp⟩ := hprop
The difference T \ B has size at most 3.
Since B and T have the same colour under the level colouring and B ⊂ T with universe size d ≤ 4k - 1, five_diamond_level_coloring_interval_card_le_three shows that |T \ B| ≤ 3.
uses
five_diamond_level_coloring,five_diamond_level_coloring_interval_card_le_threehave hcol_eq : five_diamond_level_coloring k d hk B = five_diamond_level_coloring k d hk T := by rw [hcB, hcT] have hcard : (T \ B).card ≤ 3 := five_diamond_level_coloring_interval_card_le_three k d hk hd_le B T hBT hcol_eq
The relative middle sets M(i) \ B are subsets of T \ B and are pairwise incomparable.
Since M(i) ⊆ T, we have M(i) \ B ⊆ T \ B. If M(i) \ B ⊆ M(i') \ B for distinct i, i', taking the union with B (which is contained in both M(i) and M(i')) would imply M(i) ⊆ M(i'), contradicting the incomparability of M(i) and M(i').
uses
Finset.sdiff_subset_sdiff,le_refl,Finset.sdiff_union_of_subset,Finset.union_subset_unionhave hDi_sub : ∀ i : Fin 5, M i \ B ⊆ T \ B := by intro i exact Finset.sdiff_subset_sdiff (hBMT i).2.1 (le_refl B) have hDinc : ∀ i i' : Fin 5, i ≠ i' → ¬ (M i \ B ⊆ M i' \ B) := by intro i i' hne hsub apply hincomp i i' hne have hBi : B ⊆ M i := (hBMT i).1.le have hBi' : B ⊆ M i' := (hBMT i').1.le calc M i = M i \ B ∪ B := (Finset.sdiff_union_of_subset hBi).symm _ ⊆ M i' \ B ∪ B := Finset.union_subset_union hsub (le_refl B) _ = M i' := Finset.sdiff_union_of_subset hBi'
The five subsets M(i) \ B must contain a comparable pair, which is a contradiction.
Applying five_diamond_ramsey_property_four_mul_le_five_subsets to the five subsets M(i) \ B of T \ B (which has size at most 3) gives distinct i, i' such that M(i) \ B and M(i') \ B are comparable, contradicting their incomparability.
uses
five_diamond_ramsey_property_four_mul_le_five_subsets,Ne.symmobtain ⟨i, i', hne, hcomp⟩ := five_diamond_ramsey_property_four_mul_le_five_subsets (T \ B) hcard (fun i => M i \ B) hDi_sub rcases hcomp with hc | hc · exact hDinc i i' hne hc · exact hDinc i' i (Ne.symm hne) hc
Finset.subtype_map_of_mem- If every element of a finite set s satisfies a predicate p, mapping the subtype restriction of s back to the ambient type recovers s.
Finset.card_image_of_injOn- If a function f is injective on a finite set s, then the image of s under f has the same cardinality as s.
Finset.mem_coe- An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
Finset.mem_image- An element b belongs to the image f(s) if and only if b = f(a) for some a in s.
Finset.mem_subtype- A subtype element belongs to the subtype restriction of a finite set s if and only if its underlying value belongs to s.
IsAntichain.sperner- Sperner's theorem: any antichain of subsets of a finite set α under inclusion has size at most the central binomial coefficient of |α|.
Fintype.card_coe- The cardinality of a finite set viewed as a subtype equals its cardinality as a Finset.
subset_rfl- Subset inclusion is reflexive: every set is a subset of itself.
Finset.card_image_of_injective- The image of a finite set under an injective function has the same cardinality as the domain set.
Finset.card_univ- The cardinality of the universal finset on a finite type α equals the cardinality of the type.
Fintype.card_fin- The finite type Fin n has cardinality n.
five_diamond_ramsey_property_four_mul_le_antichain_card_le_three- Any antichain of subsets of a set of cardinality at most 3 has cardinality at most 3.
five_diamond_ramsey_property_iff_sets- The Ramsey property for the j-diamond poset is equivalent to every k-colouring admitting a monochromatic induced diamond (bottom, top, and j pairwise incomparable middle sets).
five_diamond_level_coloring- The colouring of subsets A by min(k - 1, ⌊|A| / 4⌋).
five_diamond_level_coloring_interval_card_le_three- Under the level colouring on a universe of size at most 4k - 1, any monochromatic strict interval B ⊂ T satisfies |T \ B| ≤ 3.
Finset.sdiff_subset_sdiff- Set difference preserves inclusion: if s ⊆ t and v ⊆ u, then s \ u ⊆ t \ v.
le_refl- The ordering relation is reflexive: a ≤ a.
Finset.sdiff_union_of_subset- If s₁ ⊆ s₂, then (s₂ \ s₁) ∪ s₁ = s₂.
Finset.union_subset_union- Taking unions preserves inclusion: if s ⊆ u and t ⊆ v, then s ∪ t ⊆ u ∪ v.
five_diamond_ramsey_property_four_mul_le_five_subsets- Any five subsets of a set of size at most 3 must contain two distinct comparable subsets.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
- Lemma 1 restricts subsets of X to the subtype X in order to apply IsAntichain.sperner, which is stated in Mathlib for antichains over a Fintype.
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.
lemma five_diamond_ramsey_property_four_mul_le_antichain_card_le_three {α : Type*} [DecidableEq α] {X : Finset α} (hX : X.card ≤ 3) (𝒜 : Finset (Finset α)) (hsub : ∀ S ∈ 𝒜, S ⊆ X) (hanti : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α))) : 𝒜.card ≤ 3 := by let p := fun a => a ∈ X have hinj : Set.InjOn (Finset.subtype p) 𝒜 := by intro S hS T hT hST have h1 := Finset.subtype_map_of_mem (fun x hx => hsub S hS hx) have h2 := Finset.subtype_map_of_mem (fun x hx => hsub T hT hx) rw [← h1, ← h2, hST] have hcard : 𝒜.card = (𝒜.image (Finset.subtype p)).card := (Finset.card_image_of_injOn hinj).symm have hantiB : IsAntichain (· ⊆ ·) ((𝒜.image (Finset.subtype p) : Finset (Finset (Subtype p))) : Set (Finset (Subtype p))) := by intro A hA B hB hne rw [Finset.mem_coe, Finset.mem_image] at hA hB obtain ⟨S, hS, rfl⟩ := hA obtain ⟨T, hT, rfl⟩ := hB intro hle have hST_ne : S ≠ T := by rintro rfl; exact hne rfl have hST_le : S ⊆ T := by intro x hx have hx_sub : (⟨x, hsub S hS hx⟩ : Subtype p) ∈ Finset.subtype p S := by rw [Finset.mem_subtype]; exact hx have := hle hx_sub rw [Finset.mem_subtype] at this exact this exact hanti (Finset.mem_coe.mpr hS) (Finset.mem_coe.mpr hT) hST_ne hST_le have hsperner := IsAntichain.sperner hantiB have hFcard : Fintype.card (Subtype p) = X.card := Fintype.card_coe X rw [hFcard] at hsperner have h3 : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> decide omegalemma five_diamond_ramsey_property_four_mul_le_five_subsets {α : Type*} [DecidableEq α] (X : Finset α) (hX : X.card ≤ 3) (M : Fin 5 → Finset α) (hM : ∀ i : Fin 5, M i ⊆ X) : ∃ i i', i ≠ i' ∧ (M i ⊆ M i' ∨ M i' ⊆ M i) := by by_contra! h have hinj : Function.Injective M := by intro i j hij by_contra hne exact (h i j hne).1 (hij ▸ subset_rfl) let 𝒜 := Finset.image M Finset.univ have hcard : 𝒜.card = 5 := by rw [Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin] have hsub : ∀ S ∈ 𝒜, S ⊆ X := by intro S hS rw [Finset.mem_image] at hS obtain ⟨i, -, rfl⟩ := hS exact hM i have hanti : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α)) := by intro A hA B hB hne hle rw [Finset.mem_coe, Finset.mem_image] at hA hB obtain ⟨i, -, rfl⟩ := hA obtain ⟨j, -, rfl⟩ := hB have hij : i ≠ j := by rintro rfl; exact hne rfl exact (h i j hij).1 hle have := five_diamond_ramsey_property_four_mul_le_antichain_card_le_three hX 𝒜 hsub hanti omega/-- Any d for which the k-colour 5-diamond Ramsey property holds is at least 4*k, by the colouring that only looks at |A| / 4, truncated at k - 1. -/theorem five_diamond_ramsey_property_four_mul_le (k d : ℕ) (hk : 1 ≤ k) (hd : poset_ramsey_property (DiamondPoset 5) k d) : 4 * k ≤ d := by classical by_contra! h have hd_le : d ≤ 4 * k - 1 := by omega have hprop := (five_diamond_ramsey_property_iff_sets 5 k d).mp hd (five_diamond_level_coloring k d hk) obtain ⟨col, B, T, M, hcB, hcT, hcM, hBT, hBMT, hincomp⟩ := hprop have hcol_eq : five_diamond_level_coloring k d hk B = five_diamond_level_coloring k d hk T := by rw [hcB, hcT] have hcard : (T \ B).card ≤ 3 := five_diamond_level_coloring_interval_card_le_three k d hk hd_le B T hBT hcol_eq have hDi_sub : ∀ i : Fin 5, M i \ B ⊆ T \ B := by intro i exact Finset.sdiff_subset_sdiff (hBMT i).2.1 (le_refl B) have hDinc : ∀ i i' : Fin 5, i ≠ i' → ¬ (M i \ B ⊆ M i' \ B) := by intro i i' hne hsub apply hincomp i i' hne have hBi : B ⊆ M i := (hBMT i).1.le have hBi' : B ⊆ M i' := (hBMT i').1.le calc M i = M i \ B ∪ B := (Finset.sdiff_union_of_subset hBi).symm _ ⊆ M i' \ B ∪ B := Finset.union_subset_union hsub (le_refl B) _ = M i' := Finset.sdiff_union_of_subset hBi' obtain ⟨i, i', hne, hcomp⟩ := five_diamond_ramsey_property_four_mul_le_five_subsets (T \ B) hcard (fun i => M i \ B) hDi_sub rcases hcomp with hc | hc · exact hDinc i i' hne hc · exact hDinc i' i (Ne.symm hne) hc