The Setting
An ordered induced copy chooses its rows and columns independently, preserving their orders and matching every entry, including zeros.✦ The distinguished cell here is the first entry of the two by two body attached to a fixed anchor.
Write for a nonnegative integer . A binary matrix of order is a function from to .✦ The anchor is the binary matrix of order defined in (1), where denotes the indicator of a condition and is the binary digit specified there. (1)
The fixed pattern is the binary matrix of order with anchor , body , and the two attachment blocks given in (2); the matrix has row set and column set . (2)✦ Its first body index is , corresponding to index in the paper.
An increasing index map is a strictly increasing function.✦ For a binary matrix of order , an ordered copy of in is a pair of strictly increasing maps from to satisfying the condition in (3); is the number of these copies. (3)
The Host and Its Orders
For ordered sets , a frame position is an element of the disjoint union of , and , called an anchor triple, a variable or a dummy, respectively.✦ Anchor triples have lexicographic order, first by mode, then group, then offset.✦ The row frame order places variables after anchors and dummies last✦; the column frame order places dummies after anchors and variables last.✦ The row coordinate map sends each frame position to the corresponding element of the ordered disjoint union of anchors, variables and dummies, and the column coordinate map sends each frame position to the corresponding element of the ordered disjoint union of anchors, dummies and variables; the frame orders are inherited from these maps.
For height , put , and .✦ The modes are the indices ✦, and the variable positions are pairs in . The host position set is the frame with these modes, these variables and dummy set .✦ A mode’s type and level , and a variable’s depth and node , are defined by (4). (4) The sign is positive for even and negative for odd .✦ For a level , a sign and a parity , the signed level class is the subset of consisting of variables at depth with sign , with no sign restriction when , and is the subset of consisting of variables with node parity , as specified in (5). (5) The shared leaf , for , is the variable position viewed as a host position.✦
A tree order coordinate is a tuple of five natural numbers, compared lexicographically in the written order.✦ For axis on rows and on columns, the tree traversal key is defined by (6), with , , and . Its cases are the leaf, subtree entry and subtree exit keys, respectively. (6)✦ The variable position order on each axis is the order inherited from its traversal key.✦ Let and be the increasing row and column enumerations, respectively, chosen separately.
The row roles and column roles are the subsets of nonanchor positions in (7), where and . (7)
Write for and for . For variable positions , the variable matrix entry is the binary value in (8); here and . (8)✦
The raw host matrix is the binary function on given in (9). In its second and third cases and are nonanchor positions, and the role indicator is zero for group indices outside . (9)✦ The enumerated host is the binary matrix defined by (10). The sets and denote its singleton row and column leaf classes. (10)✦
The Claim
Theorem 1. Let be a nonnegative integer. Let be strictly increasing in the row and column orders, respectively, and suppose that for every . Their first body positions satisfy (11). (11)✦ For the enumerated host , the copy count and its normalized density satisfy (12) and (13), respectively. (12)✦ (13)✦ More generally, let be a binary matrix of order , and let contain for every . Then (14) holds. (14)✦
In the paper, the result reads: for every integer , each ordered copy of in maps the entry into , and , and .
What Is Checked
The confinement statement and canonical bounds are stated over the raw host on with its separate row and column orders and increasing enumerations; the bound (14) is stated over every binary matrix and every cell set satisfying its body entry condition. The host position count and the injectivity of either traversal key are the assertions in (15). (15)