A second attempt at a two-dimensional Higman's Lemma

Question

Let $A$ be a fixed finite alphabet.

If $s$ and $t$ are finite strings over $A$, define $s\leq t$ if $s$ can be obtained by deleting zero or more characters from $t$. Higman's Lemma states that if $s_1,s_2,\ldots$ is an infinite sequence of finite strings over $A$, then there is an $i<j$ such that $s_i\leq s_j$. (This property is often referred to by the linguistically bizarre term "well quasi ordered". )

Is there a similar theorem that holds for finite two-dimensional arrays over $A$? What ordering should we use? The obvious choice is to say that if $s$ and $t$ are arrays (the dimensions may not be the same), then define $s\leq t$ if $s$ can be obtained by deleting zero or more rows and zero or more columns from $t$. The analogue of Higman's Lemma would state that if $s_1,s_2,\ldots$ is an infinite sequence of finite arrays over $A$, then there is an $i<j$ such that $s_i\leq s_j$. This is false. This question was raised and answered here and here.

This raises the question of whether there is a natural but more liberal ordering on arrays that satisfies the analogue of Higman's Lemma. Consider the following.

Let $s$ with dimensions $(m,n)$, and $t$ with dimensions $(m',n')$, be arrays over $A$. By inserting $m-1$ horizontal lines between some rows of $t$ and $n-1$ vertical lines between some columns of $t$ we obtain a division of $t$ into an $m$ by $n$ array, of arrays over $A$. We now define $s\leq t$ if there is such a division of $t$ such that for all $1\leq i\leq m$ and $1\leq j\leq n$, the character $s(i,j)$ is contained somewhere in the array that's in position $(i,j)$ of the divsion of $t$.

With this new definition of $\leq$ for arrays, I wish to prove or disprove the analogue of Higman's Lemma that states that if $s_1,s_2,\ldots$ is an infinite sequence of finite arrays over $A$, then there is an $i<j$ such that $s_i\leq s_j$.

EXAMPLE:
Let $s$=

    1 1 0  
    0 1 1  
    1 0 1  

and let $t$=

    1 1 0 0  
    0 1 1 0  
    0 0 1 1  
    1 0 0 1  

It is not the case that $s\leq t$ according to the first definition of $\leq$ for arrays.

However, observing the following 3-by-3 division of $t$

    1 ┆ 1 ┆ 0 0  
    --┆---┆-----  
    0 ┆ 1 ┆ 1 0  
    0 ┆ 0 ┆ 1 1  
    --┆---┆-----  
    1 ┆ 0 ┆ 0 1  

we see that $s\leq t$ according to the second definition above.

Answer 1

The answer is still no. Here is a counterexample for three letters $X,Y,Z$; With a bit of care in the arguments, it can be fir into two letters.

For convenience, we present a sequence where indices start with $n=10$.

So, for each $n\geq 10$, let $s_n$ be a $n\times n$ array, where the columns and rows are numbered from $1$ to $n$ (left-to-right and bottom-to-top) such that:

$\bullet$ $Y$'s are situated at all entries $(i,j)$, with $i+j\in\{n+1,n+5\}$;

$\bullet$ the unique $Z$ is situated at $(n-2,n-2)$;

$\bullet$ all other entries are $X$'s.

Assume that $s_k\leq s_\ell$ with $k<\ell$. Let $s_\ell$ be cut by lines to the right of columns $a_1<a_2<\dots<a_{k-1}<a_k=\ell$ and above the rows $b_1<b_2<\dots<b_{k-1}<b_k=\ell$, to produce the $k\times j$ array of cells. Then:

$\bullet$ $a_i+b_{k+1-i}\geq \ell+1$ for all $i=1,2,\dots,k$ (otherwise we get no $Y$ at the cell $(i,k+1-i)$);

$\bullet$ $a_{i+1}+b_{k+2-i}\leq \ell+3$ for all $i=3,\dots,k-2$ (otherwise we get no $Y$ at the cell $(i+2,k+3-i)$).

This yields that $(a_{i+1}-a_i)+(b_{k+2-i}-b_{k+1-i})\leq 2$, so necessarily $a_{i+1}-a_i=1$ and $b_{i+1}-b_i=1$ for all $i=3,\dots,k-2$. Moreover, this yields that $a_i+b_{k+1-i}=\ell+1$ for all $i=3,4,\dots,k-2$, as all the inequalities come into equalities. Hence $$ a_{k-2}+b_{k-2}=(a_{k-2}+b_3)+\sum_{j=3}^{k-3}(b_{j+1}-b_j) =\ell+k-4<2\ell-4. $$ So the cell $(k-2,k-2)$ does not contain $Z$. A contradiction.