Lemma 5.5 — a matrix is mixed if and only if it contains a corner
ProvedTwinWidthI.GridThm.lemma_5_5cornermatrixmixed-minorp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1twin-width
Let be an matrix over a finite alphabet. Call mixed if it is neither vertical (all rows equal) nor horizontal (all columns equal), and call a corner any mixed submatrix on two consecutive rows and two consecutive columns. Then
Corners localize mixedness: they play for mixed minors the role that the entries play in the Marcus–Tardos theorem, and they drive Lemma 5.6 and Lemma 5.7.
Formalization Note The whole matrix is the zone univ × univ; IsCorner M i j asserts that rows i, i+1 and columns j, j+1 exist and that the zone they span is mixed. For or both sides are false.
Preamble
import Mathlib import Definitions.Def_TwinWidthI_GridThm_Setting
Formal statement
namespace TwinWidthI.GridThm
/-- Lemma 5.5, p. 3:20: a matrix is mixed if and only if it contains a corner. -/
theorem lemma_5_5 {A : Type*} [Fintype A] {n m : ℕ} (M : Matrix (Fin n) (Fin m) A) :
IsMixed M Finset.univ Finset.univ ↔ ∃ i j, IsCorner M i j := by sorry
end TwinWidthI.GridThm
Source
Bonnet, Kim, Thomassé and Watrigant, Twin-width I: Tractable FO Model Checking, J. ACM 69(1), Article 3 (2021), p. 3:20, Lemma 5.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.