AFTD Auto-Formalizing Theoretical Domains

mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour

theoremverified

Case b = 1 with every singleton of the unique fan colour: if d ≥ j*a + j and the statement holds at (a, 0) in dimension d-j, then χ has a monochromatic diamond in one of the a diamond colours or a monochromatic F_j in the single fan colour.

Statement

theorem mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour (j a d : ℕ) (hj : 2 ≤ j)
    (ha : 1 ≤ a) (hd : j * a + j ≤ d)
    (ih : mixed_ramsey_property j a 0 (d - j))
    (χ : Finset (Fin d) → Fin (a + 1)) (hx : ∀ x : Fin d, χ {x} = Fin.natAdd a 0) :
    (∃ col : Fin a, has_monochromatic_diamond_copy j d (Fin.castAdd 1 col) χ) ∨
      ∃ col : Fin 1, has_monochromatic_fan_copy j d (Fin.natAdd a col) χ
Source
step towards mixed_diamond_fan_ramsey_bound
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • mixed_ramsey_propertymixed_ramsey_property j a b d asserts that every colouring of the subsets of Fin d with a + b colours has a monochromatic induced copy of…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • has_monochromatic_diamond_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_diamond_copy j d col χ holds if there are sets bot ⊂ top of…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • has_monochromatic_fan_copyFor a colouring χ of the subsets of Fin d with k colours, has_monochromatic_fan_copy j d col χ holds if there is a set top of colour col…
Used by 1
  • mixed_diamond_fan_ramsey_boundFor j ≥ 2, a colouring of the subsets of Fin d with a + b colours contains a monochromatic induced j-diamond in one of the first a…

The proof, explained

The proof proceeds by case analysis on whether there exists a set S ⊆ Fin d of size at least j coloured with the unique fan colour a. If such a set S exists, its singletons—all coloured with the fan colour by assumption—form the middle elements of a monochromatic fan with top S. If no such set exists, every set of size at least j must receive one of the a diamond colours; by fixing a j-element subset Y and mapping B ↦ B ∪ Y, we obtain an inclusion-preserving embedding from subsets of Fin (d - j) into sets of size at least j in Fin d. Applying the induction hypothesis at (a, 0) in dimension d - j then produces a monochromatic diamond, which lifts under this embedding to dimension d.

  1. j ≤ d

    From 1 ≤ a (hypothesis ha) and j * a + j ≤ d (hypothesis hd), linear arithmetic implies j ≤ j * 1 + j ≤ j * a + j ≤ d.

    lines 8–10

      have hj_le_d : j ≤ d := by
        have : j * 1 + j ≤ j * a + j := by nlinarith
        omega
  2. If there exists a subset S ⊆ Fin d with |S| ≥ j coloured with the unique fan colour, then there exists a monochromatic fan copy of that colour.

    We split into cases on whether there exists a subset S of size at least j coloured with the fan colour a (represented as Fin.natAdd a 0). If such an S exists, we extract a subset T ⊆ S of cardinality exactly j using Finset.exists_subset_card_eq and construct a bijection e : Fin j ≃ T via Fintype.equivFinOfCardEq. We choose S as the top set and the singletons {e(i)} as the j middle sets. Each singleton has colour a by the theorem hypothesis hx. Since |{e(i)}| = 1 and 2 ≤ j ≤ |S|, each singleton is strictly contained in S. Finally, distinct singletons are mutually incomparable by injectivity of e.

    lines 11–38

    uses Finset.exists_subset_card_eq, Fintype.card_coe, Fintype.equivFinOfCardEq, Finset.ssubset_iff_subset_ne, Finset.singleton_subset_iff, congrArg, Finset.card_singleton, Finset.mem_singleton, Subtype.ext

      by_cases h_fan : ∃ S : Finset (Fin d), j ≤ S.card ∧ χ S = Fin.natAdd a 0
      · right
        rcases h_fan with ⟨S, hS_card, hS_col⟩
        use 0
        unfold has_monochromatic_fan_copy
        refine ⟨S, hS_col, ?_⟩
        obtain ⟨T, hTS, hTcard⟩ := Finset.exists_subset_card_eq hS_card
        have hT_equiv : Nonempty (Fin j ≃ T) := by
          have : Fintype.card T = j := by rw [Fintype.card_coe, hTcard]
          exact ⟨Fintype.equivFinOfCardEq this |>.symm⟩
        obtain ⟨e⟩ := hT_equiv
        let mid : Fin j → Finset (Fin d) := fun i => { (e i : Fin d) }
        refine ⟨mid, ?_, ?_⟩
        · intro i
          refine ⟨?_, hx (e i : Fin d)⟩
          rw [Finset.ssubset_iff_subset_ne]
          refine ⟨Finset.singleton_subset_iff.mpr (hTS (e i).2), ?_⟩
          intro heq
          have h1 : (mid i).card = S.card := congrArg Finset.card heq
          have h2 : (mid i).card = 1 := Finset.card_singleton _
          omega
        · intro i i' hne
          dsimp [mid]
          rw [Finset.singleton_subset_iff, Finset.mem_singleton]
          intro heq
          apply hne
          apply e.injective
          exact Subtype.ext heq
  3. In the remaining case, Fin d decomposes into a j-element subset Y and an embedding of Fin (d - j) disjoint from Y.

    Assuming no set of size at least j has the fan colour, we must produce a monochromatic diamond. Using j + (d - j) = d from Nat.add_sub_of_le, we identify Fin d with Fin (j + (d - j)) via Fin.castOrderIso. We define Y as the image of the first j coordinates via Fin.castAddEmb, and emb as the embedding of the remaining d - j coordinates via Fin.natAddEmb. Since elements of Y have value < j while elements in the range of emb have value ≥ j, the image of emb is disjoint from Y.

    lines 39–56

    uses Nat.add_sub_of_le, Fin.castOrderIso, Fin.castAddEmb, Fin.natAddEmb, Finset.mem_map, congrArg

      · left
        have hd' : j + (d - j) = d := Nat.add_sub_of_le hj_le_d
        let e_iso := (Fin.castOrderIso hd').toEquiv
        let Y_emb : Fin j ↪ Fin d := (Fin.castAddEmb (d - j)).trans e_iso.toEmbedding
        let emb : Fin (d - j) ↪ Fin d := (Fin.natAddEmb j).trans e_iso.toEmbedding
        let Y : Finset (Fin d) := Finset.univ.map Y_emb
        have h_disj : ∀ x, emb x ∉ Y := by
          intro x
          rw [Finset.mem_map]
          rintro ⟨y, hy, heq⟩
          change e_iso (Fin.castAddEmb (d - j) y) = e_iso (Fin.natAddEmb j x) at heq
          have heq' := e_iso.injective heq
          have h_val := congrArg Fin.val heq'
          have h1 : (Fin.castAddEmb (d - j) y).val = y.val := rfl
          have h2 : (Fin.natAddEmb j x).val = j + x.val := rfl
          rw [h1, h2] at h_val
          have : y.val < j := y.isLt
          omega
  4. The cylinder operation U(B) = emb(B) ∪ Y satisfies |U(B)| ≥ j for all B, and reflects and preserves set inclusion and strict inclusion: U(B) ⊆ U(B') ↔ B ⊆ B' and U(B) ⊂ U(B') ↔ B ⊂ B'.

    For any B ⊆ Fin (d - j), Y ⊆ U(B) and |Y| = j, so |U(B)| ≥ j by monotonicity of cardinality. For inclusion, if U(B) ⊆ U(B') and x ∈ B, then emb(x) ∈ U(B) ⊆ U(B'); since emb(x) ∉ Y, emb(x) must belong to emb(B'), which implies x ∈ B' by injectivity of emb. The reverse direction is immediate from union monotonicity. Strict inclusion equivalence U(B) ⊂ U(B') ↔ B ⊂ B' then follows directly from the definition of strict subset.

    lines 57–83

    uses Finset.subset_union_right, Finset.card_le_card, Finset.card_map, Finset.card_univ, Fintype.card_fin, Finset.mem_union, Finset.mem_map, Finset.union_subset_union_left, Finset.ssubset_def

        let U : Finset (Fin (d - j)) → Finset (Fin d) := fun B => B.map emb ∪ Y
        have hU_card : ∀ B, j ≤ (U B).card := by
          intro B
          have : Y ⊆ U B := Finset.subset_union_right
          have := Finset.card_le_card this
          have hY_card : Y.card = j := by
            rw [Finset.card_map, Finset.card_univ, Fintype.card_fin]
          omega
        have hU_sub : ∀ B B', U B ⊆ U B' ↔ B ⊆ B' := by
          intro B B'
          constructor
          · intro h x hx
            have h1 : emb x ∈ U B := by
              simp only [U, Finset.mem_union, Finset.mem_map]
              left; exact ⟨x, hx, rfl⟩
            have h2 := h h1
            simp only [U, Finset.mem_union, Finset.mem_map] at h2
            rcases h2 with ⟨y, hy, heqy⟩ | hy
            · have : y = x := emb.injective heqy
              rwa [← this]
            · exact (h_disj x hy).elim
          · intro h
            dsimp [U]
            exact Finset.union_subset_union_left (Finset.map_subset_map.mpr h)
        have hU_ssub : ∀ B B', U B ⊂ U B' ↔ B ⊂ B' := by
          intro B B'
          rw [Finset.ssubset_def, Finset.ssubset_def, hU_sub, hU_sub]
  5. For every B ⊆ Fin (d - j), χ(U(B)) is strictly less than a, yielding an induced colouring ψ : Finset (Fin (d - j)) → Fin a that uses only diamond colours.

    Because every set U(B) has cardinality at least j, it cannot receive the fan colour a under χ, as no set of size at least j has that colour in this case. Since χ takes values in Fin (a + 1), the numerical value of χ(U(B)) must be strictly less than a. We can therefore restrict the target to Fin a, defining ψ(B) = χ(U(B)).

    lines 84–97

    uses Fin.natAdd

        have h_val_lt : ∀ B, (χ (U B)).val < a := by
          intro B
          have h_ne : χ (U B) ≠ Fin.natAdd a 0 := fun h => h_fan ⟨U B, hU_card B, h⟩
          have h1 : (Fin.natAdd a (0 : Fin 1)).val = a := rfl
          have h2 : (χ (U B)).val < a + 1 := (χ (U B)).isLt
          have h3 : (χ (U B)).val ≠ a := by
            intro h
            apply h_ne
            ext
            rw [h, h1]
          omega
        let ψ : Finset (Fin (d - j)) → Fin (a + 0) := fun B => ⟨(χ (U B)).val, by
          have := h_val_lt B
          omega⟩
  6. The induction hypothesis applied to ψ yields a monochromatic diamond in dimension d - j, which lifts under U to a monochromatic diamond for χ in dimension d.

    We apply the induction hypothesis ih to the colouring ψ on subsets of Fin (d - j). Since the parameter b is 0, there are no fan colours, so the fan alternative is impossible. Hence ψ admits a monochromatic diamond of some diamond colour col < a, given by a bottom set bot, a top set top, and j pairwise incomparable middle sets mid(i). Mapping this configuration to dimension d via U preserves the strict inclusions and incomparability, and every set retains colour col under χ. This gives the required monochromatic diamond for χ.

    lines 98–132

    uses Fin.castAdd, congrArg

        rcases ih ψ with ⟨col, hcol⟩ | ⟨col, _⟩
        · use col
          unfold has_monochromatic_diamond_copy at hcol ⊢
          rcases hcol with ⟨bot, top, h_bot_top, h_col_bot, h_col_top, mid, h_mid, h_incomp⟩
          refine ⟨U bot, U top, ?_, ?_, ?_, fun i => U (mid i), ?_, ?_⟩
          · rwa [hU_ssub]
          · ext
            have : (Fin.castAdd 0 col).val = col.val := rfl
            have : (Fin.castAdd 1 col).val = col.val := rfl
            have h_psi := congrArg Fin.val h_col_bot
            dsimp [ψ] at h_psi
            omega
          · ext
            have : (Fin.castAdd 0 col).val = col.val := rfl
            have : (Fin.castAdd 1 col).val = col.val := rfl
            have h_psi := congrArg Fin.val h_col_top
            dsimp [ψ] at h_psi
            omega
          · intro i
            refine ⟨?_, ?_, ?_⟩
            · rw [hU_ssub]
              exact (h_mid i).1
            · rw [hU_ssub]
              exact (h_mid i).2.1
            · dsimp only
              ext
              have : (Fin.castAdd 0 col).val = col.val := rfl
              have : (Fin.castAdd 1 col).val = col.val := rfl
              have h_psi := congrArg Fin.val (h_mid i).2.2
              dsimp [ψ] at h_psi
              omega
          · intro i i' hne
            rw [hU_sub]
            exact h_incomp i i' hne
        · exact col.elim0
Finset.exists_subset_card_eq
Any finite set with at least n elements contains a subset of cardinality exactly n.
Fintype.card_coe
The cardinality of the subtype corresponding to a finset equals the cardinality of the finset itself.
Fintype.equivFinOfCardEq
Any finite type whose cardinality is n is equivalent to Fin n.
Finset.ssubset_iff_subset_ne
A finset s is a strict subset of t if and only if s ⊆ t and s ≠ t.
Finset.singleton_subset_iff
The singleton set {a} is a subset of s if and only if a ∈ s.
congrArg
Applying a function to equal arguments produces equal values: if a₁ = a₂ then f a₁ = f a₂.
Finset.card_singleton
The cardinality of any singleton finset {a} is 1.
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Nat.add_sub_of_le
For natural numbers with a ≤ b, a + (b - a) = b.
Fin.castOrderIso
An equality of natural numbers n = m induces an order isomorphism between Fin n and Fin m.
Fin.castAddEmb
The canonical embedding of Fin n into Fin (n + m) that preserves the underlying natural number value.
Fin.natAddEmb
The embedding of Fin m into Fin (n + m) that shifts each index by n.
Finset.mem_map
An element b belongs to the mapped finset Finset.map f s if and only if b = f a for some a ∈ s.
Finset.subset_union_right
A set s₂ is a subset of the union s₁ ∪ s₂.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.card_map
An embedding preserves the cardinality of a finset: |Finset.map f s| = |s|.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
Finset.mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
Finset.union_subset_union_left
If s₁ ⊆ s₂, then s₁ ∪ t ⊆ s₂ ∪ t.
Finset.ssubset_def
A set s is a strict subset of t if and only if s ⊆ t and ¬ t ⊆ s.
Fin.natAdd
The canonical embedding of Fin m into Fin (n + m) mapping i to n + i.
Fin.castAdd
The canonical embedding of Fin n into Fin (n + m) preserving index values.

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

/-- b = 1 step with the unique fan colour on every singleton: either a large fan-coloured set is already a fan, or every fan-coloured set has size < j and compressing onto a j-subset Y makes the colouring fan-free, so the (a, 0) instance at dimension d-j gives the diamond. -/theorem mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour (j a d : ℕ) (hj : 2 ≤ j)    (ha : 1 ≤ a) (hd : j * a + j ≤ d)    (ih : mixed_ramsey_property j a 0 (d - j))    (χ : Finset (Fin d) → Fin (a + 1)) (hx : ∀ x : Fin d, χ {x} = Fin.natAdd a 0) :    (∃ col : Fin a, has_monochromatic_diamond_copy j d (Fin.castAdd 1 col) χ) ∨      ∃ col : Fin 1, has_monochromatic_fan_copy j d (Fin.natAdd a col) χ := by  have hj_le_d : j ≤ d := by    have : j * 1 + j ≤ j * a + j := by nlinarith    omega  by_cases h_fan : ∃ S : Finset (Fin d), j ≤ S.card ∧ χ S = Fin.natAdd a 0  · right    rcases h_fan with ⟨S, hS_card, hS_col⟩    use 0    unfold has_monochromatic_fan_copy    refine ⟨S, hS_col, ?_⟩    obtain ⟨T, hTS, hTcard⟩ := Finset.exists_subset_card_eq hS_card    have hT_equiv : Nonempty (Fin j ≃ T) := by      have : Fintype.card T = j := by rw [Fintype.card_coe, hTcard]      exact ⟨Fintype.equivFinOfCardEq this |>.symm⟩    obtain ⟨e⟩ := hT_equiv    let mid : Fin j → Finset (Fin d) := fun i => { (e i : Fin d) }    refine ⟨mid, ?_, ?_⟩    · intro i      refine ⟨?_, hx (e i : Fin d)⟩      rw [Finset.ssubset_iff_subset_ne]      refine ⟨Finset.singleton_subset_iff.mpr (hTS (e i).2), ?_⟩      intro heq      have h1 : (mid i).card = S.card := congrArg Finset.card heq      have h2 : (mid i).card = 1 := Finset.card_singleton _      omega    · intro i i' hne      dsimp [mid]      rw [Finset.singleton_subset_iff, Finset.mem_singleton]      intro heq      apply hne      apply e.injective      exact Subtype.ext heq  · left    have hd' : j + (d - j) = d := Nat.add_sub_of_le hj_le_d    let e_iso := (Fin.castOrderIso hd').toEquiv    let Y_emb : Fin j ↪ Fin d := (Fin.castAddEmb (d - j)).trans e_iso.toEmbedding    let emb : Fin (d - j) ↪ Fin d := (Fin.natAddEmb j).trans e_iso.toEmbedding    let Y : Finset (Fin d) := Finset.univ.map Y_emb    have h_disj : ∀ x, emb x ∉ Y := by      intro x      rw [Finset.mem_map]      rintro ⟨y, hy, heq⟩      change e_iso (Fin.castAddEmb (d - j) y) = e_iso (Fin.natAddEmb j x) at heq      have heq' := e_iso.injective heq      have h_val := congrArg Fin.val heq'      have h1 : (Fin.castAddEmb (d - j) y).val = y.val := rfl      have h2 : (Fin.natAddEmb j x).val = j + x.val := rfl      rw [h1, h2] at h_val      have : y.val < j := y.isLt      omega    let U : Finset (Fin (d - j)) → Finset (Fin d) := fun B => B.map emb ∪ Y    have hU_card : ∀ B, j ≤ (U B).card := by      intro B      have : Y ⊆ U B := Finset.subset_union_right      have := Finset.card_le_card this      have hY_card : Y.card = j := by        rw [Finset.card_map, Finset.card_univ, Fintype.card_fin]      omega    have hU_sub : ∀ B B', U B ⊆ U B' ↔ B ⊆ B' := by      intro B B'      constructor      · intro h x hx        have h1 : emb x ∈ U B := by          simp only [U, Finset.mem_union, Finset.mem_map]          left; exact ⟨x, hx, rfl⟩        have h2 := h h1        simp only [U, Finset.mem_union, Finset.mem_map] at h2        rcases h2 with ⟨y, hy, heqy⟩ | hy        · have : y = x := emb.injective heqy          rwa [← this]        · exact (h_disj x hy).elim      · intro h        dsimp [U]        exact Finset.union_subset_union_left (Finset.map_subset_map.mpr h)    have hU_ssub : ∀ B B', U B ⊂ U B' ↔ B ⊂ B' := by      intro B B'      rw [Finset.ssubset_def, Finset.ssubset_def, hU_sub, hU_sub]    have h_val_lt : ∀ B, (χ (U B)).val < a := by      intro B      have h_ne : χ (U B) ≠ Fin.natAdd a 0 := fun h => h_fan ⟨U B, hU_card B, h⟩      have h1 : (Fin.natAdd a (0 : Fin 1)).val = a := rfl      have h2 : (χ (U B)).val < a + 1 := (χ (U B)).isLt      have h3 : (χ (U B)).val ≠ a := by        intro h        apply h_ne        ext        rw [h, h1]      omega    let ψ : Finset (Fin (d - j)) → Fin (a + 0) := fun B => ⟨(χ (U B)).val, by      have := h_val_lt B      omega⟩    rcases ih ψ with ⟨col, hcol⟩ | ⟨col, _⟩    · use col      unfold has_monochromatic_diamond_copy at hcol ⊢      rcases hcol with ⟨bot, top, h_bot_top, h_col_bot, h_col_top, mid, h_mid, h_incomp⟩      refine ⟨U bot, U top, ?_, ?_, ?_, fun i => U (mid i), ?_, ?_⟩      · rwa [hU_ssub]      · ext        have : (Fin.castAdd 0 col).val = col.val := rfl        have : (Fin.castAdd 1 col).val = col.val := rfl        have h_psi := congrArg Fin.val h_col_bot        dsimp [ψ] at h_psi        omega      · ext        have : (Fin.castAdd 0 col).val = col.val := rfl        have : (Fin.castAdd 1 col).val = col.val := rfl        have h_psi := congrArg Fin.val h_col_top        dsimp [ψ] at h_psi        omega      · intro i        refine ⟨?_, ?_, ?_⟩        · rw [hU_ssub]          exact (h_mid i).1        · rw [hU_ssub]          exact (h_mid i).2.1        · dsimp only          ext          have : (Fin.castAdd 0 col).val = col.val := rfl          have : (Fin.castAdd 1 col).val = col.val := rfl          have h_psi := congrArg Fin.val (h_mid i).2.2          dsimp [ψ] at h_psi          omega      · intro i i' hne        rw [hU_sub]        exact h_incomp i i' hne    · exact col.elim0
See it in the graphDiscuss this resultChallenge it