five_diamond_ramsey_property_four_mul_minus_one
For 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.
Statement
theorem five_diamond_ramsey_property_four_mul_minus_one (k : ℕ) (hk : 1 ≤ k) :
¬ poset_ramsey_property (DiamondPoset 5) k (4 * k - 1)- Source
- step towards op_270_five_diamond_poset_ramsey_number
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_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.
- 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_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,…
- 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…
The proof, explained
The proof shows that the level colouring A ↦ min(k - 1, ⌊|A|/4⌋) on the Boolean lattice of dimension 4k - 1 contains no monochromatic copy of the 5-diamond poset D₅. If such a copy existed with bottom B, top T, and five middle elements M(i), the fact that B and T share the same colour forces |T \ B| ≤ 3. However, the differences M(i) \ B would form five pairwise incomparable subsets of T \ B, which contradicts Sperner's theorem since an antichain in a set of size at most 3 can have size at most 3.
The restriction map from 𝒜 to subsets of the subtype X is injective, so the image family has the same size as 𝒜.
Let p be the predicate membership in X. Since every set S in 𝒜 satisfies S ⊆ X, mapping the subtype restriction back to the ambient type via `Finset.subtype_map_of_mem` reconstructs S. Therefore, two sets whose subtype restrictions agree must be identical, making the restriction map injective on 𝒜, and `Finset.card_image_of_injOn` equates the image cardinality with the cardinality of 𝒜.
uses
Finset.subtype_map_of_mem,Finset.card_image_of_injOnclassical let p : α → Prop := fun a => a ∈ X have hinj : Set.InjOn (fun S : Finset α => S.subtype p) (𝒜 : Set (Finset α)) := by intro S hS T hT hST have hSX : ∀ x ∈ S, p x := fun x hx => hsub S hS hx have hTX : ∀ x ∈ T, p x := fun x hx => hsub T hT hx have h1 : Finset.map (Function.Embedding.subtype p) (S.subtype p) = S := Finset.subtype_map_of_mem hSX have h2 : Finset.map (Function.Embedding.subtype p) (T.subtype p) = T := Finset.subtype_map_of_mem hTX have hST' : S.subtype p = T.subtype p := hST rw [← h1, ← h2, hST'] have hcard : (𝒜.image (fun S => S.subtype p)).card = 𝒜.card := Finset.card_image_of_injOn hinj
The image family of subtype restrictions forms an antichain in the Boolean lattice of the subtype.
Given two distinct elements of the image, they are the subtype restrictions of distinct sets S, T in 𝒜. If one subtype restriction were contained in the other, every element of S would also belong to T (by `Finset.mem_subtype`), implying S ⊆ T, which contradicts the hypothesis that 𝒜 is an antichain.
uses
Finset.mem_coe,Finset.mem_image,Finset.mem_subtypehave hantiB : IsAntichain (· ⊆ ·) ((𝒜.image (fun S => S.subtype p)) : Set (Finset (Subtype p))) := by intro a ha b hb hab rw [Finset.mem_coe, Finset.mem_image] at ha hb obtain ⟨S, hS, rfl⟩ := ha obtain ⟨T, hT, rfl⟩ := hb have hne : S ≠ T := by intro h; exact hab (by rw [h]) have hsub_of : (S.subtype p) ⊆ (T.subtype p) → S ⊆ T := by intro h x hx have hxX : p x := hsub S hS hx have h1 : (⟨x, hxX⟩ : Subtype p) ∈ S.subtype p := by rw [Finset.mem_subtype]; exact hx have h2 : (⟨x, hxX⟩ : Subtype p) ∈ T.subtype p := h h1 rwa [Finset.mem_subtype] at h2 exact fun hST => hanti hS hT hne (hsub_of hST)
By Sperner's theorem, |𝒜| ≤ 3. automation
Sperner's theorem (`hantiB.sperner`) bounds the size of any antichain in the Boolean lattice of a ground set of size |X| by the middle binomial coefficient `Nat.choose (|X|) (|X| / 2)`. Because |X| ≤ 3, exhaustive case analysis on |X| ∈ {0, 1, 2, 3} via `interval_cases` and `simp` evaluates each binomial coefficient to at most 3. Then `omega` combines the Sperner bound with the image cardinality to conclude |𝒜| ≤ 3.
have hsp := hantiB.sperner have hfx : Fintype.card (Subtype p) = X.card := by simp [p] rw [hfx] at hsp have hle : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> simp omega
Assuming no two sets in M are comparable, M is injective and its image has cardinality 5.
We argue by contradiction and suppose no two distinct sets M(i) and M(j) satisfy M(i) ⊆ M(j). If M(i) = M(j) for i ≠ j, then M(i) ⊆ M(j), a contradiction, so M is injective. Since M is injective on `Fin 5`, its image 𝒜 has cardinality 5 by `Finset.card_image_of_injective`, `Finset.card_univ`, and `Fintype.card_fin`.
uses
Finset.card_image_of_injective,Finset.card_univ,Fintype.card_finclassical by_contra h push Not at h have hinj : Function.Injective M := by intro i j hij by_contra hne exact (h i j hne).1 (by rw [hij]) set 𝒜 : Finset (Finset α) := Finset.univ.image M with h𝒜 have hcard : 𝒜.card = 5 := by rw [h𝒜, Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin]
The image 𝒜 is an antichain of subsets of X, contradicting the bound |𝒜| ≤ 3. automation
Each element of 𝒜 is some M(i) ⊆ X, so every set in 𝒜 is a subset of X. Distinct sets in 𝒜 arise from distinct indices i ≠ j, so neither is contained in the other, meaning 𝒜 is an antichain. Applying `five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_three` forces |𝒜| ≤ 3, and `omega` derives a contradiction with |𝒜| = 5.
uses
Finset.mem_image,Finset.mem_coe,five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_threehave hsub : ∀ S ∈ 𝒜, S ⊆ X := by intro S hS rw [h𝒜, Finset.mem_image] at hS obtain ⟨i, -, rfl⟩ := hS exact hM i have hanti : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α)) := by intro a ha b hb hab rw [Finset.mem_coe, h𝒜, Finset.mem_image] at ha hb obtain ⟨i, -, rfl⟩ := ha obtain ⟨j, -, rfl⟩ := hb have hne : i ≠ j := by intro e; exact hab (by rw [e]) exact (h i j hne).1 have := five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_three hX 𝒜 hsub hanti omega
Assuming the Ramsey property, the level colouring yields a monochromatic 5-diamond whose top T and bottom B satisfy |T \ B| ≤ 3.
Assuming the poset Ramsey property for the 5-diamond at dimension 4k - 1, `five_diamond_ramsey_property_iff_sets` produces a monochromatic copy under the level colouring: a bottom set B, top set T, and five middle sets M(i). Because B and T share the same colour, lemma `five_diamond_level_coloring_interval_card_le_three` establishes that |T \ B| ≤ 3.
uses
five_diamond_ramsey_property_iff_sets,five_diamond_level_coloring_interval_card_le_three,le_reflclassical intro h rw [five_diamond_ramsey_property_iff_sets] at h obtain ⟨col, B, T, M, hcB, hcT, hcM, hBT, hBMT, hincomp⟩ := h (five_diamond_level_coloring k (4 * k - 1) hk) have hcol_eq : five_diamond_level_coloring k (4 * k - 1) hk B = five_diamond_level_coloring k (4 * k - 1) hk T := by rw [hcB, hcT] have hcard : (T \ B).card ≤ 3 := five_diamond_level_coloring_interval_card_le_three k (4 * k - 1) hk (le_refl _) B T hBT hcol_eq
The differences M(i) \ B are subsets of T \ B and are pairwise incomparable.
Since each M(i) is a subset of T, taking set difference with B gives M(i) \ B ⊆ T \ B via `Finset.sdiff_subset_sdiff`. If M(i) \ B ⊆ M(i') \ B for i ≠ i', taking the union with B on both sides would imply M(i) ⊆ M(i') using `Finset.sdiff_union_of_subset` and `Finset.union_subset_union`, which contradicts the incomparability of the diamond's middle elements.
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'
Applying the five-subsets lemma to {M(i) \ B} yields a pair of comparable sets, giving a contradiction in either order.
Applying `five_diamond_ramsey_property_four_mul_minus_one_five_subsets` to the ground set T \ B of size at most 3 and the five subsets M(i) \ B produces distinct indices i, i' with M(i) \ B ⊆ M(i') \ B or M(i') \ B ⊆ M(i) \ B. Either inclusion contradicts the incomparability proved in the previous step, using `Ne.symm` to swap the indices in the second case.
uses
five_diamond_ramsey_property_four_mul_minus_one_five_subsets,Ne.symmobtain ⟨i, i', hne, hcomp⟩ := five_diamond_ramsey_property_four_mul_minus_one_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- For a finite set s whose elements all satisfy p, mapping its subtype restriction back to the ambient type via the subtype embedding recovers s.
Finset.card_image_of_injOn- If a function is injective on a finite set s, its image has the same cardinality as s.
Finset.mem_coe- Coercing a finite set to a set preserves element membership.
Finset.mem_image- An element belongs to an image finset if and only if it is the image of some element in the domain.
Finset.mem_subtype- An element of a subtype belongs to the subtype restriction of a finset s if and only if its underlying value belongs to s.
Finset.card_image_of_injective- An injective function maps a finite set to an image of the same cardinality.
Finset.card_univ- The cardinality of the universal finset `Finset.univ` of a finite type equals the cardinality of the type.
Fintype.card_fin- The standard finite type `Fin n` has cardinality n.
five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_three- Any antichain of subsets of a set of size at most 3 contains at most 3 subsets.
five_diamond_ramsey_property_iff_sets- The poset Ramsey property for the j-diamond poset is equivalent to every k-colouring admitting bottom and top sets B ⊂ T and j pairwise incomparable middle sets between them, all sharing one colour.
five_diamond_level_coloring_interval_card_le_three- In the level colouring with k colours on dimension at most 4k - 1, any two comparable sets B ⊂ T with the same colour satisfy |T \ B| ≤ 3.
le_refl- The preorder relation ≤ (here subset inclusion ⊆) is reflexive.
Finset.sdiff_subset_sdiff- If s ⊆ t and v ⊆ u, then the set difference s \ u is a subset of t \ v.
Finset.sdiff_union_of_subset- If s₁ ⊆ s₂, then (s₂ \ s₁) ∪ s₁ = s₂.
Finset.union_subset_union- If s ⊆ u and t ⊆ v, then s ∪ t ⊆ u ∪ v.
five_diamond_ramsey_property_four_mul_minus_one_five_subsets- Any family of 5 subsets of a set of size at most 3 must contain at least two comparable subsets.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
- In the first lemma, the bound on the central binomial coefficient for $|X| \le 3$ is verified by finite case analysis via `interval_cases` over the four possibilities $0, 1, 2, 3$.
- Sperner's theorem (`IsAntichain.sperner`) in Mathlib is stated for subsets of a finite type, so subsets of $X$ are formally transported to the subtype `{x // x ∈ X}` before invoking it.
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_minus_one_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 classical let p : α → Prop := fun a => a ∈ X have hinj : Set.InjOn (fun S : Finset α => S.subtype p) (𝒜 : Set (Finset α)) := by intro S hS T hT hST have hSX : ∀ x ∈ S, p x := fun x hx => hsub S hS hx have hTX : ∀ x ∈ T, p x := fun x hx => hsub T hT hx have h1 : Finset.map (Function.Embedding.subtype p) (S.subtype p) = S := Finset.subtype_map_of_mem hSX have h2 : Finset.map (Function.Embedding.subtype p) (T.subtype p) = T := Finset.subtype_map_of_mem hTX have hST' : S.subtype p = T.subtype p := hST rw [← h1, ← h2, hST'] have hcard : (𝒜.image (fun S => S.subtype p)).card = 𝒜.card := Finset.card_image_of_injOn hinj have hantiB : IsAntichain (· ⊆ ·) ((𝒜.image (fun S => S.subtype p)) : Set (Finset (Subtype p))) := by intro a ha b hb hab rw [Finset.mem_coe, Finset.mem_image] at ha hb obtain ⟨S, hS, rfl⟩ := ha obtain ⟨T, hT, rfl⟩ := hb have hne : S ≠ T := by intro h; exact hab (by rw [h]) have hsub_of : (S.subtype p) ⊆ (T.subtype p) → S ⊆ T := by intro h x hx have hxX : p x := hsub S hS hx have h1 : (⟨x, hxX⟩ : Subtype p) ∈ S.subtype p := by rw [Finset.mem_subtype]; exact hx have h2 : (⟨x, hxX⟩ : Subtype p) ∈ T.subtype p := h h1 rwa [Finset.mem_subtype] at h2 exact fun hST => hanti hS hT hne (hsub_of hST) have hsp := hantiB.sperner have hfx : Fintype.card (Subtype p) = X.card := by simp [p] rw [hfx] at hsp have hle : X.card.choose (X.card / 2) ≤ 3 := by interval_cases X.card <;> simp omegalemma five_diamond_ramsey_property_four_mul_minus_one_five_subsets {α : Type*} [DecidableEq α] (X : Finset α) (hX : X.card ≤ 3) (M : Fin 5 → Finset α) (hM : ∀ i, M i ⊆ X) : ∃ i i', i ≠ i' ∧ (M i ⊆ M i' ∨ M i' ⊆ M i) := by classical by_contra h push Not at h have hinj : Function.Injective M := by intro i j hij by_contra hne exact (h i j hne).1 (by rw [hij]) set 𝒜 : Finset (Finset α) := Finset.univ.image M with h𝒜 have hcard : 𝒜.card = 5 := by rw [h𝒜, Finset.card_image_of_injective _ hinj, Finset.card_univ, Fintype.card_fin] have hsub : ∀ S ∈ 𝒜, S ⊆ X := by intro S hS rw [h𝒜, Finset.mem_image] at hS obtain ⟨i, -, rfl⟩ := hS exact hM i have hanti : IsAntichain (· ⊆ ·) (𝒜 : Set (Finset α)) := by intro a ha b hb hab rw [Finset.mem_coe, h𝒜, Finset.mem_image] at ha hb obtain ⟨i, -, rfl⟩ := ha obtain ⟨j, -, rfl⟩ := hb have hne : i ≠ j := by intro e; exact hab (by rw [e]) exact (h i j hne).1 have := five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_three hX 𝒜 hsub hanti omega/-- The lower-bound half of R_k(D_5) = 4k: at dimension 4k-1 the level colouring A ↦ min (k-1) (|A|/4) has no monochromatic induced 5-diamond. -/theorem five_diamond_ramsey_property_four_mul_minus_one (k : ℕ) (hk : 1 ≤ k) : ¬ poset_ramsey_property (DiamondPoset 5) k (4 * k - 1) := by classical intro h rw [five_diamond_ramsey_property_iff_sets] at h obtain ⟨col, B, T, M, hcB, hcT, hcM, hBT, hBMT, hincomp⟩ := h (five_diamond_level_coloring k (4 * k - 1) hk) have hcol_eq : five_diamond_level_coloring k (4 * k - 1) hk B = five_diamond_level_coloring k (4 * k - 1) hk T := by rw [hcB, hcT] have hcard : (T \ B).card ≤ 3 := five_diamond_level_coloring_interval_card_le_three k (4 * k - 1) hk (le_refl _) 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_minus_one_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