把一些染色定理推广到高维去

使用Van der waerden定理证明2维情况:给\Bbb Z^2染有限个颜色,则一定存在一个色类,使得在横方向上存在任意长的该色类单色等差数列,同时在纵方向上也存在任意长的该色类单色等差数列。

证明:首先,我们使用Van der waerden定理的有限形式:对于任意给定的k和m,存在N,使得只要n>N,给集合\{1,\cdots,n\}染m种颜色,期间一定存在k长的单色等差数列。关于此种形式和一般形式的等价性,可以使用一个标准的方法证明。参看Tao教授的帖子,软分析和硬分析

设我们染m种颜色。我们先来证明,对于任意给定的k,一定存在一个色类,使得两个方向都存在k长的该色类等差数列。为此,由上面的定理,我们先取得相应的N,使得给\{1,\cdots,N\}染m种颜色色,总存在k长单色等差数列。对于上面的N再次使用定理,我们找到大数K_2使得给\{1,\cdots,K_2\}染m种颜色,一定有N长单色等差数列。依次类推,我们一直取到K_N,是满足对任意\{1,\cdots,K_{i+1}\}染m种颜色,一定存在K_i长单色等差数列。

我们首先在y=N上找到K_N长等差数列(仍是Van der waerden定理),然后在它们每个点的下方,直线y=N-1上找到K_{N-1}长单色等差数列。这样一直到y=1上找到长为k的单色等差数列。我们至此拥有了长为k的连续N个单色等差数列,它们拥有相同的纵坐标。最后使用一次Van der waerden定理的有限形式,我们找到了色类使得同时两个方向有k长的该色类等差数列。

然后,对于任意的k,都找到相应的色类。而根据鸽笼原理,一定可以找到一个色类对应的k有无穷多个。而显然该色类对所有的k都满足条件(注意一个隐含的性质,k长等差单色数列同时也至少是k-1长等差单色数列)。

最后,我们再把结论推广到可数无穷维情况:对\Bbb Z^\omega染m种颜色,我们有一个色类,在每个方向上(可数无穷多个)都有任意长的该色类单色等差数列。(提示,再次使用无限版本的鸽笼原理。)

About these ads
Explore posts in the same categories: combinatorics, Ergodic Theory, Maths

One Comment on “把一些染色定理推广到高维去”


  1. […] Thus we can use the trick to generalize clouring theorem to higher dimensions (as we do in some other situations) and get to our […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 26 other followers

%d bloggers like this: