拉姆齐法则_拉姆齐法则详解(拉姆齐定理有哪些)

2023-04-01 18:34:14

拉姆齐法则_拉姆齐法则详解(拉姆齐定理有哪些)

拉姆齐法则_拉姆齐法则详解(拉姆齐定理有哪些)?以下由小编为大家带来介绍。

1903年,弗兰克·拉姆齐出生于英国伦敦,后来进入剑桥大学三一学院学习数学,成为了一名杰出的数学家、哲学家和经济学家。可惜天妒英才,1930年就病逝于伦敦。但是在短短的岁月中,他

1903年,弗兰克·拉姆齐出生于英国伦敦,后来进入剑桥大学三一学院学习数学,成为了一名杰出的数学家、哲学家和经济学家。可惜天妒英才,1930年就病逝于伦敦。但是在短短的岁月中,他在数学和其它领域做出了许多贡献。今天所要谈论的是他在1930年发表的论文《形式逻辑上的一个问题》所提出来的拉姆齐定理。

拉姆齐定理(Ramsey Theorem)是图论中的一个重要概念,它被表述为对于任一具有N个顶点的完全图(complete graph),所有的顶点之间可以用红色或蓝色的线条连接,图中肯定会呈现出完全一致的大子集——要么全红,要么全蓝。我们也可以先通过确定一致子集的大小,再根据拉姆齐定理反推出能够形成该子集所需的完全图。

△ 完全图是指所有顶点间两两相连构成的图。(图片来源:Lucy
Reading-Ikkanda/QuantaMagazine)

拉姆齐定理还有一个简单易懂的版本叫“友谊定理”:六个人当中至少有三个人相互认识(朋友)或者相互不认识(陌生人)。但为什么这个定理是正确的?为什么完全图中的这些不同颜色的线条不能被完全打乱?数学家Jonathan Jedwab用一系列图形直观的解释了这个定理为什么是正确的。

让我们看一个简单的示例——一个六边形的完全图可以形成最少三条颜色一致的线组成的子集。这是为什么呢?

把这六个点看成六个人,其中任何一人与另一人必定处于认识或者不认识的状态。若认识,我们将二人用红线连接;若不认识,则用蓝线连接。因此在这个社交小圈子中,每个人都辐射出五条线与其他五人相连,并且其中至少三条线的颜色相同。这意味着无论你怎样连接这些人,结果一定会出现一个全红或者全蓝的三角形。

(图片来源:QuantaMagazine)

首先我们来看1,从他身上发射出的五条线中,像之前说过的至少有三条线颜色相同。假如他认识2、4、5,则这三条线便是红色。

(图片来源:QuantaMagazine)

再看2和5,假如2和5相识,则2与5间的连线也是红色,从而得到一个红色的三角形。我们看看是否有方法避免这样的三角形产生,所以假定2与5互不相识,并将2、5之间用蓝色线条标记。

(图片来源:QuantaMagazine)

接下来再思考4和5的关系,同样的,为了避免1、4、5形成红色三角形,我们假设4、5也互不相识。

(图片来源:QuantaMagazine)

最后考虑2和4的关系,结果发现不论2月4相识与否,都会形成一个红色或蓝色的三角形。于是一个单色的小色块集合便会出现,拉姆齐定理得到印证。

(图片来源:QuantaMagazine)

用这种方法研究更大的集合中样本时,比如数百万、数千万、数亿的人群,能看到组成的单色色团由大量相同颜色的线段组合而成。但究竟这个“大量”有多大呢?数学家们并不能确定,在已知一个单色子集的大小前,我们无法知道形成它所需要的完全图的最小大小。

拉姆齐定理也如其他许许多多日常使用的工具一样——它相当有用,但我们却不尽了解其背后所有的工作原理。

上一篇

热门阅读