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

Institutions

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Polynomial removal for the ordered two-by-two identity matrix

Martino Lupini
3 links
Zenodo (CERN European Organization for Nuclear Research)
Limits and Structures in Graph Theory
preprint

Polynomial removal for the ordered two-by-two identity matrix

Martino Lupini
preprint en

Abstract

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

Zenodo (CERN European Organization for Nuclear Research)
University of Bologna (IT)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon
Polynomial removal for the ordered two-by-two identity matrix — Martino Lupini · Zenodo (CERN European Organization for Nuclear Research) (2026) | TGRS Research Map | TGRS