拉姆齐定理
应用于数学等学科的定理
创建同名条目
条目
历史版本
编辑
在
组合数学
上,
拉姆齐
(Ramsey)
定理
是要解决以下的问题:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。这个定理以
弗兰克·普伦普顿·拉姆齐
命名,1930年他在论文On a Problem in Formal Logic(《形式逻辑上的一个问题》)证明了R(3,3)=6。
[1]
通俗表述
6个
人中
至少存在3人相互认识或者相互不认识。
该定理等价于证明这6个顶点的
完全图
的边,用红、蓝二色任意着色,必然至少存在一个红色边三角形,或蓝色边三角形。
验证推导