Functional Equivalence of Twin-Width and Mixed Minor Number

lax-49·formalized by Édouard Bonnet @EdouardBonnet·Claude Fable 5 (Anthropic)·Codex (OpenAI)·registered·created 2026-08-07·GitHub @688029c·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Sign in with ORCID

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    This submission gives a full Lean proof that finite-graph twin-width and mixed minor number are functionally equivalent: each parameter is bounded by a numerical function of the other.

    The concept surface has five review units. Two are definitions: the complete definition of mixed minor number — interval divisions, mixed matrix cells, mixed minors, and vertex-ordered adjacency matrices — phrased with plain structures and Prop-valued predicates and with the parameter an infimum of an explicit set of naturals; and the uniform signature of a graph parameter together with the functional equivalence relation over it. Three are claims: the two directional bounds, each stated on its own over the twin-width parameter of submission Lax48 and the mixed minor number, and the headline equivalence, which applies the equivalence relation to the two parameters directly. Each direction has its own literature proof and is independently usable; the equivalence follows from the two by definition.

    The proof runs through the Marcus–Tardos theorem, the matrix grid-minor theorem, and the graph twin-decomposition bridge; both submitted parameters are proved pointwise equal to their source counterparts, via the black-is-complete / red-is-non-homogeneous invariant for contraction sequences and a pointwise division-and-cell translation for mixed minors. The mixed-minor-to-twin-width direction is transported from the mirrored Theorem 14 construction, the twin-width-to-mixed direction from the leaf-order twin-decomposition, and the headline equivalence is assembled from the two directional statements alone.

    Concepts

    thm✓proven claimdefdefinition

    Concept map

    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    assumptions conclusionProven claimThis submissionProof — click to open

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    @misc{lax-49,
      author = {Édouard Bonnet and Claude Fable 5 (Anthropic) and Codex (OpenAI)},
      title = {Functional Equivalence of Twin-Width and Mixed Minor Number},
      year = {2026},
      howpublished = {Lax Archive, lax-49},
      url = {https://laxarchive.org/lax-49/},
    }

    References

    1. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant. Twin-width I: Tractable FO Model Checking. Journal of the ACM 69(1):3:1–3:46, 2022. doi:10.1145/3486655
    2. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. Journal of Combinatorial Theory, Series A 107(1):153–160, 2004. doi:10.1016/j.jcta.2004.04.002

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…