For a binary pattern and a binary matrix , an induced ordered copy of is a choice of increasing row indices and increasing column indices whose entries agree with , including both zeros and ones. The number of these copies is denoted by . A matrix is -free if . The normalized removal distance is the minimum fraction of entries that must be changed, allowing changes in either direction, to make -free. The polynomial ordered binary matrix-removal conjecture asserts that each fixed admits constants such that, whenever , and , one has .
Alon and Ben-Eliezer formulated the polynomial removal question for finite families of binary matrices. The singleton conjecture appears as Conjecture 4.5 in the first arXiv version of Gishboliner and Shapira’s survey.
For integers , write . Write . The preprint constructs a fixed binary pattern and binary matrices satisfying and for every . For this , no positive constants give a polynomial removal bound. The preprint also derives an exponential lower bound in for the number of rows and columns sampled independently and uniformly by testers that reject only when the sampled submatrix contains , at any fixed positive rejection probability along this sequence; the Lean library does not contain this sampling consequence.
Lean has checked every result of the Lean library MatrixRemoval, so the Lean library is the reference for the statements on these pages. Each result is stated as in the Lean library and linked to its Lean declaration. Where the preprint states a result differently, the preprint’s statement is given beside the Lean library’s statement. The preprint guides only the order and names of the results.
MatrixRemoval is a Lean library: 12 items, in four groups. Each has a page written by OctoInform, listed below.
No item matches.