Math Labs
Định lýĐã chứng minh

Định lý Ramsey

Phát biểu

Với mọi số nguyên dương r,sr, s, tồn tại số nguyên nhỏ nhất R(r,s)R(r,s) sao cho mọi cách tô 2 màu các cạnh của đồ thị đầy đủ KnK_n với n≥R(r,s)n \ge R(r,s) đều chứa hoặc một KrK_r đơn sắc ở màu thứ nhất, hoặc một KsK_s đơn sắc ở màu thứ hai.

Vì sao đúng?

Sự hỗn độn hoàn toàn là bất khả ở quy mô lớn: nếu một bữa tiệc đủ đông, ắt phải có một nhóm rr người đôi một quen nhau hoặc một nhóm ss người đôi một xa lạ. Dù bạn cố trộn các cạnh đỏ và xanh thế nào để tránh các cụm đầy đủ, một khi đồ thị đủ lớn thì một vùng đồng nhất buộc phải xuất hiện.

Phác thảo chứng minh

Chứng minh bằng quy nạp theo r+sr+s rằng R(r,s)≤R(r−1,s)+R(r,s−1)R(r,s) \le R(r-1,s) + R(r,s-1). Chọn một đỉnh vv trong KnK_n đã tô 2 màu với n=R(r−1,s)+R(r,s−1)n = R(r-1,s) + R(r,s-1); theo nguyên lý Dirichlet, vv có hoặc ít nhất R(r−1,s)R(r-1,s) đỉnh kề nối bằng cạnh đỏ, hoặc ít nhất R(r,s−1)R(r,s-1) đỉnh kề nối bằng cạnh xanh. Ở trường hợp đầu, tập đỉnh kề đỏ chứa hoặc một Kr−1K_{r-1} đỏ (hợp với vv tạo thành KrK_r đỏ) hoặc một KsK_s xanh; trường hợp thứ hai hoàn toàn đối xứng.

Chủ đề chứa định lý này

Lý thuyết Ramsey

Định lý liên quan

Nguyên lý Dirichlet (nguyên lý chuồng bồ câu)Định lý Szemerédi

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

  1. Frank P. Ramsey (1930). On a Problem of Formal Logic · DOI:10.1112/plms/s2-30.1.264