AFTD Auto-Formalizing Theoretical Domains

five_diamond_ramsey_property_four_mul_le

theoremverified

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

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.

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

    lines 6–13

    uses Finset.subtype_map_of_mem, Finset.card_image_of_injOn

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

    lines 14–28

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

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

    lines 29–34

    uses IsAntichain.sperner, Fintype.card_coe

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

    lines 40–47

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

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

    lines 48–61

    uses Finset.mem_image, Finset.mem_coe, five_diamond_ramsey_property_four_mul_le_antichain_card_le_three

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

    lines 66–70

    uses five_diamond_ramsey_property_iff_sets, five_diamond_level_coloring

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

    lines 71–76

    uses five_diamond_level_coloring, five_diamond_level_coloring_interval_card_le_three

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

    lines 77–87

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

    lines 88–93

    uses five_diamond_ramsey_property_four_mul_le_five_subsets, Ne.symm

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

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