close
Ramsey number
如果在一群人之中
存在一個三人子集
他們兩兩相識或是不相識
則這群人最少六個
更簡單的說
一個完全圖K6 將其邊著上紅或黑
必存在一個全黑或是全紅的三角形(K3)
所以以圖來說
Ramsey number r(m, n) 就是最小的整數 i
使得Ki的任意邊 2-著色
存在一個全部顏色相同的 Km 或 Kn 子圖
更一般的來說
t, q1, q2, ... , qn屬於自然數
且t<= q1, q2, ... , qn
則存在一個整數 p
使得
若一個有p個元素的集合中
任意 t元子集 給其一代表數(顏色代號){1, 2, ... , n}
必有一整數 k 以及 一個qk個 t元子集所構成的集合 S
S中的每個 t元子集皆對應相同的 k
Ramsey theorem 證明整數p的存在性
應該吧
如果在一群人之中
存在一個三人子集
他們兩兩相識或是不相識
則這群人最少六個
更簡單的說
一個完全圖K6 將其邊著上紅或黑
必存在一個全黑或是全紅的三角形(K3)
所以以圖來說
Ramsey number r(m, n) 就是最小的整數 i
使得Ki的任意邊 2-著色
存在一個全部顏色相同的 Km 或 Kn 子圖
更一般的來說
t, q1, q2, ... , qn屬於自然數
且t<= q1, q2, ... , qn
則存在一個整數 p
使得
若一個有p個元素的集合中
任意 t元子集 給其一代表數(顏色代號){1, 2, ... , n}
必有一整數 k 以及 一個qk個 t元子集所構成的集合 S
S中的每個 t元子集皆對應相同的 k
Ramsey theorem 證明整數p的存在性
應該吧
全站熱搜
留言列表
