combinatorics

A trivial proof of Ramsey’s theorem

- by zyymat - Leave a Comment

Ramsey’s theorem   给定正整数 \(c(\geqslant2), m(\geqslant3)\), 则存在正整数 \(N\), 当 \(n\geqslant N\) 时, 任意 \(c\) 色完全图 \(K_n\)必有单色完全子图 \(K_m\). 这两天读 terence tao的文章” What is good mathematics?”, 里面提到了这个定理. 当然, 很早以前我就学过这个组合中有名的结果, 那时我是一个高中生. 李炯生的书, “数学竞赛中的图论方法”(中国科学技术大学出版社,1992年)有一章是谈这个定理的, 还有一章谈应用. 这书证明了两色的情况, …

A trivial proof of Ramsey’s theorem Read More
math.NT

Positive density doesn’t assure infinite arithmetic progression

- by zyymat - Leave a Comment

密率与无限算术级数 Szemerédi’s theorem 任意有正（上）密率的正整数的子集必定包含任意长的算术级数. Van der Waerden’s theorem 把正整数集合任意划分成两个子集, 必有一个子集包含任意长的算术级数. 这里先要说明的是, Szemerédi’s theorem中的子集未必包含无限长的算术级数, Van der Waerden’s theorem 也未必有一个子集包含无限长的算术级数. 看下面的例子: \[ \{1,2,3\}\bigcup \{n: 2^{2i} \leqslant n < 2^{2i+1}, i \in {\Bbb N}\}\] 问题：正整数集合的子集 …

Positive density doesn’t assure infinite arithmetic progression Read More