AFTD Auto-Formalizing Theoretical Domains

five_diamond_ramsey_property_four_mul_minus_one

theoremverified

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.

  1. 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 𝒜.

    lines 5–18

    uses Finset.subtype_map_of_mem, Finset.card_image_of_injOn

      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
  2. 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.

    lines 19–32

    uses Finset.mem_coe, Finset.mem_image, Finset.mem_subtype

      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)
  3. 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.

    lines 33–38

      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
  4. 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`.

    lines 44–53

    uses Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

      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]
  5. 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.

    lines 54–67

    uses Finset.mem_image, Finset.mem_coe, five_diamond_ramsey_property_four_mul_minus_one_antichain_card_le_three

      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
  6. 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.

    lines 72–82

    uses five_diamond_ramsey_property_iff_sets, five_diamond_level_coloring_interval_card_le_three, le_refl

      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
  7. 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.

    lines 83–93

    uses Finset.sdiff_subset_sdiff, le_refl, Finset.sdiff_union_of_subset, Finset.union_subset_union

      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'
  8. 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.

    lines 94–99

    uses five_diamond_ramsey_property_four_mul_minus_one_five_subsets, Ne.symm

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it