Functional Equivalence of Twin-Width and Mixed Minor Number
No public endorsements yet.
Loading review…
Sign in with ORCIDAbstract
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✓
Lax49.FunctionalEquivalence - def
Lax49.GraphParameters - def
Lax49.MixedMinorNumber - thm✓
Lax49.MixedMinorNumberFromTwinWidth - thm✓
Lax49.TwinWidthFromMixedMinorNumber
Concept map
Proofs
Proof networkview on GitHub
-
⊢
Lax49Proofs.Main.twin_width_functionally_equivalent_mixed_minor_number -
⊢
Lax49Proofs.MixedMinorNumberFromTwinWidth.exists_mixedMinorNumber_bound_of_twinWidth -
⊢
Lax49Proofs.TwinWidthFromMixedMinorNumber.exists_twinWidth_bound_of_mixedMinorNumber
Lean sources for these proofs: proofs/ on GitHub
Proof code is not displayed; the archive records each proof's checked relationship between claims.
Related submissions
Submission map
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
- É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
- 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