AFTD Auto-Formalizing Theoretical Domains

fan_ramsey_bound

theoremverified

For 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 F_j (a maximum element over an antichain of size j).

Statement

theorem fan_ramsey_bound (j k d : ℕ) (hj : 2 ≤ j) (hk : 1 ≤ k) (hd : k * (j - 1) + 1 ≤ d)
    (χ : Finset (Fin d) → Fin k) : ∃ col : Fin k, has_monochromatic_fan_copy j d col χ
Source
step towards diamond_poset_ramsey_number_le
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • exists_hitting_set_of_no_large_antichainLet G be a finite family of nonempty subsets of a finite set α, w a natural number, and suppose every subfamily H ⊆ G that is an antichain…
Used by 3

The proof, explained

The theorem is proved by induction on the number of colours k ≥ 1. For k = 1, any subset T of size j together with its j maximal proper subsets T \ {a} forms a monochromatic copy of F_j. For k ≥ 2, let c be the colour of the entire ground set α. If the family G of non-empty subsets of colour c contains an antichain of size j, then α and this antichain form a monochromatic F_j of colour c. Otherwise, every antichain in G has size at most j - 1, so by Dilworth's theorem (via a hitting set lemma), there is a hitting set S ⊆ α of size at most j - 1 intersecting every set in G; removing S leaves a subset T = α \ S of size at least (k - 1)(j - 1) + 1 on which no non-empty subset has colour c, allowing the induction hypothesis with k - 1 colours to produce the desired monochromatic F_j.

  1. Under the assumptions 1 ≤ k, k(j - 1) + 1 ≤ d, and s ≤ j - 1, the inequality (k - 1)(j - 1) + 1 ≤ d - s holds.

    Rewrite (k - 1)(j - 1) + (j - 1) as ((k - 1) + 1)(j - 1) = k(j - 1) using right-distributivity and cancellation of subtraction. Then linear arithmetic via omega deduces (k - 1)(j - 1) + 1 ≤ d - s from k(j - 1) + 1 ≤ d and s ≤ j - 1.

    lines 3–7

    uses one_mul, Nat.add_mul, Nat.sub_add_cancel

      have h1 : (k - 1) * (j - 1) + (j - 1) = k * (j - 1) := by
        calc (k - 1) * (j - 1) + (j - 1) = (k - 1) * (j - 1) + 1 * (j - 1) := by rw [one_mul]
          _ = ((k - 1) + 1) * (j - 1) := by rw [Nat.add_mul]
          _ = k * (j - 1) := by rw [Nat.sub_add_cancel hk]
      omega
  2. In a finite set α of size at least j, there exists a subset T of size j and an injective enumeration of its single-element deletions, each of size j - 1.

    Choose a subset T ⊆ α of cardinality j using Finset.exists_subset_card_eq. Construct a bijection eT between T and Fin j, enumerating the elements of T injectively as a i. For each index i, define mid i = T \ {a i}; by Finset.card_erase_of_mem, each mid i has cardinality exactly j - 1.

    lines 13–25

    uses Finset.exists_subset_card_eq, Finset.equivFinOfCardEq, Subtype.ext, Finset.card_erase_of_mem

      classical
      obtain ⟨T, -, hTcard⟩ := Finset.exists_subset_card_eq (s := (Finset.univ : Finset α)) (n := j) (by simpa using hd)
      let eT : ↥T ≃ Fin j := Finset.equivFinOfCardEq hTcard
      let a : Fin j → α := fun i => (eT.symm i).1
      have ha_mem : ∀ i, a i ∈ T := fun i => (eT.symm i).2
      have ha_inj : Function.Injective a := by
        intro i i' h
        exact eT.symm.injective (Subtype.ext h)
      let mid : Fin j → Finset α := fun i => T.erase (a i)
      have hmid_card : ∀ i, (mid i).card = j - 1 := by
        intro i
        simp only [mid]
        rw [Finset.card_erase_of_mem (ha_mem i), hTcard]
  3. T and the family mid form a monochromatic copy of F_j of the unique colour 0.

    Because there is only one colour in Fin 1, all colour equalities hold trivially by Subsingleton.elim. Each mid i is a strict subset of T because mid i ⊆ T and their cardinalities are j - 1 and j (which differ since j ≥ 2). Moreover, the family mid is an antichain: if mid i ⊆ mid i', card equality forces mid i = mid i', so a i ∈ mid i' = mid i, which contradicts a i ∉ T \ {a i}.

    lines 26–41

    uses Subsingleton.elim, Finset.ssubset_iff_subset_ne.mpr, Finset.erase_subset, Finset.mem_erase, Finset.notMem_erase, Finset.eq_of_subset_of_card_le, le_of_eq

      refine ⟨0, T, Subsingleton.elim _ _, mid, ?_, ?_⟩
      · intro i
        refine ⟨Finset.ssubset_iff_subset_ne.mpr ⟨Finset.erase_subset _ _, ?_⟩, Subsingleton.elim _ _⟩
        intro h
        have h1 := hmid_card i
        rw [h, hTcard] at h1
        omega
      · intro i i' hii hsub
        have hne : mid i ≠ mid i' := by
          intro h
          have hmem' : a i ∈ mid i' := by
            simp only [mid, Finset.mem_erase]
            exact ⟨fun heq => hii (ha_inj heq), ha_mem i⟩
          rw [← h] at hmem'
          exact Finset.notMem_erase (a i) T hmem'
        exact hne (Finset.eq_of_subset_of_card_le hsub (le_of_eq (by rw [hmid_card i', hmid_card i])))
  4. The general Ramsey bound holds for k = 1, and the case k = 0 is impossible.

    Proceed by induction on k. The case k = 0 is ruled out by omega since 1 ≤ k. For k = 1, the goal reduces to the base lemma fan_ramsey_bound_base_one_gen since j ≤ 1 * (j - 1) + 1 ≤ |α|.

    lines 49–55

    uses fan_ramsey_bound_base_one_gen

      intro k
      induction k with
      | zero => intro hk; omega
      | succ k ih =>
        intro _hk α _instF _instD hcard χ
        cases k with
        | zero => exact fan_ramsey_bound_base_one_gen j hj (by omega) χ
  5. For the inductive step with k = m + 2 colours, identify the colour c of the universal set α and the family G of non-empty subsets of colour c.

    Let c = χ α be the colour assigned to the entire universe α = Finset.univ. Define G to be the family of all non-empty subsets of α whose colour under χ is c.

    lines 56–60

        | succ m =>
          have ih' := ih (by omega)
          classical
          let c : Fin (m + 2) := χ Finset.univ
          let G : Finset (Finset α) := Finset.univ.filter (fun A => A.Nonempty ∧ χ A = c)
  6. If G contains an antichain of size at least j, then α together with a sub-antichain of size j forms a monochromatic copy of F_j of colour c.

    Extract a sub-antichain H' ⊆ G of size exactly j, and index its elements injectively as mid i. Each mid i has colour c. Furthermore, each mid i is strictly contained in α: if mid i were equal to α, then any other branch mid i' (which exists since j ≥ 2) would be a subset of mid i, contradicting that H' is an antichain. Thus α as top and mid as branches form a monochromatic copy of F_j of colour c.

    lines 61–92

    uses Finset.exists_subset_card_eq, Finset.mem_filter.mp, Finset.equivFinOfCardEq, Subtype.ext, Finset.ssubset_iff_subset_ne.mpr, Finset.subset_univ

          by_cases hant : ∃ H : Finset (Finset α),
              H ⊆ G ∧ (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) ∧ j ≤ H.card
          · obtain ⟨H, hHG, hHanti, hjH⟩ := hant
            obtain ⟨H', hH'H, hH'card⟩ := Finset.exists_subset_card_eq hjH
            have hH'anti : ∀ A ∈ H', ∀ B ∈ H', A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A :=
              fun A hA B hB => hHanti A (hH'H hA) B (hH'H hB)
            have hH'χ : ∀ A ∈ H', χ A = c :=
              fun A hA => (Finset.mem_filter.mp (hHG (hH'H hA))).2.2
            let eH : ↥H' ≃ Fin j := Finset.equivFinOfCardEq hH'card
            let mid : Fin j → Finset α := fun i => (eH.symm i).1
            have hmid_mem : ∀ i, mid i ∈ H' := fun i => (eH.symm i).2
            have hmid_inj : Function.Injective mid := by
              intro i i' h
              exact eH.symm.injective (Subtype.ext h)
            have hother : ∀ i : Fin j, ∃ i' : Fin j, i' ≠ i := by
              intro i
              by_cases h : (⟨0, by omega⟩ : Fin j) = i
              · exact ⟨⟨1, by omega⟩, by rw [← h]; simp⟩
              · exact ⟨⟨0, by omega⟩, h⟩
            refine ⟨c, Finset.univ, rfl, mid, ?_, ?_⟩
            · intro i
              constructor
              · refine Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ _, ?_⟩
                intro h
                obtain ⟨i', hi'⟩ := hother i
                have hsub : mid i' ⊆ mid i := by rw [h]; exact Finset.subset_univ _
                exact (hH'anti (mid i') (hmid_mem i') (mid i) (hmid_mem i)
                  (fun heq => hi' (hmid_inj heq))).1 hsub
              · exact hH'χ (mid i) (hmid_mem i)
            · intro i i' hii hsub
              exact (hH'anti (mid i) (hmid_mem i) (mid i') (hmid_mem i')
                (fun h => hii (hmid_inj h))).1 hsub
  7. If G contains no antichain of size j, there is a hitting set S ⊆ α of size at most j - 1 for G, and its complement T = α \ S has size at least (m + 1)(j - 1) + 1.

    When G has no antichain of size j, every antichain in G has cardinality at most j - 1. By exists_hitting_set_of_no_large_antichain, there exists a hitting set S ⊆ α with |S| ≤ j - 1 intersecting every member of G. The complement T = α \ S has size |T| = |α| - |S|; applying the arithmetic lemma fan_ramsey_bound_arith shows that |T| ≥ (m + 1)(j - 1) + 1.

    lines 93–108

    uses Finset.mem_filter.mp, exists_hitting_set_of_no_large_antichain, Finset.card_sdiff_of_subset, Finset.subset_univ, Finset.card_univ, Fintype.card_coe, fan_ramsey_bound_arith

          · have hbound : ∀ H : Finset (Finset α), H ⊆ G →
                (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) → H.card ≤ j - 1 := by
              intro H hHG hanti
              by_contra hcon
              push Not at hcon
              exact hant ⟨H, hHG, hanti, by omega⟩
            have hGne : ∀ A ∈ G, A.Nonempty := fun A hA => (Finset.mem_filter.mp hA).2.1
            obtain ⟨S, hScard, hShit⟩ :=
              exists_hitting_set_of_no_large_antichain α G (j - 1) hGne hbound
            let T : Finset α := Finset.univ \ S
            have hTcard : (m + 1) * (j - 1) + 1 ≤ Fintype.card ↥T := by
              have hcard' : T.card = Fintype.card α - S.card := by
                rw [show T = Finset.univ \ S from rfl, Finset.card_sdiff_of_subset (Finset.subset_univ S),
                  Finset.card_univ]
              rw [Fintype.card_coe, hcard']
              exact fan_ramsey_bound_arith j (m + 2) (Fintype.card α) S.card (by omega) hcard hScard
  8. No non-empty subset of T has colour c under χ.

    Let emb : T ↪ α be the subtype embedding. If a non-empty subset A ⊆ T had colour c, its image under emb would belong to G and thus must intersect the hitting set S. But the image is contained in T = α \ S, so any intersecting element would belong to both T and S, a contradiction.

    lines 109–123

    uses Function.Embedding.subtype, Finset.mem_map, Finset.Nonempty.map, Finset.mem_univ, Finset.mem_inter, Finset.mem_sdiff

            let emb : ↥T ↪ α := Function.Embedding.subtype (· ∈ T)
            have hmapT : ∀ A : Finset ↥T, A.map emb ⊆ T := by
              intro A x hx
              rw [Finset.mem_map] at hx
              obtain ⟨y, hy, rfl⟩ := hx
              exact y.2
            have hne_col : ∀ A : Finset ↥T, A.Nonempty → χ (A.map emb) ≠ c := by
              intro A hA hχ
              have hBne : (A.map emb).Nonempty := Finset.Nonempty.map (f := emb) hA
              have hBG : A.map emb ∈ G := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hBne, hχ⟩
              obtain ⟨x, hx⟩ := hShit (A.map emb) hBG
              rw [Finset.mem_inter] at hx
              have hxT : x ∈ T := hmapT A hx.1
              rw [Finset.mem_sdiff] at hxT
              exact hxT.2 hx.2
  9. The colours different from c can be identified with Fin (m + 1), yielding a reduced colouring χ' on subsets of T using m + 1 colours.

    The set of colours in Fin (m + 2) distinct from c has size m + 1. We form a bijection e between this set and Fin (m + 1), and define a colouring χ' on Finset ↥T by mapping non-empty subsets through χ and e (sending empty sets to 0). For every non-empty subset A, lifting χ' A back to Fin (m + 2) recovers χ (A.map emb).

    lines 124–137

    uses Fintype.card_subtype, Finset.mem_erase, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_univ, Fintype.card_fin, Fintype.equivFinOfCardEq, dif_pos, congrArg, Subtype.val

            have hcard_sub : Fintype.card {x : Fin (m + 2) // x ≠ c} = m + 1 := by
              rw [Fintype.card_subtype]
              have hfilter : (Finset.univ.filter (fun x : Fin (m + 2) => x ≠ c)) = Finset.univ.erase c := by
                ext x; simp [Finset.mem_erase]
              rw [hfilter, Finset.card_erase_of_mem (Finset.mem_univ c), Finset.card_univ, Fintype.card_fin]
              omega
            let e : {x : Fin (m + 2) // x ≠ c} ≃ Fin (m + 1) := Fintype.equivFinOfCardEq hcard_sub
            let lift : Fin (m + 1) → Fin (m + 2) := fun y => (e.symm y).1
            let χ' : Finset ↥T → Fin (m + 1) := fun A =>
              if h : A.Nonempty then e ⟨χ (A.map emb), hne_col A h⟩ else 0
            have hχ'_spec : ∀ (A : Finset ↥T) (hA : A.Nonempty), lift (χ' A) = χ (A.map emb) := by
              intro A hA
              simp only [χ', dif_pos hA, lift]
              exact congrArg Subtype.val (e.symm_apply_apply ⟨χ (A.map emb), hne_col A hA⟩)
  10. Applying the induction hypothesis to T under χ' yields a monochromatic copy of F_j, which embeds into α.

    By the induction hypothesis applied to T (which has size at least (m + 1)(j - 1) + 1 and m + 1 colours), there is a monochromatic fan (top', mid') of colour col'. The branches mid' i cannot be empty because they form an antichain of size j ≥ 2, and consequently top' is non-empty. Pushing top' and mid' into α via the embedding emb preserves strict inclusion and incomparability, yielding a monochromatic copy of F_j in α of colour lift col'.

    lines 138–163

    uses Finset.not_nonempty_iff_eq_empty, Ne.symm, Finset.empty_subset, Finset.Nonempty.mono, Finset.ssubset_iff_subset_ne.mp, Finset.ssubset_iff_subset_ne.mpr

            obtain ⟨col', top', htop'col, mid', hmid'spec, hmid'anti⟩ := ih' ↥T hTcard χ'
            have hmid'_ne : ∀ i, (mid' i).Nonempty := by
              intro i
              by_contra hcon
              rw [Finset.not_nonempty_iff_eq_empty] at hcon
              obtain ⟨i', hi'⟩ : ∃ i' : Fin j, i' ≠ i := by
                by_cases h : (⟨0, by omega⟩ : Fin j) = i
                · exact ⟨⟨1, by omega⟩, by rw [← h]; simp⟩
                · exact ⟨⟨0, by omega⟩, h⟩
              exact hmid'anti i i' (Ne.symm hi') (by rw [hcon]; exact Finset.empty_subset _)
            have htop'_ne : top'.Nonempty :=
              Finset.Nonempty.mono
                (Finset.ssubset_iff_subset_ne.mp ((hmid'spec (⟨0, by omega⟩ : Fin j)).1)).1
                (hmid'_ne _)
            refine ⟨lift col', top'.map emb, ?_, fun i => (mid' i).map emb, ?_, ?_⟩
            · rw [← hχ'_spec top' htop'_ne, htop'col]
            · intro i
              constructor
              · refine Finset.ssubset_iff_subset_ne.mpr
                  ⟨Finset.map_subset_map.mpr
                    (Finset.ssubset_iff_subset_ne.mp ((hmid'spec i).1)).1, ?_⟩
                intro h
                exact (Finset.ssubset_iff_subset_ne.mp ((hmid'spec i).1)).2 (Finset.map_inj.mp h)
              · rw [← hχ'_spec (mid' i) (hmid'_ne i), (hmid'spec i).2]
            · intro i i' hii hsub
              exact hmid'anti i i' hii (Finset.map_subset_map.mp hsub)
  11. The main theorem fan_ramsey_bound holds for α = Fin d.

    Apply fan_ramsey_bound_general to the type Fin d, whose cardinality is d ≥ k(j - 1) + 1, and simplify using the definition has_monochromatic_fan_copy.

    lines 168–169

    uses fan_ramsey_bound_general, has_monochromatic_fan_copy

      have h := fan_ramsey_bound_general j hj k hk (Fin d) (by simpa using hd) χ
      simpa [has_monochromatic_fan_copy] using h
one_mul
Multiplying by 1 on the left leaves an element unchanged: 1 * a = a.
Nat.add_mul
Multiplication of natural numbers distributes over addition from the right: (n + m) * k = n * k + m * k.
Nat.sub_add_cancel
Subtracting and then adding m cancels out when m ≤ n: n - m + m = n.
Finset.exists_subset_card_eq
In any finite set s with n ≤ |s|, there exists a subset of s of cardinality n.
Finset.equivFinOfCardEq
A finite set of cardinality n is in bijection with Fin n.
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Finset.card_erase_of_mem
Erasing an element from a finite set decreases its cardinality by 1 if the element is present: |s.erase a| = |s| - 1.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
Finset.ssubset_iff_subset_ne.mpr
A set s is a strict subset of t if and only if s ⊆ t and s ≠ t.
Finset.erase_subset
Erasing an element from a finite set produces a subset: s.erase a ⊆ s.
Finset.mem_erase
An element x belongs to s.erase b if and only if x ≠ b and x ∈ s.
Finset.notMem_erase
An element does not belong to the set obtained by erasing it: a ∉ s.erase a.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
le_of_eq
Equality implies less-than-or-equal: a = b → a ≤ b.
fan_ramsey_bound_base_one_gen
Every 1-colouring of the subsets of a finite set of size at least j contains a monochromatic copy of F_j.
Finset.mem_filter.mp
If an element belongs to a filtered set, it belongs to the base set and satisfies the filter predicate.
Finset.subset_univ
Every finite set of elements of a finite type α is a subset of Finset.univ.
exists_hitting_set_of_no_large_antichain
If every antichain in a family G of non-empty subsets has size at most w, then G has a hitting set of size at most w.
Finset.card_sdiff_of_subset
If s ⊆ t, the cardinality of the difference t \ s is |t| - |s|.
Finset.card_univ
The cardinality of the universal finset on a finite type α equals the cardinality of α.
Fintype.card_coe
The cardinality of a coerced subtype ↥s equals the cardinality of the finset s.
fan_ramsey_bound_arith
If 1 ≤ k, k(j - 1) + 1 ≤ d, and s ≤ j - 1, then (k - 1)(j - 1) + 1 ≤ d - s.
Function.Embedding.subtype
The canonical inclusion of a subtype into its ambient type is an embedding (an injective map).
Finset.mem_map
An element b belongs to the image Finset.map f s if and only if b = f a for some a ∈ s.
Finset.Nonempty.map
The image of a non-empty finset under an embedding is non-empty.
Finset.mem_univ
Every element of a finite type belongs to its universal finset.
Finset.mem_inter
An element belongs to the intersection of two finsets if and only if it belongs to both.
Finset.mem_sdiff
An element belongs to s \ t if and only if it belongs to s and not to t.
Fintype.card_subtype
The cardinality of a subtype equals the cardinality of the finset of elements satisfying the predicate.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
Fintype.equivFinOfCardEq
A finite type of cardinality n is in bijection with Fin n.
dif_pos
A dependent if-then-else evaluates to its then-branch when the condition holds.
congrArg
Applying a function to equal arguments produces equal results: a₁ = a₂ → f a₁ = f a₂.
Subtype.val
The projection extracting the underlying value from a subtype element.
Finset.not_nonempty_iff_eq_empty
A finset is not non-empty if and only if it is the empty set.
Ne.symm
Inequality is symmetric: a ≠ b → b ≠ a.
Finset.empty_subset
The empty set is a subset of every finset: ∅ ⊆ s.
Finset.Nonempty.mono
If s ⊆ t and s is non-empty, then t is non-empty.
Finset.ssubset_iff_subset_ne.mp
A strict subset inclusion s ⊂ t implies s ⊆ t and s ≠ t.
fan_ramsey_bound_general
For j ≥ 2 and k ≥ 1, every k-colouring of the subsets of a finite set of size at least k(j - 1) + 1 contains a monochromatic copy of F_j.
has_monochromatic_fan_copy
The predicate asserting that a colouring of the subsets of Fin d has a monochromatic top element strictly containing an antichain of size j of the same colour.

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

lemma fan_ramsey_bound_arith (j k d s : ℕ) (hk : 1 ≤ k) (hd : k * (j - 1) + 1 ≤ d) (hs : s ≤ j - 1) :    (k - 1) * (j - 1) + 1 ≤ d - s := by  have h1 : (k - 1) * (j - 1) + (j - 1) = k * (j - 1) := by    calc (k - 1) * (j - 1) + (j - 1) = (k - 1) * (j - 1) + 1 * (j - 1) := by rw [one_mul]      _ = ((k - 1) + 1) * (j - 1) := by rw [Nat.add_mul]      _ = k * (j - 1) := by rw [Nat.sub_add_cancel hk]  omegalemma fan_ramsey_bound_base_one_gen (j : ℕ) {α : Type} [Fintype α] [DecidableEq α]    (hj : 2 ≤ j) (hd : j ≤ Fintype.card α) (χ : Finset α → Fin 1) :    ∃ col : Fin 1, ∃ top : Finset α, χ top = col ∧ ∃ mid : Fin j → Finset α,      (∀ i, mid i ⊂ top ∧ χ (mid i) = col) ∧ ∀ i i', i ≠ i' → ¬ mid i ⊆ mid i' := by  classical  obtain ⟨T, -, hTcard⟩ := Finset.exists_subset_card_eq (s := (Finset.univ : Finset α)) (n := j) (by simpa using hd)  let eT : ↥T ≃ Fin j := Finset.equivFinOfCardEq hTcard  let a : Fin j → α := fun i => (eT.symm i).1  have ha_mem : ∀ i, a i ∈ T := fun i => (eT.symm i).2  have ha_inj : Function.Injective a := by    intro i i' h    exact eT.symm.injective (Subtype.ext h)  let mid : Fin j → Finset α := fun i => T.erase (a i)  have hmid_card : ∀ i, (mid i).card = j - 1 := by    intro i    simp only [mid]    rw [Finset.card_erase_of_mem (ha_mem i), hTcard]  refine ⟨0, T, Subsingleton.elim _ _, mid, ?_, ?_⟩  · intro i    refine ⟨Finset.ssubset_iff_subset_ne.mpr ⟨Finset.erase_subset _ _, ?_⟩, Subsingleton.elim _ _⟩    intro h    have h1 := hmid_card i    rw [h, hTcard] at h1    omega  · intro i i' hii hsub    have hne : mid i ≠ mid i' := by      intro h      have hmem' : a i ∈ mid i' := by        simp only [mid, Finset.mem_erase]        exact ⟨fun heq => hii (ha_inj heq), ha_mem i⟩      rw [← h] at hmem'      exact Finset.notMem_erase (a i) T hmem'    exact hne (Finset.eq_of_subset_of_card_le hsub (le_of_eq (by rw [hmid_card i', hmid_card i])))lemma fan_ramsey_bound_general (j : ℕ) (hj : 2 ≤ j) :    ∀ k, 1 ≤ k → ∀ (α : Type) [Fintype α] [DecidableEq α],      k * (j - 1) + 1 ≤ Fintype.card α →      ∀ χ : Finset α → Fin k, ∃ col : Fin k, ∃ top : Finset α, χ top = col ∧        ∃ mid : Fin j → Finset α, (∀ i, mid i ⊂ top ∧ χ (mid i) = col) ∧          ∀ i i', i ≠ i' → ¬ mid i ⊆ mid i' := by  intro k  induction k with  | zero => intro hk; omega  | succ k ih =>    intro _hk α _instF _instD hcard χ    cases k with    | zero => exact fan_ramsey_bound_base_one_gen j hj (by omega) χ    | succ m =>      have ih' := ih (by omega)      classical      let c : Fin (m + 2) := χ Finset.univ      let G : Finset (Finset α) := Finset.univ.filter (fun A => A.Nonempty ∧ χ A = c)      by_cases hant : ∃ H : Finset (Finset α),          H ⊆ G ∧ (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) ∧ j ≤ H.card      · obtain ⟨H, hHG, hHanti, hjH⟩ := hant        obtain ⟨H', hH'H, hH'card⟩ := Finset.exists_subset_card_eq hjH        have hH'anti : ∀ A ∈ H', ∀ B ∈ H', A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A :=          fun A hA B hB => hHanti A (hH'H hA) B (hH'H hB)        have hH'χ : ∀ A ∈ H', χ A = c :=          fun A hA => (Finset.mem_filter.mp (hHG (hH'H hA))).2.2        let eH : ↥H' ≃ Fin j := Finset.equivFinOfCardEq hH'card        let mid : Fin j → Finset α := fun i => (eH.symm i).1        have hmid_mem : ∀ i, mid i ∈ H' := fun i => (eH.symm i).2        have hmid_inj : Function.Injective mid := by          intro i i' h          exact eH.symm.injective (Subtype.ext h)        have hother : ∀ i : Fin j, ∃ i' : Fin j, i' ≠ i := by          intro i          by_cases h : (⟨0, by omega⟩ : Fin j) = i          · exact ⟨⟨1, by omega⟩, by rw [← h]; simp⟩          · exact ⟨⟨0, by omega⟩, h⟩        refine ⟨c, Finset.univ, rfl, mid, ?_, ?_⟩        · intro i          constructor          · refine Finset.ssubset_iff_subset_ne.mpr ⟨Finset.subset_univ _, ?_⟩            intro h            obtain ⟨i', hi'⟩ := hother i            have hsub : mid i' ⊆ mid i := by rw [h]; exact Finset.subset_univ _            exact (hH'anti (mid i') (hmid_mem i') (mid i) (hmid_mem i)              (fun heq => hi' (hmid_inj heq))).1 hsub          · exact hH'χ (mid i) (hmid_mem i)        · intro i i' hii hsub          exact (hH'anti (mid i) (hmid_mem i) (mid i') (hmid_mem i')            (fun h => hii (hmid_inj h))).1 hsub      · have hbound : ∀ H : Finset (Finset α), H ⊆ G →            (∀ A ∈ H, ∀ B ∈ H, A ≠ B → ¬ A ⊆ B ∧ ¬ B ⊆ A) → H.card ≤ j - 1 := by          intro H hHG hanti          by_contra hcon          push Not at hcon          exact hant ⟨H, hHG, hanti, by omega⟩        have hGne : ∀ A ∈ G, A.Nonempty := fun A hA => (Finset.mem_filter.mp hA).2.1        obtain ⟨S, hScard, hShit⟩ :=          exists_hitting_set_of_no_large_antichain α G (j - 1) hGne hbound        let T : Finset α := Finset.univ \ S        have hTcard : (m + 1) * (j - 1) + 1 ≤ Fintype.card ↥T := by          have hcard' : T.card = Fintype.card α - S.card := by            rw [show T = Finset.univ \ S from rfl, Finset.card_sdiff_of_subset (Finset.subset_univ S),              Finset.card_univ]          rw [Fintype.card_coe, hcard']          exact fan_ramsey_bound_arith j (m + 2) (Fintype.card α) S.card (by omega) hcard hScard        let emb : ↥T ↪ α := Function.Embedding.subtype (· ∈ T)        have hmapT : ∀ A : Finset ↥T, A.map emb ⊆ T := by          intro A x hx          rw [Finset.mem_map] at hx          obtain ⟨y, hy, rfl⟩ := hx          exact y.2        have hne_col : ∀ A : Finset ↥T, A.Nonempty → χ (A.map emb) ≠ c := by          intro A hA hχ          have hBne : (A.map emb).Nonempty := Finset.Nonempty.map (f := emb) hA          have hBG : A.map emb ∈ G := Finset.mem_filter.mpr ⟨Finset.mem_univ _, hBne, hχ⟩          obtain ⟨x, hx⟩ := hShit (A.map emb) hBG          rw [Finset.mem_inter] at hx          have hxT : x ∈ T := hmapT A hx.1          rw [Finset.mem_sdiff] at hxT          exact hxT.2 hx.2        have hcard_sub : Fintype.card {x : Fin (m + 2) // x ≠ c} = m + 1 := by          rw [Fintype.card_subtype]          have hfilter : (Finset.univ.filter (fun x : Fin (m + 2) => x ≠ c)) = Finset.univ.erase c := by            ext x; simp [Finset.mem_erase]          rw [hfilter, Finset.card_erase_of_mem (Finset.mem_univ c), Finset.card_univ, Fintype.card_fin]          omega        let e : {x : Fin (m + 2) // x ≠ c} ≃ Fin (m + 1) := Fintype.equivFinOfCardEq hcard_sub        let lift : Fin (m + 1) → Fin (m + 2) := fun y => (e.symm y).1        let χ' : Finset ↥T → Fin (m + 1) := fun A =>          if h : A.Nonempty then e ⟨χ (A.map emb), hne_col A h⟩ else 0        have hχ'_spec : ∀ (A : Finset ↥T) (hA : A.Nonempty), lift (χ' A) = χ (A.map emb) := by          intro A hA          simp only [χ', dif_pos hA, lift]          exact congrArg Subtype.val (e.symm_apply_apply ⟨χ (A.map emb), hne_col A hA⟩)        obtain ⟨col', top', htop'col, mid', hmid'spec, hmid'anti⟩ := ih' ↥T hTcard χ'        have hmid'_ne : ∀ i, (mid' i).Nonempty := by          intro i          by_contra hcon          rw [Finset.not_nonempty_iff_eq_empty] at hcon          obtain ⟨i', hi'⟩ : ∃ i' : Fin j, i' ≠ i := by            by_cases h : (⟨0, by omega⟩ : Fin j) = i            · exact ⟨⟨1, by omega⟩, by rw [← h]; simp⟩            · exact ⟨⟨0, by omega⟩, h⟩          exact hmid'anti i i' (Ne.symm hi') (by rw [hcon]; exact Finset.empty_subset _)        have htop'_ne : top'.Nonempty :=          Finset.Nonempty.mono            (Finset.ssubset_iff_subset_ne.mp ((hmid'spec (⟨0, by omega⟩ : Fin j)).1)).1            (hmid'_ne _)        refine ⟨lift col', top'.map emb, ?_, fun i => (mid' i).map emb, ?_, ?_⟩        · rw [← hχ'_spec top' htop'_ne, htop'col]        · intro i          constructor          · refine Finset.ssubset_iff_subset_ne.mpr              ⟨Finset.map_subset_map.mpr                (Finset.ssubset_iff_subset_ne.mp ((hmid'spec i).1)).1, ?_⟩            intro h            exact (Finset.ssubset_iff_subset_ne.mp ((hmid'spec i).1)).2 (Finset.map_inj.mp h)          · rw [← hχ'_spec (mid' i) (hmid'_ne i), (hmid'spec i).2]        · intro i i' hii hsub          exact hmid'anti i i' hii (Finset.map_subset_map.mp hsub)/-- Lemma 4 of the paper: the k-colour Ramsey number of the poset F_j (a maximum element over an antichain of size j) is at most k(j-1)+1. -/theorem fan_ramsey_bound (j k d : ℕ) (hj : 2 ≤ j) (hk : 1 ≤ k) (hd : k * (j - 1) + 1 ≤ d)    (χ : Finset (Fin d) → Fin k) : ∃ col : Fin k, has_monochromatic_fan_copy j d col χ := by  have h := fan_ramsey_bound_general j hj k hk (Fin d) (by simpa using hd) χ  simpa [has_monochromatic_fan_copy] using h
See it in the graphDiscuss this resultChallenge it