论文标题
在Erdős-Szekeres定理上的注释二维
A note on the Erdős-Szekeres theorem in two dimensions
论文作者
论文摘要
Burkill和Mirsky和Kalmanson，独立地证明，对于每$ r \ ge 2，n \ ge 1 $ 1至$ n $，$（v^{j} _i）_ {1 \ le j \ le r+1} $形成单调序列。此外，$ r^{2^n} $是此属性最大的整数。在此简短说明中，对于两个向量$ u =（u_1，u_2，\ dots，u_n）$和$ v =（v_1，v_1，v_2，\ dots，v_n）$ in $ \ mathbb r^n $，我们说$ u \ u \ u \ u \ u \ u \ u \ u \ u \ u \ u \ u \ u \ u $ i $ $ $ $ i $之间，$ n $之间，$ n $ n $ $ u_i $ \ u_i \ le v_i \ le v_i。就像Burkill和Mirsky和Kalmanson一样，对于每个$ k，\ ell \ ge 1，d \ ge 2 $，我们都会发现最大$ n_1，n_2 $（结果相等），因此数值的二维数组均为$ $ $（k+ell-1）$（k+ell-1）\ times n_1 $（k+el），n_1 $（k+el），\ el \ el \ el \ el \ el \ el \ ell \ ell \ el \ el \ ell \ el \ ell \ el \ ell \ el \ el \ ell） $ k \ times d $，其列形成了$ \ mathbb r^k $的$ d $ vectors的非排除序列，也不包含一个大小$ \ ell \ ell \ times d $的子阵列，其列形成了$ d $ vectors in $ \ mathbb r r^{\ el e^{\ ell} $的非增加序列。在随之而来的讨论中，我们考虑了这种环境的概括，并与编码理论中的著名问题建立联系。
Burkill and Mirsky, and Kalmanson, prove independently that, for every $r\ge 2, n\ge 1$, there is a sequence of $r^{2^n}$ vectors in $\mathbb R^n$, which does not contain a subsequence of $r+1$ vectors $v^1, v^2,\dots,v^{r+1}$ such that, for every $i$ between 1 and $n$, $(v^{j}_i)_{1\le j\le r+1}$ forms a monotone sequence. Moreover, $r^{2^n}$ is the largest integer with this property. In this short note, for two vectors $u = (u_1, u_2,\dots, u_n)$ and $v = (v_1, v_2, \dots, v_n)$ in $\mathbb R^n$, we say that $u\le v$ if, for every $i$ between 1 and $n$, $u_i\le v_i$. Just like Burkill and Mirsky, and Kalmanson, for every $k, \ell\ge 1, d\ge 2$ we find the maximal $N_1, N_2$ (which turn out to be equal) such that there are numerical two-dimensional arrays of size $(k+\ell-1)\times N_1$ and $(k+\ell)\times N_2$, which neither contain a subarray of size $k\times d$, whose columns form a non-decreasing sequence of $d$ vectors in $\mathbb R^k$, nor contain a subarray of size $\ell\times d$, whose columns form a non-increasing sequence of $d$ vectors in $\mathbb R^{\ell}$. In a consequent discussion, we consider a generalisation of this setting and make a connection with a famous problem in coding theory.
