mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours
Case 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 χ has a monochromatic diamond in one of the a diamond colours or a monochromatic F_j in one of the b fan colours.
Statement
theorem mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours (j a b d : ℕ) (hj : 2 ≤ j)
(ha : 1 ≤ a) (hb : 2 ≤ b) (hd : j * a + (j - 1) * b + 1 ≤ d)
(ih : mixed_ramsey_property j a (b - 1) (d - (j - 1)))
(χ : Finset (Fin d) → Fin (a + b))
(hx : ∀ x : Fin d, ∃ c : Fin b, χ {x} = Fin.natAdd a c) :
(∃ col : Fin a, has_monochromatic_diamond_copy j d (Fin.castAdd b col) χ) ∨
∃ col : Fin b, has_monochromatic_fan_copy j d (Fin.natAdd a col) χ- Source
- step towards mixed_diamond_fan_ramsey_bound
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 14
- 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.
- mdfrbf_compression_boundArithmetic side condition of the compression step: if j ≥ 2, a ≥ 1, b ≥ 2 and j*a + (j-1)*b + 1 ≤ d, then j*a + (j-1)*(b-1) + 1 ≤ d - (j-1).
- mdfrbf_compression_cardIf W is a set of j-1 points of Fin d (j ≥ 2), then the complement of W has exactly d - (j-1) elements, so it can be reindexed by Fin (d -…
- mdfrbf_fibre_subsetPigeonhole: if f : Fin d → Fin b and b*n < d, then some fibre of f contains n+1 points; equivalently there are a colour c and a set W of…
- mdfrbf_compressThe compression map: given a block W ⊆ Fin d, a colouring χ and an excluded colour c, send a set A of points outside W to its image…
- mdfrbf_compress_subset_iffThe compression map is an order embedding: for all sets A, A' of points outside W, T A ⊆ T A' holds if and only if A ⊆ A'. Consequently T…
- mdfrbf_diamond_transferPush-forward of a monochromatic diamond along an order embedding of set systems: if T is injective, monotone and reflects inclusions on…
- mdfrbf_fan_transferPush-forward of a monochromatic fan along an order embedding of set systems: if j ≥ 2, T is injective, monotone and reflects inclusions, χ…
- mdfrbf_colour_injThere is a bijection from Fin (a + (b-1)) onto the colours of Fin (a+b) other than the fan colour Fin.natAdd a c, which fixes the a…
- mdfrbf_fan_of_c_subsetFan witness from a c-coloured block: if W has j-1 points, each of whose singletons is c-coloured, and B is a nonempty c-coloured subset of…
- 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…
- 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…
- 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…
- 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
The proof proceeds by pigeonholing the singletons into a common fan color, followed by a case analysis on whether board compression preserves this fan color. Since the dimension $d$ exceeds $b(j - 2)$, the pigeonhole principle yields a fan color $c$ and a set $W$ of $j - 1$ singletons that all have color $c$. If some nonempty set $A$ disjoint from $W$ compresses to a set of color $c$, then $A$ contains a nonempty monochromatic subset $B$ of color $c$, which together with the $j - 1$ singletons in $W$ forms a monochromatic fan of size $j$ in color $c$. Otherwise, color $c$ is never achieved by nonempty compressed sets, allowing us to eliminate $c$ and pull back the coloring to dimension $d - (j - 1)$ with $b - 1$ fan colors, where the induction hypothesis guarantees a monochromatic diamond or fan that transfers back to dimension $d$.
Each element $x \in \text{Fin } d$ is assigned a fan color $f(x) \in \text{Fin } b$ such that $\chi(\{x\}) = a + f(x)$.
The hypothesis $hx$ states that every singleton $\{x\}$ has a fan color, meaning its color is of the form $a + c$ for some $c \in \text{Fin } b$. Using choice, we define $f : \text{Fin } d \to \text{Fin } b$ selecting this color for each $x$, so $\chi(\{x\}) = a + f(x)$.
classical let f : Fin d → Fin b := fun x => (hx x).choose have hf_spec : ∀ x : Fin d, χ {x} = Fin.natAdd a (f x) := fun x => (hx x).choose_spec
The product $b(j - 2)$ is strictly less than $d$. automation
Using $j - 1 = (j - 2) + 1$, the product $(j - 1)b$ expands to $(j - 2)b + b$ by `Nat.add_mul` and `one_mul`. Since $j \ge 2$ and $a \ge 1$, we have $j a \ge 1$ by `Nat.mul_pos`. Using commutativity of multiplication (`Nat.mul_comm`) and the hypothesis $d \ge j a + (j - 1)b + 1$, linear arithmetic (`omega`) confirms $b(j - 2) < d$.
uses
Nat.add_mul,one_mul,Nat.mul_pos,Nat.mul_commhave hb_gt : b * (j - 2) < d := by have hj1 : j - 1 = (j - 2) + 1 := by omega have hmul : (j - 1) * b = (j - 2) * b + b := by rw [hj1, Nat.add_mul, one_mul] have hja : 1 ≤ j * a := by have h : 0 < j * a := Nat.mul_pos (by omega) (by omega) omega rw [Nat.mul_comm b (j - 2)] omega
There exist a fan color $c \in \text{Fin } b$ and a subset $W \subseteq \text{Fin } d$ of size $j - 1$ such that $\chi(\{w\}) = a + c$ for all $w \in W$.
Applying the pigeonhole principle (`mdfrbf_fibre_subset`) to $f$ with threshold $j - 2$ (valid since $b(j - 2) < d$), we obtain a color $c \in \text{Fin } b$ and a set $W$ of $(j - 2) + 1 = j - 1$ elements on which $f$ takes the constant value $c$. By specification of $f$, every $w \in W$ satisfies $\chi(\{w\}) = a + c$.
uses
mdfrbf_fibre_subsetobtain ⟨c, W, hWcard, hWf⟩ := mdfrbf_fibre_subset f (j - 2) hb_gt have hWcard' : W.card = j - 1 := by omega have hWc : ∀ w ∈ W, χ {w} = Fin.natAdd a c := by intro w hw; rw [hf_spec w, hWf w hw]
It suffices to consider whether there exists a nonempty set $A \subseteq \text{Fin } d \setminus W$ whose compression has color $a + c$.
We perform a case split on whether there exists a nonempty subset $A$ of the remaining elements $\text{Fin } d \setminus W$ whose compressed image $\text{mdfrbf\_compress } W\ \chi\ (a + c)\ A$ has color $a + c$.
by_cases hwin : ∃ A : Finset ↥(Finset.univ \ W), A.Nonempty ∧ χ (mdfrbf_compress W χ (Fin.natAdd a c) A) = Fin.natAdd a cIn the positive case, compression adds $W$ exactly when $A$ contains a nonempty monochromatic subset of color $a + c$, and all subsets of $\text{Fin } d \setminus W$ are disjoint from $W$.
We define the canonical embedding `emb` of $\text{Fin } d \setminus W$ into $\text{Fin } d$ using `Function.Embedding.subtype`. Unfolding `mdfrbf_compress`, we verify via `if_pos` and `if_neg` that compressing $A$ appends $W$ if and only if $A$ contains a nonempty subset $B$ with $\chi(B) = a + c$. Furthermore, using `Finset.mem_sdiff`, `Finset.disjoint_left`, and `Finset.mem_map`, we verify that the image of any subset of $\text{Fin } d \setminus W$ under `emb` is strictly disjoint from $W$.
uses
Function.Embedding.subtype,if_pos,if_neg,Finset.mem_sdiff,Finset.disjoint_left,Finset.mem_map· right set emb : ↥(Finset.univ \ W) ↪ Fin d := Function.Embedding.subtype fun x => x ∈ Finset.univ \ W with hemb have hdef : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb ∪ (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c) then W else ∅) := by intro A unfold mdfrbf_compress simp only [← hemb] by_cases h : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c) · rw [if_pos h, if_pos h] · rw [if_neg h, if_neg h]; simp have hnotW : ∀ x : ↥(Finset.univ \ W), (emb x : Fin d) ∉ W := by intro x hx' have hx2 : (x : Fin d) ∈ Finset.univ \ W := x.2 rw [Finset.mem_sdiff] at hx2 have hv : (emb x : Fin d) = (x : Fin d) := rfl rw [hv] at hx' exact hx2.2 hx' have hdisj : ∀ A : Finset ↥(Finset.univ \ W), Disjoint (A.map emb) W := by intro A rw [Finset.disjoint_left] intro y hy hyW rw [Finset.mem_map] at hy obtain ⟨x, -, rfl⟩ := hy exact hnotW x hyW
The winning set $A$ contains a nonempty subset $B \subseteq A$ with $\chi(B) = a + c$, and the compressed set equals $A \cup W$.
From the case hypothesis, we obtain a nonempty set $A$ whose compression has color $a + c$. If $A$ contained no nonempty subset of color $a + c$, its compression would simply be $A$ itself (by `if_neg`), which leads to a contradiction since $A \subseteq A$ by `le_rfl`. Thus such a nonempty $B \subseteq A$ exists with $\chi(B) = a + c$, and by `if_pos`, the compressed set is indeed $A \cup W$.
uses
if_neg,le_rfl,if_posobtain ⟨A, hAne, hAcol⟩ := hwin have hH : A.Nonempty ∧ ∃ B, B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c := by by_contra hcon have hT : mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb := by rw [hdef A, if_neg hcon] simp exact hcon ⟨hAne, A, hAne, le_rfl, by rw [← hT]; exact hAcol⟩ obtain ⟨B, hBne, hBsub, hBcol⟩ := hH.2 have hT_union : mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb ∪ W := by rw [hdef A, if_pos hH]
The coloring $\chi$ contains a monochromatic fan copy of size $j$ in fan color $c$.
We assemble a monochromatic fan in color $c$ using `mdfrbf_fan_of_c_subset`. The top element is the compressed set $A \cup W$, which has color $a + c$. It contains $W$ by `Finset.subset_union_right`, and all $j - 1$ elements of $W$ form singletons of color $a + c$. Furthermore, $B$ is a nonempty subset of $A \cup W$ by `Finset.map_subset_map.mpr` and `Finset.subset_union_left`, has color $a + c$, and is disjoint from $W$. Together, the $j - 1$ singletons from $W$ and the subset $B$ provide $j$ incomparable sub-elements colored $a + c$ below the top set, completing the fan.
uses
mdfrbf_fan_of_c_subset,Finset.subset_union_right,Finset.map_subset_map.mpr,Finset.subset_union_leftrefine ⟨c, mdfrbf_fan_of_c_subset hj W hWcard' χ (Fin.natAdd a c) _ (B.map emb) hAcol ?_ hWc ?_ ?_ hBcol ?_⟩ · rw [hT_union]; exact Finset.subset_union_right · exact hBne.map (f := emb) · rw [hT_union]; exact (Finset.map_subset_map.mpr hBsub).trans Finset.subset_union_left · exact hdisj B
In the negative case, color $a + c$ is never achieved on any nonempty compressed set, yielding an injective re-indexing $f_0$ of the remaining $a + (b - 1)$ colors.
Since no nonempty set compresses to color $a + c$, all nonempty compressed sets avoid color $a + c$. By `mdfrbf_colour_inj`, there exists an injection $f_0 : \text{Fin }(a + (b - 1)) \to \text{Fin }(a + b)$ whose image avoids $a + c$, fixes the $a$ diamond colors, and maps the remaining $b - 1$ fan colors to fan colors in $\text{Fin } b$.
uses
mdfrbf_colour_inj· have hnowin : ∀ A : Finset ↥(Finset.univ \ W), A.Nonempty → χ (mdfrbf_compress W χ (Fin.natAdd a c) A) ≠ Fin.natAdd a c := by intro A hA hcontra exact hwin ⟨A, hA, hcontra⟩ obtain ⟨f0, hf0_inj, hf0_surj, hf0_cast, hf0_nat, hf0_ne⟩ := mdfrbf_colour_inj a b ha hb c
The complement $\text{Fin } d \setminus W$ has cardinality $K = d - (j - 1)$, and identifying it with $\text{Fin } K$ gives an inclusion-preserving compression map $T'$.
By `mdfrbf_compression_card`, the complement of $W$ has size $K = d - (j - 1)$. We identify $\text{Fin } K$ with $\text{Fin } d \setminus W$ via a bijection `e` given by `Fintype.equivOfCardEq` and `Fintype.card_fin`. Defining $T'(A)$ as the compression of $e(A)$, the lemma `mdfrbf_compress_subset_iff` together with `Finset.map_subset_map` shows that $T'$ is strictly inclusion-preserving ($T'(A) \subseteq T'(A') \iff A \subseteq A'$).
uses
mdfrbf_compression_card,Fintype.equivOfCardEq,Fintype.card_fin,mdfrbf_compress_subset_iff,Finset.map_subset_maplet K := d - (j - 1) have hKcard : Fintype.card ↥(Finset.univ \ W) = K := mdfrbf_compression_card j d hj W hWcard' let e : Fin K ≃ ↥(Finset.univ \ W) := Fintype.equivOfCardEq (by rw [Fintype.card_fin]; exact hKcard.symm) let T' : Finset (Fin K) → Finset (Fin d) := fun A => mdfrbf_compress W χ (Fin.natAdd a c) (A.map e.toEmbedding) have hT' : ∀ A A' : Finset (Fin K), T' A ⊆ T' A' ↔ A ⊆ A' := by intro A A' simp only [T'] rw [mdfrbf_compress_subset_iff] exact Finset.map_subset_map
There is a reduced coloring $\psi'$ on subsets of $\text{Fin } K$ using $a + (b - 1)$ colors such that $\chi(T'(B)) = f_0(\psi'(B))$ for every nonempty $B$.
For each nonempty $B \subseteq \text{Fin } K$, since $\chi(T'(B)) \ne a + c$, the surjectivity property of $f_0$ guarantees a unique pre-image under $f_0$. For the empty set, we assign an arbitrary fan color $a + c_0$. Using `dif_pos` and `Classical.choose_spec`, we verify that $\chi(T'(B)) = f_0(\psi'(B))$ holds for every nonempty $B$.
uses
dif_pos,Classical.choose_speclet c₀ : Fin (b - 1) := ⟨0, by omega⟩ let ψ' : Finset (Fin K) → Fin (a + (b - 1)) := fun B => if h : B.Nonempty then Classical.choose (hf0_surj (χ (T' B)) (hnowin (B.map e.toEmbedding) (h.map (f := e.toEmbedding)))) else Fin.natAdd a c₀ have hpoint : ∀ B : Finset (Fin K), B.Nonempty → χ (T' B) = f0 (ψ' B) := by intro B hB have hex : ∃ u : Fin (a + (b - 1)), f0 u = χ (T' B) := hf0_surj (χ (T' B)) (hnowin (B.map e.toEmbedding) (hB.map (f := e.toEmbedding))) have hψ : ψ' B = Classical.choose hex := by simp only [ψ'] rw [dif_pos hB] rw [hψ] exact (Classical.choose_spec hex).symm
The empty set is not assigned any diamond color under $\psi'$. automation
By definition of $\psi'$, since $\emptyset$ is not nonempty (`Finset.not_nonempty_empty`), by `dif_neg` $\psi'(\emptyset)$ equals the fan color $a + c_0$. Numerical evaluation via `Fin.val_natAdd` and `Fin.val_castAdd` shows that its index is at least $a$, whereas any diamond color has index strictly less than $a$. Linear arithmetic (`omega`) confirms that $\psi'(\emptyset)$ cannot equal any diamond color.
uses
dif_neg,Finset.not_nonempty_empty,Fin.val_natAdd,Fin.val_castAddhave hempty : ∀ col : Fin a, ψ' ∅ ≠ Fin.castAdd (b - 1) col := by intro col simp only [ψ'] rw [dif_neg (Finset.not_nonempty_empty)] intro h have hv : (Fin.natAdd a c₀).val = (Fin.castAdd (b - 1) col).val := by rw [h] simp only [Fin.val_natAdd, Fin.val_castAdd] at hv have := col.isLt omega
Either $\chi$ has a monochromatic diamond copy in one of the $a$ diamond colors, or $\chi$ has a monochromatic fan copy in one of the $b$ fan colors.
By the induction hypothesis `ih` applied to the coloring $\psi'$ on $\text{Fin } K$, there is either a monochromatic diamond in a diamond color or a monochromatic fan in a fan color. In the diamond case, because $\psi'(\emptyset)$ is not a diamond color, `mdfrbf_diamond_transfer` pulls the diamond forward along $T'$ and $f_0$ to dimension $d$. In the fan case, `mdfrbf_fan_transfer` pulls the fan forward to dimension $d$. In both cases, this establishes the required monochromatic structure for $\chi$.
uses
mdfrbf_diamond_transfer,mdfrbf_fan_transferrcases ih ψ' with ⟨col, hcopy⟩ | ⟨col, hcopy⟩ · left have htr := mdfrbf_diamond_transfer f0 T' hT' χ ψ' hpoint (Fin.castAdd (b - 1) col) (hempty col) hcopy rw [hf0_cast col] at htr exact ⟨col, htr⟩ · right have htr := mdfrbf_fan_transfer hj f0 T' hT' χ ψ' hpoint (Fin.natAdd a col) hcopy obtain ⟨col', hcol'⟩ := hf0_nat col rw [hcol'] at htr exact ⟨col', htr⟩
Classical.choose_spec- given an existential proof $\exists x, p(x)$, the chosen witness satisfies $p$
Fin.val_castAdd- the numerical value of $\text{Fin.castAdd } m\ i$ is $i$
Fin.val_natAdd- the numerical value of $\text{Fin.natAdd } n\ i$ is $n + i$
Finset.disjoint_left- two finite sets are disjoint if and only if no element of the first belongs to the second
Finset.map_subset_map- mapping along an embedding preserves and reflects subset inclusion between finite sets
Finset.map_subset_map.mpr- if $s_1 \subseteq s_2$, then mapping both sets along an embedding preserves the subset relation
Finset.mem_map- an element $b$ is in the mapped set $\text{Finset.map } f\ s$ if and only if $b = f(a)$ for some $a \in s$
Finset.mem_sdiff- an element belongs to the set difference $s \setminus t$ if and only if it belongs to $s$ and not to $t$
Finset.not_nonempty_empty- the empty set is not nonempty
Finset.subset_union_left- any set $s_1$ is a subset of the union $s_1 \cup s_2$
Finset.subset_union_right- any set $s_2$ is a subset of the union $s_1 \cup s_2$
Fintype.card_fin- the cardinality of the finite type $\text{Fin } n$ is $n$
Fintype.equivOfCardEq- two finite types with equal cardinality are isomorphic
Function.Embedding.subtype- the canonical embedding of a subtype into its ambient type
Nat.add_mul- multiplication distributes over addition on the right: $(n + m) \times k = n \times k + m \times k$
Nat.mul_comm- multiplication of natural numbers is commutative: $n \times m = m \times n$
Nat.mul_pos- the product of two strictly positive natural numbers is strictly positive
dif_neg- dependent if-then-else evaluates to the else branch when the condition is false
dif_pos- dependent if-then-else evaluates to the then branch when the condition holds
if_neg- if a condition is false, the if-then-else expression evaluates to the else branch
if_pos- if a condition holds, the if-then-else expression evaluates to the then branch
le_rfl- the partial order relation $\le$ is reflexive: $a \le a$
mdfrbf_colour_inj- there exists an injection from $\text{Fin }(a + (b - 1))$ to $\text{Fin }(a + b)$ that avoids the fan color $c$, preserves diamond colors, and maps fan colors to fan colors
mdfrbf_compress_subset_iff- the compression map preserves and reflects subset inclusion between sets: $\text{mdfrbf\_compress } W\ \chi\ c\ A \subseteq \text{mdfrbf\_compress } W\ \chi\ c\ A' \iff A \subseteq A'$
mdfrbf_compression_card- the complement of a subset $W$ of cardinality $j - 1$ in a board of dimension $d$ has cardinality $d - (j - 1)$
mdfrbf_diamond_transfer- a monochromatic diamond copy transfers from a smaller board under an inclusion-preserving embedding, provided $\psi(\emptyset)$ is not the diamond color
mdfrbf_fan_of_c_subset- a top set of color $c$ containing a set $W$ of $j - 1$ singletons of color $c$ and a disjoint nonempty set $B$ of color $c$ contains a monochromatic fan of size $j$ in color $c$
mdfrbf_fan_transfer- a monochromatic fan copy transfers from a smaller board under an inclusion-preserving embedding
mdfrbf_fibre_subset- if $b \times n < d$, any function $f : \text{Fin } d \to \text{Fin } b$ has a fiber containing a subset of size $n + 1$ on which $f$ is constant
one_mul- one is the left identity for multiplication: $1 \times a = a$
- The tactic `omega` discharges linear integer arithmetic goals automatically (such as verifying $b(j - 2) < d$ and that $\psi'(\emptyset)$ cannot equal any diamond color).
- The proof freely relies on classical choice (`Classical.choose`) to noncomputably define the color choice function $f$ and pre-images under the injection $f_0$.
- The board compression `mdfrbf_compress` is a formal construction that adds $W$ to a set $A$ if and only if $A$ contains a monochromatic subset of color $c$, ensuring that in the second case color $c$ never appears on nonempty sets.
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.
/-- b ≥ 2 step with all singletons fan-coloured: pigeonhole a colour c on j-1 singletons, compress away that set W, and apply the (a, b-1) instance; a c-coloured set inside the compressed board is already a fan in colour c. -/theorem mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours (j a b d : ℕ) (hj : 2 ≤ j) (ha : 1 ≤ a) (hb : 2 ≤ b) (hd : j * a + (j - 1) * b + 1 ≤ d) (ih : mixed_ramsey_property j a (b - 1) (d - (j - 1))) (χ : Finset (Fin d) → Fin (a + b)) (hx : ∀ x : Fin d, ∃ c : Fin b, χ {x} = Fin.natAdd a c) : (∃ col : Fin a, has_monochromatic_diamond_copy j d (Fin.castAdd b col) χ) ∨ ∃ col : Fin b, has_monochromatic_fan_copy j d (Fin.natAdd a col) χ := by classical let f : Fin d → Fin b := fun x => (hx x).choose have hf_spec : ∀ x : Fin d, χ {x} = Fin.natAdd a (f x) := fun x => (hx x).choose_spec have hb_gt : b * (j - 2) < d := by have hj1 : j - 1 = (j - 2) + 1 := by omega have hmul : (j - 1) * b = (j - 2) * b + b := by rw [hj1, Nat.add_mul, one_mul] have hja : 1 ≤ j * a := by have h : 0 < j * a := Nat.mul_pos (by omega) (by omega) omega rw [Nat.mul_comm b (j - 2)] omega obtain ⟨c, W, hWcard, hWf⟩ := mdfrbf_fibre_subset f (j - 2) hb_gt have hWcard' : W.card = j - 1 := by omega have hWc : ∀ w ∈ W, χ {w} = Fin.natAdd a c := by intro w hw; rw [hf_spec w, hWf w hw] by_cases hwin : ∃ A : Finset ↥(Finset.univ \ W), A.Nonempty ∧ χ (mdfrbf_compress W χ (Fin.natAdd a c) A) = Fin.natAdd a c · right set emb : ↥(Finset.univ \ W) ↪ Fin d := Function.Embedding.subtype fun x => x ∈ Finset.univ \ W with hemb have hdef : ∀ A : Finset ↥(Finset.univ \ W), mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb ∪ (if (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c) then W else ∅) := by intro A unfold mdfrbf_compress simp only [← hemb] by_cases h : (A.Nonempty ∧ ∃ B : Finset ↥(Finset.univ \ W), B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c) · rw [if_pos h, if_pos h] · rw [if_neg h, if_neg h]; simp have hnotW : ∀ x : ↥(Finset.univ \ W), (emb x : Fin d) ∉ W := by intro x hx' have hx2 : (x : Fin d) ∈ Finset.univ \ W := x.2 rw [Finset.mem_sdiff] at hx2 have hv : (emb x : Fin d) = (x : Fin d) := rfl rw [hv] at hx' exact hx2.2 hx' have hdisj : ∀ A : Finset ↥(Finset.univ \ W), Disjoint (A.map emb) W := by intro A rw [Finset.disjoint_left] intro y hy hyW rw [Finset.mem_map] at hy obtain ⟨x, -, rfl⟩ := hy exact hnotW x hyW obtain ⟨A, hAne, hAcol⟩ := hwin have hH : A.Nonempty ∧ ∃ B, B.Nonempty ∧ B ⊆ A ∧ χ (B.map emb) = Fin.natAdd a c := by by_contra hcon have hT : mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb := by rw [hdef A, if_neg hcon] simp exact hcon ⟨hAne, A, hAne, le_rfl, by rw [← hT]; exact hAcol⟩ obtain ⟨B, hBne, hBsub, hBcol⟩ := hH.2 have hT_union : mdfrbf_compress W χ (Fin.natAdd a c) A = A.map emb ∪ W := by rw [hdef A, if_pos hH] refine ⟨c, mdfrbf_fan_of_c_subset hj W hWcard' χ (Fin.natAdd a c) _ (B.map emb) hAcol ?_ hWc ?_ ?_ hBcol ?_⟩ · rw [hT_union]; exact Finset.subset_union_right · exact hBne.map (f := emb) · rw [hT_union]; exact (Finset.map_subset_map.mpr hBsub).trans Finset.subset_union_left · exact hdisj B · have hnowin : ∀ A : Finset ↥(Finset.univ \ W), A.Nonempty → χ (mdfrbf_compress W χ (Fin.natAdd a c) A) ≠ Fin.natAdd a c := by intro A hA hcontra exact hwin ⟨A, hA, hcontra⟩ obtain ⟨f0, hf0_inj, hf0_surj, hf0_cast, hf0_nat, hf0_ne⟩ := mdfrbf_colour_inj a b ha hb c let K := d - (j - 1) have hKcard : Fintype.card ↥(Finset.univ \ W) = K := mdfrbf_compression_card j d hj W hWcard' let e : Fin K ≃ ↥(Finset.univ \ W) := Fintype.equivOfCardEq (by rw [Fintype.card_fin]; exact hKcard.symm) let T' : Finset (Fin K) → Finset (Fin d) := fun A => mdfrbf_compress W χ (Fin.natAdd a c) (A.map e.toEmbedding) have hT' : ∀ A A' : Finset (Fin K), T' A ⊆ T' A' ↔ A ⊆ A' := by intro A A' simp only [T'] rw [mdfrbf_compress_subset_iff] exact Finset.map_subset_map let c₀ : Fin (b - 1) := ⟨0, by omega⟩ let ψ' : Finset (Fin K) → Fin (a + (b - 1)) := fun B => if h : B.Nonempty then Classical.choose (hf0_surj (χ (T' B)) (hnowin (B.map e.toEmbedding) (h.map (f := e.toEmbedding)))) else Fin.natAdd a c₀ have hpoint : ∀ B : Finset (Fin K), B.Nonempty → χ (T' B) = f0 (ψ' B) := by intro B hB have hex : ∃ u : Fin (a + (b - 1)), f0 u = χ (T' B) := hf0_surj (χ (T' B)) (hnowin (B.map e.toEmbedding) (hB.map (f := e.toEmbedding))) have hψ : ψ' B = Classical.choose hex := by simp only [ψ'] rw [dif_pos hB] rw [hψ] exact (Classical.choose_spec hex).symm have hempty : ∀ col : Fin a, ψ' ∅ ≠ Fin.castAdd (b - 1) col := by intro col simp only [ψ'] rw [dif_neg (Finset.not_nonempty_empty)] intro h have hv : (Fin.natAdd a c₀).val = (Fin.castAdd (b - 1) col).val := by rw [h] simp only [Fin.val_natAdd, Fin.val_castAdd] at hv have := col.isLt omega rcases ih ψ' with ⟨col, hcopy⟩ | ⟨col, hcopy⟩ · left have htr := mdfrbf_diamond_transfer f0 T' hT' χ ψ' hpoint (Fin.castAdd (b - 1) col) (hempty col) hcopy rw [hf0_cast col] at htr exact ⟨col, htr⟩ · right have htr := mdfrbf_fan_transfer hj f0 T' hT' χ ψ' hpoint (Fin.natAdd a col) hcopy obtain ⟨col', hcol'⟩ := hf0_nat col rw [hcol'] at htr exact ⟨col', htr⟩