6

Ramsey’s theorem

 3 years ago
source link: https://zhuanlan.zhihu.com/p/402510108
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Ramsey’s theorem

CrackingOysters，也是微信公众号

Ramsey theorem在<<Introduction to the Theory of Computation>>的习题0.14。

英文版本为，

Let G be a graph. A clique in G is a subgraph in which every two nodes are connected by an edge. An anti-clique, also called an independent set, is a subgraph in which every two nodes are not connected by an edge. Show that every graph with n nodes contains either a clique or an anti-clique with at least
[公式] nodes

翻译如下，

[公式] 表示一个图。一个小集团(clique)是图G的一个子图，这个子图任意的两个节点都有一条边关联。一个反集团(anti-clique)，也叫独立集，它里面没有一对节点是相连的。证明每一个有n个节点的图，总会包含至少有 [公式] 大小的小集团或者反集团。

小集团，反集团听起来很难理解，其实Ramsey theorem有一个更形象的名字，叫友谊定理。

我们可以认为相连的两个节点，相当于两个互相认识的人。不相连的两个节点，相当于两个人不认识。所以上面的定理，可以表述为任意一个有n个人的房间里面，总会有至少 [公式] 个人相互认识，或者相互不认识。

比如房间里面有16个人，以下情况总会有一个成立，

  • 至少有2个人互相认识
  • 至少有2个人互相不认识

额，这不是很明显吗？所以应该关注的问题是，如何证明这个定理。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK