AFTD Auto-Formalizing Theoretical Domains

mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours

theoremverified

Base 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 F_j in one of the b colours.

Statement

theorem mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours (j b d : ℕ) (hj : 2 ≤ j)
    (hb : 1 ≤ b) (hd : (j - 1) * b + 1 ≤ d) : mixed_ramsey_property j 0 b d
Source
step towards mixed_diamond_fan_ramsey_bound
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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…
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

This theorem establishes the base case a = 0 of the mixed diamond-fan Ramsey bound, where no colours are reserved for diamonds and all b colours are fan colours. Because the dimension d satisfies d ≥ (j - 1) * b + 1, the general fan Ramsey theorem (`fan_ramsey_bound_general`) applies directly to any colouring with 0 + b colours. Identifying the resulting monochromatic colour with a colour in Fin b via `Fin.natAdd 0` produces the desired monochromatic fan.

  1. To establish `mixed_ramsey_property j 0 b d`, it suffices to find a monochromatic fan copy for any (0 + b)-colouring χ.

    Given an arbitrary colouring χ of the subsets of `Fin d` using 0 + b colours, the definition of `mixed_ramsey_property` offers a disjunction: either a monochromatic diamond in one of the first 0 colours, or a monochromatic fan in one of the b fan colours. Since there are 0 diamond colours, the tactic `right` selects the second alternative, leaving the goal of finding a monochromatic fan in some colour `Fin.natAdd 0 col'`.

    lines 4–5

      intro χ
      right
  2. The number of colours 0 + b is at least 1, and the cardinality condition (0 + b) * (j - 1) + 1 ≤ |Fin d| holds.

    Since b ≥ 1, linear arithmetic (`omega`) shows 1 ≤ 0 + b. Furthermore, using |Fin d| = d (`Fintype.card_fin`), simplifying 0 + b to b (`Nat.zero_add`), and commutativity of multiplication (`Nat.mul_comm`), the cardinality requirement (0 + b) * (j - 1) + 1 ≤ |Fin d| reduces to (j - 1) * b + 1 ≤ d, which is exactly the hypothesis `hd`.

    lines 6–9

    uses Fintype.card_fin, Nat.zero_add, Nat.mul_comm

      have hk : 1 ≤ 0 + b := by omega
      have hcard : (0 + b) * (j - 1) + 1 ≤ Fintype.card (Fin d) := by
        rw [Fintype.card_fin, Nat.zero_add, Nat.mul_comm]
        exact hd
  3. There exists a monochromatic fan copy of size j in some colour col ∈ Fin (0 + b).

    Applying the general fan Ramsey theorem `fan_ramsey_bound_general` with k = 0 + b colours on the universe `Fin d` produces a colour `col : Fin (0 + b)`, a top subset `top`, and j pairwise incomparable subsets `mid i ⊂ top` that all share the colour `col`.

    lines 10–11

    uses fan_ramsey_bound_general

      have h := fan_ramsey_bound_general j hj (0 + b) hk (Fin d) hcard χ
      rcases h with ⟨col, top, htop, mid, hmid, hinc⟩
  4. The colour col ∈ Fin (0 + b) is equal to Fin.natAdd 0 col' for some col' ∈ Fin b.

    Since `col.val < 0 + b = b`, the underlying integer value of `col` defines a valid element `col' : Fin b`. Shifting this index by 0 via `Fin.natAdd 0` produces `col`, so we can substitute `col` with `Fin.natAdd 0 col'`.

    lines 12–16

      have hcol : ∃ col' : Fin b, Fin.natAdd 0 col' = col := by
        use ⟨col.val, by omega⟩
        ext
        simp
      rcases hcol with ⟨col', rfl⟩
  5. The monochromatic fan copy witnessed by col', top, and mid satisfies the goal.

    Supplying the re-indexed colour `col'`, the top set `top`, and the collection of subsets `mid` witnesses `has_monochromatic_fan_copy j d (Fin.natAdd 0 col') χ`, completing the proof.

    line 17

      refine ⟨col', top, htop, mid, hmid, hinc⟩
Fintype.card_fin
The cardinality of the standard finite type `Fin n` with n elements is n.
Nat.zero_add
Adding zero on the left is the identity: `0 + n = n`.
Nat.mul_comm
Multiplication of natural numbers is commutative: `n * m = m * n`.
fan_ramsey_bound_general
For any finite set α with |α| ≥ k * (j - 1) + 1 and j ≥ 2, k ≥ 1, any k-colouring of the subsets of α contains a monochromatic induced fan copy of size j.

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

/-- Base case a = 0: only fan colours, so this is fan_ramsey_bound up to the Fin (0+b) ≃ Fin b reindexing. -/theorem mixed_diamond_fan_ramsey_bound_base_zero_diamond_colours (j b d : ℕ) (hj : 2 ≤ j)    (hb : 1 ≤ b) (hd : (j - 1) * b + 1 ≤ d) : mixed_ramsey_property j 0 b d := by  intro χ  right  have hk : 1 ≤ 0 + b := by omega  have hcard : (0 + b) * (j - 1) + 1 ≤ Fintype.card (Fin d) := by    rw [Fintype.card_fin, Nat.zero_add, Nat.mul_comm]    exact hd  have h := fan_ramsey_bound_general j hj (0 + b) hk (Fin d) hcard χ  rcases h with ⟨col, top, htop, mid, hmid, hinc⟩  have hcol : ∃ col' : Fin b, Fin.natAdd 0 col' = col := by    use ⟨col.val, by omega⟩    ext    simp  rcases hcol with ⟨col', rfl⟩  refine ⟨col', top, htop, mid, hmid, hinc⟩
See it in the graphDiscuss this resultChallenge it