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.
Nội dung trích xuất từ tài liệu:
Bài giảng Toán rời rạc: Định lý Ramsey - Trần Vĩnh Đức Định lý Ramsey Trần Vĩnh Đức HUSTCuuDuongThanCong.com https://fb.com/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 bossesCuuDuongThanCong.com https://fb.com/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.CuuDuongThanCong.com https://fb.com/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)CuuDuongThanCong.com https://fb.com/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”CuuDuongThanCong.com https://fb.com/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”CuuDuongThanCong.com https://fb.com/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”CuuDuongThanCong.com https://fb.com/tailieudientucntt Chứng minh K6 → K3 , K3 ▶ Xét một đối tượng p của K6 . Vì có 5 cạnh liên quan đến p có mầu đỏ hoặc xanh nên có ít nhất 3 cạnh cùng màu. Ta giả sử 3 cạnh này cùng màu đỏ. (Nếu màu xanh ta lập luận tương tự.) Có ba đối tượng a, b, c nối với p qua ba cạnh đỏ này. a ▶ Bây giờ, nếu tồn tại một cạnh nối giữa a − b hoặc a − c hoặc b − c có màu đỏ, vậy ta được một K3 đỏ. p b ▶ Nếu không thì ta được K3 xanh liên c quan đến a, b, c.CuuDuongThanCong.com https://fb.com/tailieudientucntt K5 ̸→ K3 , K3 Khẳng định K5 → K3 , K3 là sai vì có cách tô màu cạnh K5 không tạo ra K3 đỏ hoặc K3 xanh.CuuDuongThanCong.com https://fb.com/tailieudientucntt Câu hỏi Giả sử Kn → Ka , Kb . Giải thích tại sao Kp → Ka , Kb với mọi p > n.CuuDuongThanCong.com https://fb.com/tailieudientucntt Câu hỏi ▶ Chứng minh rằng Kb → K2 , Kb . ▶ Chứng minh rằng Kb−1 ̸→ K2 , Kb .CuuDuongThanCong.com https://fb.com/tailieudien ...