The Setting
The ordered removal problem compares induced containment with the cost of eliminating a pattern by changing entries. Rows and columns have separate orders, and their selections need not coincide. Write for the index set of a matrix of order , with .
The Definition
Definition 1. A binary matrix of order is a function belonging to the set in (1). (1)✦
An increasing index map is a function that preserves strict order, as in (2). (2)✦
For and , an induced ordered copy of in is a pair of increasing row and column maps that matches every entry of , including zeros, as in (3). (3)✦
For and , the ordered copy count is the number of induced ordered copies of in , as in (4). (4)✦
A matrix is -free when it satisfies (5). (5)✦
The Hamming distance between matrices is the number of entries at which they differ, as in (6). (6)✦
The binary digit , for nonnegative integers , is the element of specified by (7). (7)✦
The anchor is the binary matrix of order defined in (8), with . (8)✦
Let be the coordinate unit vectors indexed by , and let . The fixed forbidden pattern is the binary matrix of order in (9), whose lower right body is . (9)✦
The minimum removal edit count of is the minimum Hamming distance to an -free binary matrix, as in (10). (10)✦
The removal distance of is the normalized edit count in (11), with value when . (11)✦
In the paper, the result reads: for a binary pattern of order and a binary matrix of order , an ordered copy selects independently increasing rows and columns with at every cell, including zeros, counts these choices, -freeness means , is the minimum number of arbitrary binary entry changes producing an -free matrix divided by , and the polynomial removal conjecture asks for constants such that, for every integer , every , and every such with , one has .
What Is Checked
The definitions range over square binary matrices of every nonnegative integer size and use the fixed pattern of order for the removal distance.