The Setting
Ordered matrix removal compares the density of a fixed induced pattern with the proportion of entries that must change to remove it. A binary matrix of order is a matrix , where .✦ Rows and columns have their own increasing selections.
For nonnegative integers and , an increasing index map from to is a function between these ordered sets that is strictly increasing.✦ For a binary pattern of order and a binary matrix of order , an ordered copy of in is a pair of increasing index maps that matches every entry, including zeros.✦ The set of ordered copies and its cardinality are defined by (1). (1) A binary matrix is -free when its ordered copy count is zero.✦
The Fixed Pattern and Removal Distance
For nonnegative integers , the binary digit is the element of defined in (2). (2)✦ The anchor is the binary matrix of order defined by (3), with row and column indices starting at zero. (3)✦
The fixed forbidden pattern has order . Its anchor occupies the first rows and columns, and its body is the binary matrix of order two in (4). The matrix in that equation has rows and two columns; its column indices are . The first body index is , corresponding to index when indices start at one. (4)✦
The Hamming distance between two binary matrices of the same order is the number of entries in which they differ.✦ For a binary matrix of order , the minimum removal edit count is the least Hamming distance from to an -free binary matrix of order .✦ The normalized removal distance of a binary matrix of positive order is its minimum removal edit count divided by the square of its order, as in (5). (5)
For each integer , use the parameters in (6). (6)
The Claim
Theorem 1. For every integer , there is a binary matrix of order such that (7)✦ For every pair of positive real constants , there are an integer , a real number , and a binary matrix of order such that (8)✦
In the paper, the result reads: there is a fixed binary matrix such that, for every integer , putting and , there is a binary matrix with and , and consequently no positive constants give a polynomial removal bound for this fixed .
What Is Checked
The claims (7) and (8) are stated over finite binary matrices with their row and column orders, the explicit pattern (4), ordered copy counts (1), and the minimum edit distance (5) to an -free matrix.