AFTD Auto-Formalizing Theoretical Domains

mixed_diamond_fan_ramsey_bound_last_colour_step

theoremverified

Case b = 0, a ≥ 1: if d ≥ j*a and the statement holds at (a-1, 1) in the same dimension, then every colouring with a colours has a monochromatic induced j-diamond in one of them.

Statement

theorem mixed_diamond_fan_ramsey_bound_last_colour_step (j a d : ℕ) (hj : 2 ≤ j) (ha : 1 ≤ a)
    (hd : j * a ≤ d) (ih : mixed_ramsey_property j (a - 1) 1 d) : mixed_ramsey_property j a 0 d
Source
step towards mixed_diamond_fan_ramsey_bound
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • has_monochromatic_diamond_copy_colour_injectiveRelabelling colours by an injective map does not change the existence of a monochromatic induced j-diamond: if ψ = f ∘ χ with f injective,…
  • has_monochromatic_fan_copy_colour_injectiveRelabelling colours by an injective map does not change the existence of a monochromatic induced F_j: if ψ = f ∘ χ with f injective, then…
  • 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…
  • 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…
  • 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…
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

To establish the base case b = 0 with a ≥ 1 colours, we evaluate the colouring on the empty set, c₀ = χ(∅). We construct a bijection on colours that maps c₀ to the designated single fan colour and the remaining a - 1 colours to diamond colours, then apply the (a-1, 1) induction hypothesis to the recoloured hypercube. If this yields a diamond in one of the first a - 1 colours, it pulls back directly to a monochromatic diamond for χ. If it yields a fan in colour c₀, adjoining ∅ as the bottom element turns the fan into a monochromatic diamond in colour c₀, because incomparability of the fan branches guarantees no branch is empty.

  1. Unpack the monochromatic fan into its apex and branches.

    From the assumption that χ contains a monochromatic j-fan in colour c, we obtain its apex top with χ(top) = c and j branches mid(i) such that each branch is strictly contained in top, has colour c, and no branch is a subset of another. Since j ≥ 2, the index type Fin j is non-empty.

    lines 6–7

      have : NeZero j := ⟨by omega⟩
      obtain ⟨top, htop, mid, hmid, hpair⟩ := hfan
  2. Every branch of the fan is non-empty.

    Suppose for contradiction that some branch mid(i) is empty. Since j ≥ 2, there exists a distinct index i' ≠ i (either 1 if i = 0, or 0 if i ≠ 0). But the empty set is a subset of every set, so mid(i) = ∅ ⊆ mid(i'), contradicting the requirement that fan branches are pairwise incomparable.

    lines 8–19

    uses eq_or_ne, congrArg, Fin.val, Ne.symm, Finset.empty_subset

      have key : ∀ i : Fin j, mid i ≠ ∅ := by
        intro i hi
        have hne : ∃ i' : Fin j, i' ≠ i := by
          rcases eq_or_ne i 0 with h | h
          · refine ⟨⟨1, by omega⟩, ?_⟩
            rw [h]
            intro hh
            have hv := congrArg Fin.val hh
            simp at hv
          · exact ⟨0, fun hh => h hh.symm⟩
        obtain ⟨i', hi'⟩ := hne
        exact hpair i i' (Ne.symm hi') (by rw [hi]; exact Finset.empty_subset _)
  3. The fan together with the empty set as the bottom element forms a monochromatic diamond.

    We construct a monochromatic diamond copy using ∅ as the bottom element, top as the apex, and mid as the branches. By hypothesis, χ(∅) = c. Because each branch is non-empty, ∅ ⊂ mid(i). By transitivity through branch 0, ∅ ⊂ mid(0) ⊂ top, so ∅ ⊂ top. Each branch mid(i) retains colour c, is strictly contained in top, and the branches remain pairwise incomparable.

    lines 20–25

    uses lt_trans, Finset.empty_ssubset.mpr, Finset.nonempty_iff_ne_empty.mpr

      refine ⟨∅, top, ?_, h0, htop, mid, ?_, hpair⟩
      · exact lt_trans (Finset.empty_ssubset.mpr (Finset.nonempty_iff_ne_empty.mpr (key 0)))
          (hmid 0).1
      · intro i
        exact ⟨Finset.empty_ssubset.mpr (Finset.nonempty_iff_ne_empty.mpr (key i)),
          (hmid i).1, (hmid i).2⟩
  4. Construct a colour bijection sending the colour of the empty set to the designated fan colour.

    Let c₀ = χ(∅). Since a ≥ 1, we write a = (a - 1) + 1. Identifying Fin a with Fin ((a - 1) + 1) via the canonical order isomorphism, we swap the image of c₀ with the final colour Fin.last (a - 1). This produces an equivalence e : Fin a ≃ Fin ((a - 1) + 1) that maps c₀ to Fin.last (a - 1).

    lines 30–37

    uses Fin.castOrderIso, Equiv.swap, Fin.last, Equiv.swap_apply_left

      intro χ
      have ha' : a = (a - 1) + 1 := by omega
      let c₀ : Fin a := χ ∅
      let e₀ : Fin a ≃ Fin ((a - 1) + 1) := (Fin.castOrderIso ha').toEquiv
      let e : Fin a ≃ Fin ((a - 1) + 1) := e₀.trans (Equiv.swap (e₀ c₀) (Fin.last (a - 1)))
      have he_c₀ : e c₀ = Fin.last (a - 1) := by
        show (Equiv.swap (e₀ c₀) (Fin.last (a - 1))) (e₀ c₀) = Fin.last (a - 1)
        exact Equiv.swap_apply_left _ _
  5. Apply the (a-1, 1) induction hypothesis to the recoloured hypercube.

    Define the recoloured colouring κ(A) = e(χ(A)). Applying the induction hypothesis ih to κ with a - 1 diamond colours and 1 fan colour yields either a monochromatic diamond in one of the first a - 1 colours, or a monochromatic fan in the final colour.

    lines 38–40

      let κ : Finset (Fin d) → Fin ((a - 1) + 1) := fun A => e (χ A)
      have hκ : ∀ A, κ A = e (χ A) := fun A => rfl
      rcases ih κ with ⟨col, hcol⟩ | ⟨col, hcol⟩
  6. If the induction hypothesis yields a diamond, pull it back to a monochromatic diamond for χ.

    In the first case, κ contains a monochromatic diamond in colour Fin.castAdd 1 col for some col ∈ Fin (a - 1). Because e is bijective, the lemma has_monochromatic_diamond_copy_colour_injective pulls this diamond back to a monochromatic diamond for χ in colour e.symm (Fin.castAdd 1 col), which is one of the a colours.

    lines 41–50

    uses has_monochromatic_diamond_copy_colour_injective, Fin.castAdd, Equiv.apply_symm_apply

      · left
        have hdiam : has_monochromatic_diamond_copy j d (e.symm (Fin.castAdd 1 col)) χ := by
          refine (has_monochromatic_diamond_copy_colour_injective (j := j) e e.injective
            (e.symm (Fin.castAdd 1 col)) χ κ hκ).mp ?_
          rwa [Equiv.apply_symm_apply]
        refine ⟨e.symm (Fin.castAdd 1 col), ?_⟩
        have heq : Fin.castAdd 0 (e.symm (Fin.castAdd 1 col))
            = e.symm (Fin.castAdd 1 col) := rfl
        rw [heq]
        exact hdiam
  7. If the induction hypothesis yields a fan, its colour corresponds to c₀ under the bijection.

    In the second case, κ contains a monochromatic fan in colour Fin.natAdd (a - 1) col where col ∈ Fin 1. Since Fin 1 contains only 0, col = 0. The fan colour thus simplifies to Fin.last (a - 1), which equals e(c₀) by the construction of e.

    lines 51–56

    uses Fin.natAdd, Fin.ext, Fin.last

      · left
        have hcol0 : (Fin.natAdd (a - 1) col) = e c₀ := by
          have hc : col = 0 := by ext; omega
          rw [hc, he_c₀]
          apply Fin.ext
          simp [Fin.last]
  8. Pull back the fan to χ and extend it to a monochromatic diamond in colour c₀.

    By injectivity of e, the monochromatic fan for κ in colour e(c₀) pulls back to a monochromatic fan for χ in colour c₀. Since χ(∅) = c₀, the helper lemma mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond adjoins ∅ as the bottom element to turn this fan into a monochromatic diamond for χ in colour c₀, completing the proof.

    lines 57–61

    uses has_monochromatic_fan_copy_colour_injective, mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond

        have hfan : has_monochromatic_fan_copy j d c₀ χ := by
          refine (has_monochromatic_fan_copy_colour_injective (j := j) e e.injective c₀ χ κ hκ).mp ?_
          rw [← hcol0]
          exact hcol
        exact ⟨c₀, mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond j d hj c₀ χ rfl hfan⟩
eq_or_ne
Any two elements x and y are either equal or not equal.
congrArg
Applying a function to equal arguments yields equal results.
Fin.val
The underlying natural number value of an element of Fin n.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.empty_subset
The empty set is a subset of every finite set.
lt_trans
Strict inequality (and strict subset inclusion) is transitive: a < b and b < c imply a < c.
Finset.empty_ssubset.mpr
A finite set is a strict superset of the empty set if it is nonempty.
Finset.nonempty_iff_ne_empty.mpr
A finite set is nonempty if it is not equal to the empty set.
Fin.castOrderIso
An equality of bounds n = m induces an order-preserving isomorphism between Fin n and Fin m.
Equiv.swap
The permutation that swaps two elements and fixes every other element.
Fin.last
The maximum element of Fin (n + 1), having numerical value n.
Equiv.swap_apply_left
The transposition of a and b maps a to b.
has_monochromatic_diamond_copy_colour_injective
Injective colour maps preserve and reflect the property of having a monochromatic diamond copy.
Fin.castAdd
Embeds Fin n into Fin (n + m) by preserving the numerical value.
Equiv.apply_symm_apply
Applying an equivalence to the image of its inverse is the identity.
Fin.natAdd
Embeds Fin m into Fin (n + m) by adding n to the numerical value.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
has_monochromatic_fan_copy_colour_injective
Injective colour maps preserve and reflect the property of having a monochromatic fan copy.
mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond
In dimension d with j ≥ 2, if the empty set has colour c, any monochromatic j-fan in colour c extends to a monochromatic j-diamond in colour c with bottom element ∅.

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

theorem mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond    (j d : ℕ) (hj : 2 ≤ j) {k : ℕ} (c : Fin k)    (χ : Finset (Fin d) → Fin k) (h0 : χ ∅ = c)    (hfan : has_monochromatic_fan_copy j d c χ) :    has_monochromatic_diamond_copy j d c χ := by  have : NeZero j := ⟨by omega⟩  obtain ⟨top, htop, mid, hmid, hpair⟩ := hfan  have key : ∀ i : Fin j, mid i ≠ ∅ := by    intro i hi    have hne : ∃ i' : Fin j, i' ≠ i := by      rcases eq_or_ne i 0 with h | h      · refine ⟨⟨1, by omega⟩, ?_⟩        rw [h]        intro hh        have hv := congrArg Fin.val hh        simp at hv      · exact ⟨0, fun hh => h hh.symm⟩    obtain ⟨i', hi'⟩ := hne    exact hpair i i' (Ne.symm hi') (by rw [hi]; exact Finset.empty_subset _)  refine ⟨∅, top, ?_, h0, htop, mid, ?_, hpair⟩  · exact lt_trans (Finset.empty_ssubset.mpr (Finset.nonempty_iff_ne_empty.mpr (key 0)))      (hmid 0).1  · intro i    exact ⟨Finset.empty_ssubset.mpr (Finset.nonempty_iff_ne_empty.mpr (key i)),      (hmid i).1, (hmid i).2⟩/-- b = 0 step: recolour the colour of ∅ as the single fan colour and apply the (a-1, 1) instance; a fan in that colour plus ∅ as bottom is a diamond. -/theorem mixed_diamond_fan_ramsey_bound_last_colour_step (j a d : ℕ) (hj : 2 ≤ j) (ha : 1 ≤ a)    (hd : j * a ≤ d) (ih : mixed_ramsey_property j (a - 1) 1 d) : mixed_ramsey_property j a 0 d := by  intro χ  have ha' : a = (a - 1) + 1 := by omega  let c₀ : Fin a := χ ∅  let e₀ : Fin a ≃ Fin ((a - 1) + 1) := (Fin.castOrderIso ha').toEquiv  let e : Fin a ≃ Fin ((a - 1) + 1) := e₀.trans (Equiv.swap (e₀ c₀) (Fin.last (a - 1)))  have he_c₀ : e c₀ = Fin.last (a - 1) := by    show (Equiv.swap (e₀ c₀) (Fin.last (a - 1))) (e₀ c₀) = Fin.last (a - 1)    exact Equiv.swap_apply_left _ _  let κ : Finset (Fin d) → Fin ((a - 1) + 1) := fun A => e (χ A)  have hκ : ∀ A, κ A = e (χ A) := fun A => rfl  rcases ih κ with ⟨col, hcol⟩ | ⟨col, hcol⟩  · left    have hdiam : has_monochromatic_diamond_copy j d (e.symm (Fin.castAdd 1 col)) χ := by      refine (has_monochromatic_diamond_copy_colour_injective (j := j) e e.injective        (e.symm (Fin.castAdd 1 col)) χ κ hκ).mp ?_      rwa [Equiv.apply_symm_apply]    refine ⟨e.symm (Fin.castAdd 1 col), ?_⟩    have heq : Fin.castAdd 0 (e.symm (Fin.castAdd 1 col))        = e.symm (Fin.castAdd 1 col) := rfl    rw [heq]    exact hdiam  · left    have hcol0 : (Fin.natAdd (a - 1) col) = e c₀ := by      have hc : col = 0 := by ext; omega      rw [hc, he_c₀]      apply Fin.ext      simp [Fin.last]    have hfan : has_monochromatic_fan_copy j d c₀ χ := by      refine (has_monochromatic_fan_copy_colour_injective (j := j) e e.injective c₀ χ κ hκ).mp ?_      rw [← hcol0]      exact hcol    exact ⟨c₀, mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamond j d hj c₀ χ rfl hfan⟩
See it in the graphDiscuss this resultChallenge it