3
$\begingroup$

A string over a finite alphabet $A$ can be thought of as a function $f:\{1,2,...,m\} \rightarrow A$ for some natural number $m$.

A 2-Dim string over $A$ is a function $f$ where $f:\{1,2,\ldots,m\}\times\{1,2,\ldots,n\} \rightarrow A$ for some natural numbers $m$ and $n$.

If $f$ and $f'$ are 2-Dims (over $A$), with dimensions $(m,n)$ and $(m'n')$ respectively, we say $f\leq f'$ if there is are increasing functions $D:\{1,2,\ldots,m\}\rightarrow\{1,2,\ldots, m'\}$ and $E:\{1,2,\ldots,n\}\rightarrow\{1,2,\ldots, n'\}$ such that whenever $1\leq i\leq m$ and $1\leq j\leq n$, $f(i,j)=f'(D(i),E(j))$.

Is there a proof or disproof of the version of Higman's lemma that states that for every infinite sequence $f_1,f_2,\ldots$ of 2-Dims over $A$, there is $1\leq u<v$ such that $f_u\leq f_v$?

Edit August 29 2023

  1. This same question was posed and solved here.
  2. I've posted a new attempt at a two-dimensional version of Higman's Lemma here.
$\endgroup$
1
  • 1
    $\begingroup$ would it be a special case of Robertson-Seymour theorem, on well quasi-ordering of graphs? $\endgroup$ Commented May 29, 2019 at 19:13

1 Answer 1

3
$\begingroup$

I think there's a counterexample. Consider rectangles that look something like this:

10000000
10000000
11000000
01100000
00110000
...
00000011
00000001
00000001

where we increase the size of the "middle" block by one each time. Since only the first and the last column contain three 1's then any embedding would have to map those two columns to one another but then the other connections form a path between them.

This of course is closely related to the antichain of graphs under the induced subgraph relation that you get by taking paths of various lengths and splitting the first and last vertices into independent pairs.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .