mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour
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 thanLinearOrder— 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
LinearOrderis aTotalPreorder. - 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.
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.
have hj_le_d : j ≤ d := by have : j * 1 + j ≤ j * a + j := by nlinarith omega
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.
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.extby_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
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.
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
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.
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_deflet 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]
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)).
uses
Fin.natAddhave 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⟩
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 χ.
uses
Fin.castAdd,congrArgrcases 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.
- The identification of Fin d with Fin (j + (d - j)) and the definitions of Y_emb and emb are formal infrastructure to partition the coordinates into two disjoint blocks of sizes j and d - j.
- In Step 6, the fan alternative of the induction hypothesis mixed_ramsey_property j a 0 (d - j) produces a colour in Fin 0, which is eliminated as impossible (col.elim0), leaving only the diamond alternative.
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.
/-- 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