Về định lý Ramsey, các số Ramsey 2 màu và một số ứng dụng

Bài viết này nhằm mục đích tổng quan định lý Ramsey, các số Ramsey và một số vấn đề liên quan; Trên cơ sở đó xem xét ứng dụng của chúng vào trò chơi Ramsey và việc phát biểu một số bài toán sơ cấp hay và khó.
Nội dung trích xuất từ tài liệu:
Về định lý Ramsey, các số Ramsey 2 màu và một số ứng dụng VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU VÀ MỘT SỐ ỨNG DỤNG NGUYỄN THÀNH THÁI Khoa Toán học1 GIỚI THIỆUĐịnh lý Ramsey và các vấn đề liên quan đã đặt ra rất nhiều vấn đề thú vị và phần lớntrong số đó vẫn là những vấn đề mở. Bên cạnh đó, định lý Ramsey và các vấn đề liên quancũng có rất nhiều ứng dụng vào các lĩnh vực khác. Bài viết này nhằm mục đích tổng quanđịnh lý Ramsey, các số Ramsey và một số vấn đề liên quan; trên cơ sở đó xem xét ứngdụng của chúng vào trò chơi Ramsey và việc phát biểu một số bài toán sơ cấp hay và khó.2 MỘT SỐ KHÁI NIỆM VỀ ĐỒ THỊ 1. Cho tập hợp V và E là tập hợp bao gồm các tập con 2 phần tử của V . Khi đó, ta gọi cặp G = (V, E) là đồ thị G với tập đỉnh V và tập cạnh E. Đồ thị đầy đủ là đồ thị mà mọi cặp đỉnh đều được nối bởi một cạnh, kí hiệu Kn . 2. Đồ thị H được gọi là đồ thị con của đồ thị G nếu V (H) ⊆ V (G) và E(H) ⊆ E(G). 3. Đồ thị con H = (V (H), E(H)) của G với V (H) = {x1 , x2 , . . . xn } và E(H) = {x1 x2 , x2 x3 . . . xn−1 xn } được gọi là đường đi nối x1 với xn đi qua x2 , x3 , . . . , xn−1 và có độ dài n, kí hiệu P = x1 x2 . . . xn . Nếu tập E(H) có thêm cạnh xn x1 thì ta nói H là n−chu trình đi qua x1 , x2 , . . . , xn , kí hiệu C = x1 x2 . . . xn x1 . Đồ thị chu trình là đồ thị mà trong đó có chu trình đi qua tất cả các đỉnh và ngoài ra không có cạnh nào khác, kí hiệu Cn . 4. Siêu đồ thị G = (V (H), E(H)) có tập đỉnh V (H) như đồ thị thông thường và tập cạnh E(H) trong đó mỗi cạnh e ∈ E(H) là một tập con bất kì của V (H) (hay mỗi cạnh là một đường đi). Nếu tập cạnh của siêu đồ thị G chỉ gồm những đường đi độ dài n thì ta nói G là siêu đồ thị n-đều. Siêu đồ thị được gọi là n-đều đầy đủ nếu tập cạnh của nó chứa tất cả các đường đi độ dài n.Để biết thêm về lý thuyết đồ thị người đọc có thể tìm hiểu ở [1].Kỷ yếu Hội nghị Khoa học Sinh viên năm học 2013-2014Trường Đại học Sư phạm Huế, tháng 12/2013: tr. 37-4638 NGUYỄN THÀNH THÁI3 ĐỊNH LÝ RAMSEY VÀ CÁC SỐ RAMSEYKhi giảng về lý thuyết Ramsey, Paul Erdos, một nhà toán học lỗi lạc và là người đi đầutrong việc đề xuất những vấn đề về lý thuyết Ramsey, đã giới thiệu hai bài toán. Bài toánthứ nhất được mang tên là Party problem. Nội dung bài toán là trong 6 người cùng đidự tiệc, liệu có thể tìm ra 3 người quen biết lẫn nhau (đôi một quen biết) hoặc 3 ngườikhông quen biết lẫn nhau hay không? Bài toán được phát biểu tương đương là với mộtcách tô 2 màu các cạnh đồ thị đầy đủ 6 đỉnh, liệu ta có thể tìm ra một tam giác cùng màu?Và xa hơn, liệu rằng với chỉ 5 người dự tiệc, ta có thể làm được điều tương tự không? Lờigiải của những câu hỏi trên sẽ đề cập tới số đỉnh nhỏ nhất của một đồ thị đầy đủ mà vớimột cách tô 2 màu bất kì luôn tìm được một tam giác cùng màu, gọi là số Ramsey, kí hiệuR(3, 3).Định lý Ramsey khẳng định rằng với mọi cách tô màu một đồ thị (trong suốt bài viết này,khi nói đến tô màu đồ thị ta hiểu là tô màu các cạnh đồ thị) đầy đủ bậc đủ lớn, ta luôn cóthể tìm được một đồ thị con đầy đủ đồng màu. Với số màu tô là 2, định lý Ramsey phátbiểu rằng với bất kì 2 số nguyên dương (m, n), tồn tại số nguyên dương nhỏ nhất R(m, n)sao cho với mọi cách tô màu các cạnh của đồ thị đầy đủ có R(m, n) đỉnh bởi 2 màu xanhvà đỏ, thì luôn tồn tại một đồ thị con đầy đủ với m đỉnh màu xanh hoặc một đồ thị conđầy đủ với n đỉnh màu đỏ.Định lý 3.1. Với 2 số tự nhiên m, n > 1 thì số R(m, n) tồn tại hữu hạn.Định lý Ramsey cũng đúng trong trường hợp mở rộng cho nhiều màu. Với các số tự nhiênr > 2 và n1 , n2 , . . . , nr > 1, số Ramsey R(n1 , n2 , . . . , nr ) là số tự nhiên n nhỏ nhất sao chovới mọi cách tô Kn (đồ thị đầy đủ bậc n) bởi r màu (được đánh số [r] = {1, 2, . . . , r}),luôn tồn tại chỉ số m sao cho trong Kn có đồ thị con Kim đồng màu m.Định lý 3.2. Với mọi n1 , n2 , . . . , nr > 1, R(n1 , n2 , . . . , nr ) tồn tại hữu hạn.Thực chất 2 định lý trên chỉ là một trường hợp đặc biệt của định lý Ramsey cho siêuđồ thị. Hai định lý dưới đây được Frank Plumpton Ramsey đưa ra trong bài báo On aproblem of formal logic trên Proceedings London Mathematical Society năm 1928 (đượcđăng năm 1930) dưới ngôn ngữ tập hợp, trong đó định lý cho siêu đồ thị vô hạn là tổngquát nhất.Định lý 3.3. Cho các số tự nhiên n1 , n2 , . . . , nr , k > 1. Khi đó, tồn tại số tự nhiên n thỏamãn với mọi cách tô màu một đồ thị k-đều đầy đủ với n đỉnh bằng r màu được đánh số[r], luôn tồn tại chỉ số i sao cho siêu đồ thị con k-đều đầy đủ với ni đỉnh là đồng màu i.Số n nhỏ nhất trong định lý trên gọi là số Ramsey cho siêu đồ thị, kí hiệu Rk (n1 , n2 , . . . , nr )VỀ ĐỊNH LÝ RAMSEY, CÁC SỐ RAMSEY 2 MÀU... 39Định lý 3.4. Cho số tự nhiên n > 1 và G là một siêu đồ thị n-đều đầy đủ với số đỉnh vôhạn đếm được. Khi đó, nếu tô màu G bằng hữu hạn màu thì tồn tại một đồ thị con n-đềuđầy đủ với số đỉnh vô hạn đồng màu.Bài toán thứ hai Erdos đặt ra là giả sử chúng ta phải trả lời chính xác giá trị R(5, 5) chongười ngoài hành tinh hoặc họ sẽ hủy diệt trái đất thì khi đó chúng ta nên làm gì? Và nếuthay R(5, 5) bằng R(6, 6) thì sao? Với R(5, 5), Erdos nói rằng tất cả các nhà toán học cùngvới máy tính trên trái đất cần làm việc cật lực để tìm ra lời giải. Còn với R(6, 6), Erdoskhuyên rằng ta nên giành thời gian để nghĩ cách hủy diệt người ngoài hành tinh trước khiquá muộn! Bởi thực tế người ta đã chỉ ra rằng 102 ≤ R(6, 6) ≤ 165. Việc nghiên cứu tất cảnhững đồ thị tô màu với số đỉnh từ 102 đến 165 hầu như là điều không tưởng. Bằng mộtphép tính đơn giản, số các đồ thị 102 đỉnh cần nghiên ...