tailieunhanh - Bài giảng Toán rời rạc: Định lý Ramsey - Trần Vĩnh Đức

Bài giảng Toán rời rạc: Định lý Ramsey cung cấp cho người học những nội dung kiến thức như: Lý thuyết Ramsey, chứng minh định lý Ramsey, cận trên của số Ramsey, ví dụ và Tổng quát hoá. Mời các bạn cùng tham khảo. | Định lý Ramsey Trần Vĩnh Đức HUST https tailieudientucntt which often first manifest themselves inconspicuously as seemingly irrelevant curiosities. In this chapter we discuss one such peculiarity concerning graphs with a mere 6 vertices. We begin with the following popular form of the result. Six people meet at a party. Khẳng định Some of them know each other some of them don t perhaps Trong because số 6 ngườithey luônsee có one another ba người for the đôi một quenfirst nhautime. hoặc The ba party may lookđôi người according to one of the following schemes for example một lạ nhau. party 50 years lonely hearts party of meeting of two after graduation party admirers mafia bosses https tailieudientucntt Bài tập Hãy chứng minh rằng trong 9 người luôn có 3 người đôi một quen nhau hoặc 4 người đôi một không quen nhau. https tailieudientucntt Lý thuyết Ramsey Lý thuyết Ramsey theo tên của nhà toán học người Anh Frank Plumpton Ramsey. Hình F. P. Ramsey 1903-1930 https tailieudientucntt Khẳng định Trong sáu người bất kỳ luôn tồn tại ba người sao cho hoặc là họ quen nhau từng đôi một hoặc họ không quen nhau từng đôi một. Viết lại khẳng định trên một cách ngắn gọn dùng ký hiệu mũi tên như sau K6 K3 K3 với ý nghĩa K6 6 đối tượng và 15 cặp không thứ tự để thể hiện quan hệ quen hoặc lạ giữa các đối tượng này K3 K3 Ba đối tượng quen nhau từng đôi một Ba đối tượng không quen nhau từng đôi một https tailieudientucntt Ký hiệu Kn Kn một tập n đối tượng và mọi cặp không thứ tự cạnh các đối tượng này https tailieudientucntt Ký hiệu mũi tên Nếu ta xem mỗi cặp không thứ tự như một cạnh. Cặp đối tượng quen nhau xem như cạnh tô màu xanh. Cặp đối tượng không quen nhau như các cạnh tô màu đỏ. Vậy K6 K3 K3 có nghĩa là Dù có tô xanh đỏ các cạnh của K6 ta luôn tìm được một K3 có toàn cạnh đỏ hoặc một K3 toàn cạnh xanh .