Lemma 5.6 — fusing two consecutive row parts does not increase the mixed value of C
ProvedTwinWidthI.GridThm.lemma_5_6Let be an matrix over a finite alphabet, a row-division of (every part consists of consecutive rows), and a set of consecutive columns. Let be consecutive parts, i.e. the last row of is immediately followed by the first row of , and let be the row-division obtained by replacing and by . Then the mixed value of does not increase:
where is the number of mixed zones plus the number of mixed cuts of on .
This monotonicity is what lets the greedy fusion procedure of Lemma 5.7 keep the mixed value of every column part under control while fusing row parts.
Formalization Note "Consecutive" is stated as: there are , with , and . is any Finpartition whose parts are those of with replaced by .
import Mathlib import Definitions.Def_TwinWidthI_GridThm_Setting
namespace TwinWidthI.GridThm
/-- Lemma 5.6, p. 3:20: fusing two consecutive parts `X`, `X'` of a row-division `R` into one part
(giving `R'`) does not increase the mixed value of a set `C` of consecutive columns on the
row-division. -/
theorem lemma_5_6 {A : Type*} [Fintype A] {n m : ℕ} (M : Matrix (Fin n) (Fin m) A)
(R R' : Finpartition (Finset.univ : Finset (Fin n))) (hR : IsDivision R)
(C : Finset (Fin m)) (hC : IsIntervalSet C)
(X X' : Finset (Fin n)) (hX : X ∈ R.parts) (hX' : X' ∈ R.parts)
(hcons : ∃ a ∈ X, ∃ b ∈ X', (∀ x ∈ X, x ≤ a) ∧ (∀ y ∈ X', b ≤ y) ∧ (a : ℕ) + 1 = b)
(hR' : R'.parts = insert (X ∪ X') ((R.parts.erase X).erase X')) :
mixedValueRow M R' C ≤ mixedValueRow M R C := by sorry
end TwinWidthI.GridThm
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.