Each chain changes the labeling at most twice.
ProvedGeometry.PosetTwinWidth.FinitePoset.labelChanges_le_twoaether-cataloggeometry
Each chain changes the labeling at most twice. Along a list sorted in
ascending poset order, the trichotomy labeling relative to any fixed reference
vertex w follows the monotone pattern blue … green … red, so it changes value
at most twice. This is the per-chain core of the twin-width ≤ 2k bound.
theorem Geometry.PosetTwinWidth.FinitePoset.labelChanges_le_two(w : P.carrier) (l : List P.carrier)
(hsorted : l.Pairwise (fun a b => P.le a b)) :
labelChanges (P.label w) l ≤ 2 := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Geometry/PosetTwinWidth/LinearBound.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Geometry/PosetTwinWidth/LinearBound.lean import Mathlib import Definitions.Def_Geometry_Contractions import Definitions.Def_Geometry_PosetTheory_NonCircular import Definitions.Def_Geometry_PosetTwinWidth_LinearBound /- Copyright (c) 2025 Harmonic. All rights reserved. Released under Apache 2.0 license as described in the file LICENSE. Authors: Aristotle (Harmonic) -/ /-! # A linear contraction sequence for finite posets of bounded width ## Strategy For a finite poset `P` we build a **contraction sequence** — a list of "merge" operations on the vertices that, applied in order, identify all vertices into a single super-vertex. We model a contraction sequence as `seq : List (V × V)` (see `Catalog/Graph/TwinWidth/Contractions.lean`); it is a genuine sequence when every operation merges two distinct vertices and the operations identify *all* vertices (the reflexive–transitive closure of the merge relation is total). The construction proceeds in two reusable steps: 1. **Order the vertices without self-reference.** Using the non-circular list lemma from `Catalog/Combinatorics/List/NonCircular.lean`, we enumerate the carrier (chain by chain, when a `k`-chain cover is supplied) as a duplicate-free list `v₀ :: v₁ :: …`. Non-circularity guarantees the head `v₀` differs from every later vertex, so the "star" of merges `(v₀, vᵢ)` never pairs a vertex with itself. 2. **Contract along that order.** We invoke the generic `Graph.TwinWidth.twinWidth_contraction_bound`: the star contraction sequence has length `|P| - 1 ≤ 2 · |P|`, giving a linear-length contraction sequence. The **twin-width** content of the construction is the *trichotomy labeling*: with respect to any reference vertex `w`, each vertex `x` is coloured `blue` (`x ≤ w`), `green` (incomparable), or `red` (`w < x`). Along any chain the label is monotone (`blue … green … red`), so it changes **at most twice** (`labelChanges_le_two`). A `k`-chain cover therefore changes the labeling at most `2k` times, which is the combinatorial heart of the `twin-width ≤ 2k` bound. ## Main results * `FinitePoset.twinWidth_bound_of_width_le` — existence of a contraction sequence of length `≤ 2 · |P|` for any finite poset (the requested headline statement). * `FinitePoset.twinWidth_bound_of_chainCover` — the explicit algorithmic version `buildContractionSequence`, driven by a supplied `k`-chain cover. * `FinitePoset.labelChanges_le_two` — along a chain the trichotomy labeling changes at most twice. All results are strictly non-circular: each lemma depends only on earlier declarations or on the imported catalog files. -/ -- open removed: section is not a namespace open Geometry.PosetTwinWidth attribute [instance] FinitePoset.ftype FinitePoset.deq FinitePoset.dle open FinitePoset variable (P : FinitePoset) /-! ### Trichotomy labeling -/ /-! ### Chain covers -/ /-! ### The contraction sequence predicate -/ /-! ### The construction -/ /-! ### Properties of the chain ordering -/ /-! ### The trichotomy labeling changes at most twice along a chain -/
Formal statement
theorem Geometry.PosetTwinWidth.FinitePoset.labelChanges_le_two(w : P.carrier) (l : List P.carrier)
(hsorted : l.Pairwise (fun a b => P.le a b)) :
labelChanges (P.label w) l ≤ 2 := by sorrySource