mixed_diamond_fan_ramsey_bound_last_colour_step
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.
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.
have : NeZero j := ⟨by omega⟩ obtain ⟨top, htop, mid, hmid, hpair⟩ := hfan
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.
uses
eq_or_ne,congrArg,Fin.val,Ne.symm,Finset.empty_subsethave 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 _)
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.
uses
lt_trans,Finset.empty_ssubset.mpr,Finset.nonempty_iff_ne_empty.mprrefine ⟨∅, 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⟩
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).
uses
Fin.castOrderIso,Equiv.swap,Fin.last,Equiv.swap_apply_leftintro χ 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 _ _
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.
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⟩
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.
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
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.
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]
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.
uses
has_monochromatic_fan_copy_colour_injective,mixed_diamond_fan_ramsey_bound_last_colour_step_fan_to_diamondhave 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 ∅.
- The induction hypothesis operates on colourings into Fin ((a - 1) + 1). In the formal proof, aligning the colour of the empty set with the designated fan colour requires explicitly constructing an order isomorphism and transposing two elements via Equiv.swap, whereas on paper this is treated as a routine relabelling of colours.
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.
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⟩