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）
用这种方法研究更大的集合中样本时，比如数百万、数千万、数亿的人群，能看到组成的单色色团由大量相同颜色的线段组合而成。但究竟这个“大量”有多大呢？数学家们并不能确定，在已知一个单色子集的大小前，我们无法知道形成它所需要的完全图的最小大小。
拉姆齐定理也如其他许许多多日常使用的工具一样——它相当有用，但我们却不尽了解其背后所有的工作原理。
版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站不拥有所有权，不承担相关法律责任。如发现有侵权/违规的内容， 请联系我们将立刻清除。
什么是前期费用（工程项目前期费都包括哪些费用）
原创文章，作者：菜鸡，如若转载，请注明出处：https://www.20on.com/174945.html
