mixed_diamond_fan_ramsey_bound
For 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 colours, or a monochromatic induced F_j in one of the last b colours, provided d ≥ j*a + (j-1)*b + 1 when b > 0 and d ≥ j*a when b = 0.
Statement
theorem mixed_diamond_fan_ramsey_bound (j a b : ℕ) (hj : 2 ≤ j) (d : ℕ) (hd : (if b = 0 then j * a else j * a + (j - 1) * b + 1) ≤ d) : mixed_ramsey_property j a b d
- Source
- step towards diamond_poset_ramsey_number_le
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 13
- 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…
- 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…
- fan_ramsey_boundFor j ≥ 2 and k ≥ 1, every colouring of the subsets of Fin d with k colours, where d ≥ k(j-1)+1, contains a monochromatic induced copy of…
- 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…
- mixed_diamond_fan_ramsey_bound_base_zero_diamond_coloursBase case a = 0 (b ≥ 1): if d ≥ (j-1)*b + 1 then every colouring of the subsets of Fin d with 0 + b colours has a monochromatic induced…
- mixed_diamond_fan_ramsey_bound_last_colour_stepCase 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…
- has_monochromatic_diamond_copy_colour_injective_nonemptyIf ψ = f ∘ χ on nonempty sets (f injective) and ψ ∅ ≠ f col, then a monochromatic induced j-diamond in ψ of colour f col yields one in χ…
- has_monochromatic_fan_copy_colour_injective_nonemptyFor j ≥ 2, if ψ = f ∘ χ on nonempty sets (f injective), then a monochromatic induced F_j in ψ of colour f col yields one in χ of colour col.
- mixed_diamond_fan_ramsey_bound_singleton_diamond_stepCase b ≥ 1 with a singleton {x} whose colour is the diamond colour c: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a-1, b+1) in…
- mixed_diamond_fan_ramsey_bound_all_singletons_fan_coloursCase b ≥ 2 with every singleton fan-coloured: if d ≥ j*a + (j-1)*b + 1 and the statement holds at (a, b-1) in dimension d-(j-1), then χ…
- mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colourCase 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…
- Used by 2
- diamond_poset_ramsey_propertyFor j ≥ 2 and k ≥ 1, every colouring of the subsets of Fin (j*k) with k colours has a monochromatic induced copy of the j-diamond…
- diamond_poset_ramsey_number_leFor all natural numbers j ≥ 2 and k ≥ 1, the k-color poset Ramsey number of the j-diamond DiamondPoset j is at most j * k.
The proof, explained
The theorem establishes an upper bound on the Ramsey number for finding either an induced monochromatic j-diamond in one of a colours or an induced monochromatic j-fan in one of b colours among subsets of Fin d. The proof proceeds by strong induction on the total number of colours k = a + b, accompanied by an inner strong induction on the number of diamond colours a for a fixed k. In the non-trivial case where a > 0 and b > 0, the argument examines the colours of singletons {x}: if any singleton receives a diamond colour, the problem reduces to (a - 1, b + 1, d - 1) via the inner induction hypothesis; otherwise, all singletons receive fan colours, reducing the problem to (a, 0, d - j) when b = 1 or (a, b - 1, d - (j - 1)) when b ≥ 2, both of which are resolved by the outer induction hypothesis since the total number of colours strictly decreases.
It suffices to prove the Ramsey bound for all k, a, b, and d where a + b = k.
We generalize the goal by introducing the total number of colours k = a + b and universally quantifying over k, a, b, and d. Once this general statement H is proved, applying it to a + b, a, b, and d immediately implies the original theorem.
classical suffices H : ∀ k : ℕ, ∀ a b : ℕ, a + b = k → ∀ d : ℕ, (if b = 0 then j * a else j * a + (j - 1) * b + 1) ≤ d → mixed_ramsey_property j a b d by exact H (a + b) a b rfl d hdSets up strong induction on the total number of colours k = a + b, followed by strong induction on the number of diamond colours a for fixed k.
We induct strongly on k using Nat.strong_induction_on, yielding an induction hypothesis ihk for strictly fewer total colours. For fixed k, we induct strongly on a using Nat.strong_induction_on, yielding an induction hypothesis iha for strictly fewer diamond colours with the same total sum a + b = k. We then fix b, the equality a + b = k, the dimension d, and the dimension bound hd'.
uses
Nat.strong_induction_onintro k induction k using Nat.strong_induction_on with | h k ihk => intro a induction a using Nat.strong_induction_on with | h a iha => intro b hab d hd'
The Ramsey property holds in the base cases where there are no diamond colours (a = 0).
We case split on a using Nat.eq_zero_or_pos. When a = 0, we further split on b: if b = 0, the colouring maps into Fin 0, which has no elements, so the goal follows vacuously by Fin.elim0. If b > 0, the result is given by the base lemma mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours, whose dimension requirement (j - 1) * b + 1 ≤ d matches the simplified assumption hd'.
uses
Nat.eq_zero_or_pos,Fin.elim0,mixed_diamond_fan_ramsey_bound_base_zero_diamond_coloursrcases Nat.eq_zero_or_pos a with ha0 | ha · subst ha0 rcases Nat.eq_zero_or_pos b with hb0 | hb · subst hb0 intro χ exact Fin.elim0 (χ ∅) · exact mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours j b d hj hb (by have hbne : b ≠ 0 := by omega simpa [hbne] using hd')
The Ramsey property holds when a > 0 and there are no fan colours (b = 0).
When b = 0, the reduction lemma mixed_diamond_fan_ramsey_bound_last_colour_step reduces the problem for (a, 0) on Fin d to (a - 1, 1) on Fin d. Because (a - 1) + 1 = a = k and a - 1 < a, this subproblem is solved by the inner induction hypothesis iha. The required dimension bound j * (a - 1) + (j - 1) * 1 + 1 ≤ d simplifies to j * a ≤ d, which matches the hypothesis.
uses
Nat.eq_zero_or_pos,mixed_diamond_fan_ramsey_bound_last_colour_step,Nat.mul_succ,if_neg· rcases Nat.eq_zero_or_pos b with hb0 | hb · subst hb0 refine mixed_diamond_fan_ramsey_bound_last_colour_step j a d hj ha (by simpa using hd') ?_ refine iha (a - 1) (by omega) 1 (by omega) d ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hd1 : j * a ≤ d := by simpa using hd' simp only [if_neg (show (1:ℕ) ≠ 0 by norm_num)] omega
For a > 0 and b > 0, simplify the dimension bound to j * a + (j - 1) * b + 1 ≤ d and fix a colouring χ.
Since b is strictly positive, b ≠ 0, allowing the if-condition in the dimension hypothesis to simplify to j * a + (j - 1) * b + 1 ≤ d. We then introduce an arbitrary colouring χ of the subsets of Fin d with a + b colours.
· have hbne : b ≠ 0 := by omega have hdj : j * a + (j - 1) * b + 1 ≤ d := by simpa [hbne] using hd' intro χ
If some singleton {x} receives a diamond colour c, the colouring contains a monochromatic induced diamond or fan.
We case split on whether there exists a singleton {x} coloured by one of the first a colours. If such an x and colour c exist, mixed_diamond_fan_ramsey_bound_singleton_diamond_step reduces the goal to the Ramsey property for a - 1 diamond colours and b + 1 fan colours in dimension d - 1. Since (a - 1) + (b + 1) = k and a - 1 < a, this is proved by the inner induction hypothesis iha. The dimension condition follows by expanding the arithmetic and using Nat.le_sub_iff_add_le.
uses
mixed_diamond_fan_ramsey_bound_singleton_diamond_step,Nat.mul_succ,if_neg,Nat.le_sub_iff_add_leby_cases hA : ∃ (x : Fin d) (c : Fin a), χ {x} = Fin.castAdd b c · obtain ⟨x, c, hxc⟩ := hA refine mixed_diamond_fan_ramsey_bound_singleton_diamond_step j a b d hj ha hb hdj ?_ χ x c hxc refine iha (a - 1) (by omega) (b + 1) (by omega) (d - 1) ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hjb : (j - 1) * (b + 1) = (j - 1) * b + (j - 1) := by rw [Nat.mul_succ] simp only [if_neg (show b + 1 ≠ 0 by omega)] rw [Nat.le_sub_iff_add_le (by omega : 1 ≤ d)] omega
If no singleton receives a diamond colour, then every singleton {x} is coloured by one of the b fan colours.
Assuming no singleton receives a diamond colour, we apply Fin.addCases to inspect the colour χ({x}) of each singleton. Since having a diamond colour leads to a contradiction, χ({x}) must be an image under Fin.natAdd a, meaning every singleton receives a fan colour.
uses
Fin.addCases· push Not at hA have hxall : ∀ x : Fin d, ∃ c : Fin b, χ {x} = Fin.natAdd a c := by intro x rcases Fin.addCases (motive := fun γ => (∃ c : Fin a, γ = Fin.castAdd b c) ∨ (∃ c : Fin b, γ = Fin.natAdd a c)) (fun i => Or.inl ⟨i, rfl⟩) (fun i => Or.inr ⟨i, rfl⟩) (χ {x}) with ⟨c, hc⟩ | ⟨c, hc⟩ · exact absurd hc (hA x c) · exact ⟨c, hc⟩
If all singletons receive fan colours and b = 1, the colouring contains a monochromatic induced diamond or fan.
When b = 1, the only fan colour is 0 because Fin 1 is a subsingleton. The lemma mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour reduces the problem to dimension d - j with a diamond colours and 0 fan colours. Because the new total number of colours is a + 0 = a < a + 1 = k, this subproblem is closed by the outer induction hypothesis ihk. The dimension inequality j * a + j ≤ d is rearranged via Nat.le_sub_iff_add_le to j * a ≤ d - j.
uses
Nat.eq_or_lt_of_le,Nat.mul_one,Nat.sub_one_add_one,mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour,Nat.le_sub_iff_add_le,Subsingleton.elimrcases Nat.eq_or_lt_of_le hb with hb1 | hb2 · have hb1' : b = 1 := by omega subst hb1' have hjeq : (j - 1) * 1 + 1 = j := by rw [Nat.mul_one, Nat.sub_one_add_one (by omega : j ≠ 0)] have hdaj : j * a + j ≤ d := by omega refine mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour j a d hj ha hdaj ?_ χ ?_ · refine ihk (a + 0) (by omega) a 0 (by omega) (d - j) ?_ rw [Nat.le_sub_iff_add_le (by omega : j ≤ d)] exact hdaj · intro x obtain ⟨c, hc⟩ := hxall x obtain rfl : c = 0 := Subsingleton.elim c 0 exact hc
If all singletons receive fan colours and b ≥ 2, the colouring contains a monochromatic induced diamond or fan.
When b ≥ 2, mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours reduces the problem to dimension d - (j - 1) with a diamond colours and b - 1 fan colours. The total colour count is a + (b - 1) < a + b = k, so the outer induction hypothesis ihk applies. Expanding the product terms using Nat.mul_succ shows that the required dimension bound is equivalent to the initial dimension bound hdj.
uses
mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours,Nat.mul_succ,Nat.le_mul_of_pos_right,if_neg,Nat.le_sub_iff_add_le· refine mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours j a b d hj ha hb2 hdj ?_ χ hxall refine ihk (a + (b - 1)) (by omega) a (b - 1) (by omega) (d - (j - 1)) ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hjb : (j - 1) * b = (j - 1) * (b - 1) + (j - 1) := by rw [← Nat.mul_succ (j - 1) (b - 1)]; congr 1; omega have hja2 : j ≤ j * a := Nat.le_mul_of_pos_right j (by omega : 0 < a) simp only [if_neg (show b - 1 ≠ 0 by omega)] rw [Nat.le_sub_iff_add_le (by omega : j - 1 ≤ d)] omega
Fin.addCases- Every element of Fin (m + n) is either the image under Fin.castAdd of an element of Fin m, or the image under Fin.natAdd of an element of Fin n.
Fin.elim0- The empty type Fin 0 has no elements; given an element of Fin 0, any goal follows by ex falso.
if_neg- If the condition c is false, then (if c then t else e) simplifies to the else-branch e.
mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour- For j ≥ 2, a ≥ 1, and d ≥ j * a + j, if all singletons receive the single fan colour 0, the Ramsey property holds provided it holds for a diamond colours and 0 fan colours on Fin (d - j).
mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours- For j ≥ 2, a ≥ 1, b ≥ 2, and d ≥ j * a + (j - 1) * b + 1, if all singletons receive fan colours, the Ramsey property holds provided it holds for a diamond colours and b - 1 fan colours on Fin (d - (j - 1)).
mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours- For j ≥ 2, b ≥ 1, and d ≥ (j - 1) * b + 1, any colouring of subsets of Fin d with 0 diamond colours and b fan colours contains a monochromatic j-fan in one of the b colours.
mixed_diamond_fan_ramsey_bound_last_colour_step- For j ≥ 2, a ≥ 1, and d ≥ j * a, the Ramsey property for a diamond colours and 0 fan colours on Fin d reduces to the Ramsey property for a - 1 diamond colours and 1 fan colour on Fin d.
mixed_diamond_fan_ramsey_bound_singleton_diamond_step- For j ≥ 2, a ≥ 1, b ≥ 1, and d ≥ j * a + (j - 1) * b + 1, if some singleton {x} receives a diamond colour c, the Ramsey property holds provided it holds for a - 1 diamond colours and b + 1 fan colours on Fin (d - 1).
Nat.eq_or_lt_of_le- If n ≤ m, then either n = m or n < m.
Nat.eq_zero_or_pos- Every natural number is either equal to 0 or strictly positive.
Nat.le_sub_iff_add_le- For k ≤ m, the inequality n ≤ m - k is equivalent to n + k ≤ m.
Nat.le_mul_of_pos_right- If m is strictly positive, then n ≤ n * m.
Nat.mul_one- Multiplying any natural number by 1 leaves it unchanged: n * 1 = n.
Nat.mul_succ- Multiplication distributes over successor: n * (m + 1) = n * m + n.
Nat.strong_induction_on- Strong induction on natural numbers: to prove p(n) for all n, it suffices to prove p(n) assuming p(m) holds for all m < n.
Nat.sub_one_add_one- For any nonzero natural number a, (a - 1) + 1 = a.
Subsingleton.elim- In a subsingleton type (such as Fin 1), any two elements are equal.
- The total colour set Fin (a + b) is partitioned into the first a colours (the diamond colours, embedded via Fin.castAdd) and the remaining b colours (the fan colours, embedded via Fin.natAdd).
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 7 of arXiv:2610.20545: with a colours assigned the j-diamond and b colours assigned F_j, the Ramsey number is at most j*a + (j-1)*b + 1 when b > 0, and at most j*a when b = 0. -/theorem mixed_diamond_fan_ramsey_bound (j a b : ℕ) (hj : 2 ≤ j) (d : ℕ) (hd : (if b = 0 then j * a else j * a + (j - 1) * b + 1) ≤ d) : mixed_ramsey_property j a b d := by classical suffices H : ∀ k : ℕ, ∀ a b : ℕ, a + b = k → ∀ d : ℕ, (if b = 0 then j * a else j * a + (j - 1) * b + 1) ≤ d → mixed_ramsey_property j a b d by exact H (a + b) a b rfl d hd intro k induction k using Nat.strong_induction_on with | h k ihk => intro a induction a using Nat.strong_induction_on with | h a iha => intro b hab d hd' rcases Nat.eq_zero_or_pos a with ha0 | ha · subst ha0 rcases Nat.eq_zero_or_pos b with hb0 | hb · subst hb0 intro χ exact Fin.elim0 (χ ∅) · exact mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours j b d hj hb (by have hbne : b ≠ 0 := by omega simpa [hbne] using hd') · rcases Nat.eq_zero_or_pos b with hb0 | hb · subst hb0 refine mixed_diamond_fan_ramsey_bound_last_colour_step j a d hj ha (by simpa using hd') ?_ refine iha (a - 1) (by omega) 1 (by omega) d ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hd1 : j * a ≤ d := by simpa using hd' simp only [if_neg (show (1:ℕ) ≠ 0 by norm_num)] omega · have hbne : b ≠ 0 := by omega have hdj : j * a + (j - 1) * b + 1 ≤ d := by simpa [hbne] using hd' intro χ by_cases hA : ∃ (x : Fin d) (c : Fin a), χ {x} = Fin.castAdd b c · obtain ⟨x, c, hxc⟩ := hA refine mixed_diamond_fan_ramsey_bound_singleton_diamond_step j a b d hj ha hb hdj ?_ χ x c hxc refine iha (a - 1) (by omega) (b + 1) (by omega) (d - 1) ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hjb : (j - 1) * (b + 1) = (j - 1) * b + (j - 1) := by rw [Nat.mul_succ] simp only [if_neg (show b + 1 ≠ 0 by omega)] rw [Nat.le_sub_iff_add_le (by omega : 1 ≤ d)] omega · push Not at hA have hxall : ∀ x : Fin d, ∃ c : Fin b, χ {x} = Fin.natAdd a c := by intro x rcases Fin.addCases (motive := fun γ => (∃ c : Fin a, γ = Fin.castAdd b c) ∨ (∃ c : Fin b, γ = Fin.natAdd a c)) (fun i => Or.inl ⟨i, rfl⟩) (fun i => Or.inr ⟨i, rfl⟩) (χ {x}) with ⟨c, hc⟩ | ⟨c, hc⟩ · exact absurd hc (hA x c) · exact ⟨c, hc⟩ rcases Nat.eq_or_lt_of_le hb with hb1 | hb2 · have hb1' : b = 1 := by omega subst hb1' have hjeq : (j - 1) * 1 + 1 = j := by rw [Nat.mul_one, Nat.sub_one_add_one (by omega : j ≠ 0)] have hdaj : j * a + j ≤ d := by omega refine mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colour j a d hj ha hdaj ?_ χ ?_ · refine ihk (a + 0) (by omega) a 0 (by omega) (d - j) ?_ rw [Nat.le_sub_iff_add_le (by omega : j ≤ d)] exact hdaj · intro x obtain ⟨c, hc⟩ := hxall x obtain rfl : c = 0 := Subsingleton.elim c 0 exact hc · refine mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours j a b d hj ha hb2 hdj ?_ χ hxall refine ihk (a + (b - 1)) (by omega) a (b - 1) (by omega) (d - (j - 1)) ?_ have hja : j * a = j * (a - 1) + j := by rw [← Nat.mul_succ j (a - 1)]; congr 1; omega have hjb : (j - 1) * b = (j - 1) * (b - 1) + (j - 1) := by rw [← Nat.mul_succ (j - 1) (b - 1)]; congr 1; omega have hja2 : j ≤ j * a := Nat.le_mul_of_pos_right j (by omega : 0 < a) simp only [if_neg (show b - 1 ≠ 0 by omega)] rw [Nat.le_sub_iff_add_le (by omega : j - 1 ≤ d)] omega