Ramsey 数

Ramsey 数 $R(a,b)$ 是指最小的自然数 $n$, 使得每个有 $n$ 个顶点的图一定有一个 $a$ 个两两相邻的顶点或 $b$ 个两两不相邻的顶点. 例如, $R(3,3)=6$ 这一事实可以表述如下: 在世界上任意找 $6$ 个人, 总有 $3$ 个人两两认识, 或 $3$ 个人两两不认识.

Ramsey 数的存在性称为 Ramsey 定理.

1定义

定义 1.1 (Ramsey 数). 设 $a,b$ 是自然数. Ramsey 数 $R(a,b)$ 是指最小的自然数 $n$, 使得每个 $n$ 阶图一定有一个 $a$ 个两两相邻的顶点或 $b$ 个两两不相邻的顶点.

等价地说, Ramsey 数是最小的自然数 $n$, 使得如果对完全图 $K_n$ 的边用两种颜色进行着色, 那么一定有第一色的 $a$ 阶完全图或第二色的 $b$ 阶完全图.

定义 1.1 也可以推广到多种颜色的着色,超图,有向图.

定义 1.2 (多色 Ramsey 数). 设 $a_1,\dots ,a_r$ 是自然数. Ramsey 数 $R(a_1,\dots ,a_r)$ 是指最小的自然数 $n$, 使得如果对图 $K_n$ 的边用 $r$ 种颜色进行着色, 那么一定存在 $i=1,\dots ,r$, 使得图中有第 $i$ 色的 $a_i$ 阶完全图.

注 1.3. 定义 1.2 中的 $R(a_1,\dots ,a_r)$ 可以记作 $R(a_1,\dots ,a_r;r)$. 其表示了含 $r$ 种颜色.

定义 1.4 (超图的 Ramsey 数). $m$-超图表示每条边有 $m$ 个顶点的超图. 设 $a_1,\dots ,a_r$ 是自然数. Ramsey 数 $R(a_1,\dots ,a_r;r,m)$ 是指最小的自然数 $n$, 使得如果对完全 $m$-超图 $H_n$ 的边用 $r$ 种颜色进行着色, 那么一定存在 $i=1,\dots ,r$, 使得图中有第 $i$ 色的 $a_i$ 阶完全 $m$-超图.

定义 1.5 (有向图的 Ramsey 数). 设 $n$ 是自然数. Ramsey 数 $R(n)$ 是指最小的自然数 $m$, 使得 $m$ 阶完全有向图中一定有一个 $n$-顶点有向完全图.

2性质

此板块 $a_1,\dots ,a_r,s,r$ 都是自然数.

命题 2.1. $R(a_1,\dots ,a_r)$ 括号内各项可以随意交换位置, 且交换后此 Ramsey 数数值不变.

命题 2.2. 对于任意有限自然数 $a$ , $R(1,a)=1$ , $R(2,a)=a$.

命题 2.3. $R(s,r)⩽R(s-1,r)+R(s,r-1)$

命题 2.4. $R(a_1,\dots ,a_r)⩽R(a_1,\dots ,a_{r-2},R(a_{r-1},a_r))$

命题 2.5. $R(s,r)⩽\left(\genfrac{}{}{0ex}{}{r+s-2}{r-1}\right)$

(...)

3数值

下表列出了 Ramsey 数 $R(a,b)$ 的一些已知值.

$a╲b$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$2$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$3$	$1$	$3$	$6$	$9$	$14$	$18$	$23$	$28$	$32$
$4$	$1$	$4$	$9$	$18$	$25$

下表列出了 Ramsey 数 $R(n)$ 的一些已知值

$\mathbf{n}$	$R(n)$
$0$	$0$
$1$	$1$
$2$	$2$
$3$	$4$
$4$	$8$
$5$	$14$
$6$	$28$

4相关概念

•	抽屉原理
•	Seetapun 猜想
•	Ramsey 理论

术语翻译

Ramsey 数 • 英文 Ramsey number