AFTD Auto-Formalizing Theoretical Domains

mixed_diamond_fan_ramsey_bound_all_singletons_fan_colours

theoremverified

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

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

    lines 9–11

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

    lines 12–19

    uses Nat.add_mul, one_mul, Nat.mul_pos, Nat.mul_comm

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

    lines 20–23

    uses mdfrbf_fibre_subset

      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]
  4. 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$.

    line 24

      by_cases hwin : ∃ A : Finset ↥(Finset.univ \ W), A.Nonempty ∧ χ (mdfrbf_compress W χ (Fin.natAdd a c) A) = Fin.natAdd a c
  5. In 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$.

    lines 25–48

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

    lines 49–58

    uses if_neg, le_rfl, if_pos

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

    lines 59–63

    uses mdfrbf_fan_of_c_subset, Finset.subset_union_right, Finset.map_subset_map.mpr, Finset.subset_union_left

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

    lines 64–67

    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
  9. 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'$).

    lines 68–77

    uses mdfrbf_compression_card, Fintype.equivOfCardEq, Fintype.card_fin, mdfrbf_compress_subset_iff, Finset.map_subset_map

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

    lines 78–91

    uses dif_pos, Classical.choose_spec

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

    lines 92–100

    uses dif_neg, Finset.not_nonempty_empty, Fin.val_natAdd, Fin.val_castAdd

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

    lines 101–110

    uses mdfrbf_diamond_transfer, mdfrbf_fan_transfer

        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⟩
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$

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

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