Polynomial removal for the ordered two-by-two identity matrix
For a binary n×n matrix A, let N(A) count induced ordered copies of the two-by-two identity matrix, and let D(A) be the minimum number of entry changes needed to eliminate them. We prove that absolute constants c,C > 0 satisfy D(A) ≥ ε n² ⇒ N(A) ≥ c ε^C n⁴. This resolves the identity case highlighted as open by Gishboliner and Shapira in 2025 (Section 4.2). For binary hosts of algebraic rank at most r over any field, we prove N(A) ≥ 2^(−6r−2) D(A)², with optimal exponent two for each fixed r ≥ 2. The unrestricted proof combines compatible repair of row blocks with triangular markers and a removal theorem for families closed under row permutations. The block method also gives a short-row-span repair estimate, while an elementary construction forces any uniform unrestricted removal exponent to be at least three. Further results treat rectangular hosts and product row–column measures, finite-type hosts over finite alphabets, small entry perturbations, and larger identities at bounded rank. Combining Shea’s qualitative obstruction with an exact distance-preserving padding lemma gives the identity dichotomy: unrestricted ordered binary identities admit polynomial removal exactly in sizes one and two. GitHub repository
Authors
- Martino Lupini (ORCID: https://orcid.org/0000-0003-1588-7057)
Institutions
- University of Bologna (IT)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-02
- DOI
- https://doi.org/10.5281/zenodo.23618366
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint