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ó. | 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ọc 1 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ớn trong số đó vẫn là những vấn đề mở. Bên cạnh đó định lý Ramsey và các vấn đề liên quan cũ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 ứ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ó. 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-2014 Trường Đại học Sư phạm Huế tháng 12 2013 tr. 37-46 38 NGUYỄN THÀNH THÁI 3 ĐỊNH LÝ RAMSEY VÀ CÁC SỐ RAMSEY Khi 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 đầu trong việc đề xuất những vấn đề về lý thuyết Ramsey đã giới .
