AFTD Auto-Formalizing Theoretical Domains

mixed_diamond_fan_ramsey_bound

theoremverified

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
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.

  1. 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.

    lines 5–9

      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
  2. Sets 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'.

    lines 10–16

    uses Nat.strong_induction_on

      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'
  3. 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'.

    lines 17–25

    uses Nat.eq_zero_or_pos, Fin.elim0, mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours

          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')
  4. 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.

    lines 26–34

    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
  5. 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.

    lines 35–37

            · have hbne : b ≠ 0 := by omega
              have hdj : j * a + (j - 1) * b + 1 ≤ d := by simpa [hbne] using hd'
              intro χ
  6. 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.

    lines 38–47

    uses mixed_diamond_fan_ramsey_bound_singleton_diamond_step, Nat.mul_succ, if_neg, Nat.le_sub_iff_add_le

              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
  7. 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.

    lines 48–57

    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⟩
  8. 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.

    lines 58–71

    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.elim

                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
  9. 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.

    lines 72–81

    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.

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 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
See it in the graphDiscuss this resultChallenge it