fan_ramsey_bound
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
- 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…
- 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.
- 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…
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.
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.
uses
one_mul,Nat.add_mul,Nat.sub_add_cancelhave 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
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.
uses
Finset.exists_subset_card_eq,Finset.equivFinOfCardEq,Subtype.ext,Finset.card_erase_of_memclassical 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]
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}.
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_eqrefine ⟨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])))
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 ≤ |α|.
uses
fan_ramsey_bound_base_one_genintro 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) χ
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.
| 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)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.
uses
Finset.exists_subset_card_eq,Finset.mem_filter.mp,Finset.equivFinOfCardEq,Subtype.ext,Finset.ssubset_iff_subset_ne.mpr,Finset.subset_univby_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
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.
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
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.
uses
Function.Embedding.subtype,Finset.mem_map,Finset.Nonempty.map,Finset.mem_univ,Finset.mem_inter,Finset.mem_sdifflet 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
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).
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.valhave 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⟩)
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'.
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.mprobtain ⟨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)
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.
uses
fan_ramsey_bound_general,has_monochromatic_fan_copyhave 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.
- The arithmetic helper fan_ramsey_bound_arith is needed formally because subtraction on ℕ is truncated, so bounds involving subtraction like d - s require explicit verification.
- The proof of the inductive step relies on exists_hitting_set_of_no_large_antichain, an external lemma from this knowledge base based on Dilworth's theorem, which guarantees that a family of non-empty sets with no antichain of size j can be pierced by a hitting set of size at most j - 1.
- In the reduction step, the proof explicitly constructs an equivalence between the remaining m + 1 colours and Fin (m + 1) to apply the inductive hypothesis, and maps the resulting fan back into α via the subtype embedding Finset ↥T ↪ Finset α.
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.
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