Đăng ký Đăng nhập
Trang chủ Lý thuyết Ramsey và vài ứng dụng...

Tài liệu Lý thuyết Ramsey và vài ứng dụng

.PDF
54
980
150

Mô tả:

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- ĐINH HỮU LÂM LÝ THUYẾT RAMSEY VÀ MỘT SỐ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC Hà Nội – Năm 2014 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ------------------- ĐINH HỮU LÂM LÝ THUYẾT RAMSEY VÀ MỘT SỐ ỨNG DỤNG Chuyên ngành : Phương pháp toán sơ cấp Mã số : 60 46 40 LUẬN VĂN THẠC SĨ KHOA HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS. TẠ DUY PHƯỢNG Hà Nội – Năm 2014 MỤC LỤC Trang Mục lục 1 Lời nói đầu 2 Chương 1 Kiến thức chuẩn bị 4 Chương 2 Định lí Ramsey 7 §1 Định lí Ramsey trong lí thuyết đồ thị 7 §2 Định lí Ramsey trong tập hợp hữu hạn 15 Chương 3 Ứng dụng của định lí Ramsey 15 §1 Định lí Schur 25 §2 Định lí Erdös–Szekeres 32 §3 Ứng dụng trong giải toán phổ thông 39 Kết luận 51 Tài liệu tham khảo 52 1 LỜI NÓI ĐẦU Năm 1928, nhà toán học người Anh Frank Plumpton Ramsey đã công bố kết quả chứng minh của ông trên tạp chí “On a Proplem of Formal logic” trong đó ông đã chứng minh định lí”Giả sử họ  r  S  được phân hoạch thành hai họ các tập hợp A và B , p và q là hai số nguyên sao cho r  p, q  s . Khi ấy tồn tại số nguyên nhỏ nhất R  p, q, r  chỉ phụ thuộc vào các số p, q, r mà không phụ thuộc vào tập S , sao cho nếu s  R  p, q, r  thì tồn tại một tập P gồm p phần tử của S , mà tất cả các tập con r phần tử của P đều thuộc A , hoặc tồn tại một tập Q gồm q phần tử của S , mà tất cả các tập con r phần tử của Q đều thuộc B ”. Định lí trên sau này được gọi là Định lý Ramsey. Định lí trên đã mở ra một cách tiếp cận mới về các bài toán tổ hợp nay được gọi là lý thuyết Ramsey. Trong luận văn này tôi sẽ giới thiệu một số kết quả quan trọng trong lý thuyết Ramsey và một số ứng dụng của lí thuyết này. Năm 1916 Issai Schur đã chứng minh rằng “Cho r là số tự nhiên, r  1 . Khi đó tồn tại một số tự nhiên S (r ) sao cho N  S(r ) , tập số {1,2,…,N} được tô bởi r màu luôn tồn tại ba số x, y, z có cùng màu sao cho x  y  z ”. Kết quả cơ bản này đã được tổng quát hóa bởi Richard Rado vào năm 1933. Định lý Van der Waerden đã được chứng minh vào năm 1927, một năm sớm hơn so với chứng minh của Ramsey. Van der Waerden đã chứng minh rằng “Cho k, r là số tự nhiên k, r  1 . Khi đó tồn tại một số tự nhiên W(k, r ) sao cho N  W(k, r ) , tập số {1,2,…, W(k, r ) } được tô bởi r màu luôn tồn tại k số được tô cùng màu lập thành một cấp số cộng”. 2 Năm 1935, Paul Erdös và György Szekeresđã phát biểu giả thuyết (Erdös– Szekeres, 1935) “ Với mỗi số tự nhiên n  3 , mọi tập có tối thiểu N  n   2n2  1 điểm trên mặt phẳng ở vị trí tổng quát, đều chứa n điểm là đỉnh của một đa giác lồi n cạnh.” Các kết quả trên có thể được chứng minh độc lập với định lý Ramsey, tuy nhiên sau khi Ramsey công bố kết quả chứng minh của mình thì các bài toán trên đã được chứng minh lại theo cách ngắn gọn hơn nhờ áp dụng định lý Ramsey. Luận văn được chia làm ba chương Chương I Kiến thức chuẩn bị Chương II Định lý Ramsey Chương III Ứng dụng của định lý Ramsey. Luận văn được hoàn thành dưới sự hướng dẫn tận tình của PGS.TS. Tạ Duy Phượng, Viện Toán học – Viện Khoa học và Công nghệ Việt Nam. Em xin bày tỏ lòng biết ơn sâu sắc nhất đối với Thầy. Tôi xin được cảm ơn khoa Toán, khoa Sau Đại học trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã quan tâm giúp đỡ, tạo điều kiện thuận lợi cho tôi thực hiện kế hoạch học tập. Hà Nội ngày 26 tháng 8 năm 2014 Đinh Hữu Lâm 3 CHƯƠNG 1 KIẾN THỨC CHUẨN BỊ §1.1 Một số khái niệm cơ bản của lí thuyết đồ thị Định nghĩa 1.1.1Đồ thị được hiểu là một bộ hai tập hợp hữu hạn : tập hợp đỉnh và tập hợp cạnh nối các đỉnh này với nhau. Định nghĩa 1.1.2Mộtđồ thị n đỉnh được gọi là đồ thị đầy đủ nếu hai đỉnh bất kì của nó có đúng một cạnh nối. Một đồ thị đầy đủ n đỉnh kí hiệu là K n . Định nghĩa 1.1.3 Một đồ thị gọi được là đồ thị đều bậc t nếu mỗi đỉnh của đồ thị G có bậc là t. Định nghĩa 1.1.4 Một đồ thị n đỉnh gọi là đồ thị hai màu nếu các cạnh của nó được tô bởi hai màu xanh hoặc đỏ. Định nghĩa 1.1.5 Một đồ thị n đỉnh gọi là đồ thị r màu nếu các cạnh của nó được tô bởi một trong r màu k1 , k2 ,..., kr . §1.2 Nguyên lí Dirichlet Định lí Ramsey là một cách mở rộng của Nguyên lí chuồng chim bồ câu (Nguyên lí Dirichlet): Một tập gồm s phần tử được chia thành n các tập con phân biệt. Nếu s  n thì tồn tại ít nhất một tập con chứa nhiều hơn một phần tử. Nguyên lí Dirichlet được dùng để giải bài toán sau. Bài toán 1.2.1 Sáu điểm được nối với nhau bởi các đoạn thẳng tô màu đỏ hoặc xanh. Chứng minh rằng tìm được một tam giác đơn sắc, nghĩa là tam giác có ba cạnh cùng có màu đỏ hoặc màu xanh. 4 Giải. Kí hiệu một đỉnh là O , các đỉnh còn A lại là A, B, C , D, E. Theo nguyên lí Dirichlet, có ít nhất ba trong số các cạnh OA, OB, OC , OD, OE là cùng màu (đỏ hoặc B xanh). Giả sử OA, OB, OC có cùng màu đỏ. O Xét tam giác ABC . Nếu có ít nhất một C E cạnh, thí dụ, AB là màu đỏ, thì tam giác OAB có cả ba cạnh là màu đỏ. Nếu tất cả F các cạnh của tam giác ABC là màu xanh, thì tam giác ABC là tam giác cần tìm. Như vậy, từ 6 điểm không thẳng hàng, ta có tất cả C63  20 tam giác, trong đó có ít nhất một tam giác đơn sắc (các cạnh cùng màu đỏ hoặc xanh). Câu hỏi Số điểm ít nhất là bao nhiêu để không có một tam giác đơn sắc? Trả lời Số điểm ít nhất là 6. Thật vậy, xét năm điểm A, B, C , D, E với các cạnh AB, BC , CD, DE , EA màu xanh và các cạnh AD, AC , BE , BD, CE màu đỏ. Khi ấy màu của các cạnh của các tam giác được cho trong hình bên và bảng sau. Tam giác Cạnh xanh Cạnh đỏ Tam giác Cạnh xanh Cạnh đỏ ABC AB; BC AC ADE AE; DE AD ABD AB; AD; BD BCD BC;CD BD 5 ABE AB; AE BE BCE BC BE; CE ACD CD AD;AC BDE DE BD;BE ACE AE AC; CE CDE CD; DE CE Như vậy, không có tam giác nào trong số tất cả 10 tam giác có các cạnh cùng màu. Nói cách khác, trong năm điểm bất kỳ không có một tam giác đơn sắc. Dưới đây ta cố gắng phát triển tư tưởng của Bài toán 1.2.1 trên ngôn ngữ tập hợp kết hợp với nguyên lí Dirichlet. Trong nguyên lí Dirichlet, tập gồm s phần tử được chia thành n tập với các phần tử riêng rẽ. Nếu s  n thì tồn tại một tập gồm ít nhất hai phần tử từ tập cho trước (gồm s phần tử). Tập hai phần tử này có thể coi như một tập chứa hai tập con một phần tử trong cùng một lớp chia. Trong Bài toán 1.2.1, ta có một tập gồm sáu phần tử. Chúng có thể được coi là sáu đỉnh của một đồ thị, kí hiệu là K 6 . Ta có thể coi các tập hai phần tử lấy từ tập các đỉnh như là các cạnh. Và coi tập ba phần tử (ba đỉnh) như là tam giác. Chia các cạnh thành hai lớp, là lớp các cạnh màu đỏ và lớp các cạnh màu xanh. Và ta đã chỉ ra rằng trong đồ thị K 6 có một tam giác có cả ba cạnh được tô cùng màu đỏ hoặc cùng màu xanh. Nói cách khác, nếu ta chia tập gồm sáu điểm thành hai lớp các tập hợp hai điểm, thì có một tập ba điểm nào đó trong tập gồm sáu điểm có mọi tập con hai điểm nằm trong cùng một lớp chia. Từ bài toán đơn giản trên, ta đi đến một định lí quan trọng là định lí Ramsey được trình bày trong chương 2. 6 CHƯƠNG 2 ĐỊNH LÍ RAMSEY §2.1 Định lí Ramsey trong lí thuyết đồ thị 1. Định lí Ramsey cho đồ thị hai màu Định lí 2.1.1Cho 2 số tự nhiên p và q. Khi ấy tồn tại số tự nhiên nhỏ nhất R  p, q  chỉ phụ thuộc vào các số p, q sao cho mọi đồ thị đầy đủ n đỉnh 2 màu, n  R  p, q  luôn tồn tại một đồ thị con đầy đủ p đỉnh mà tất cả các cạnh được tô màu xanh hoặc q đỉnh mà tất cả các cạnh được tô màu đỏ. Bổ đề 2.1.2 1) R  p, 2   p . 2) R  2, q   q . 3) R  p, q   R  q, p  . Chứng minh 1) Nếu R  p, 2   p  1 ta chọn đồ thị đầy đủ có p  1 đỉnh mà tất cả các cạnh được tô màu xanh thì đồ thị này không thỏa mãn định lí suy ra R  p, 2   p  1. Ta xét một đồ thị 2 màu đầy đủ có p đỉnh. Nếu tất cả các cạnh được tô màu xanh thì p đỉnh này thỏa mãn định lí. Nếu tất cả các cạnh không được tô màu xanh thì tồn tại một cạnh được tô màu đỏ giả sử là AB thì 2 đỉnh A, B thỏa mãn định lí suy ra R  p, 2   p . Vậy R  p, 2   p . 2) Chứng minh tương tự ta có R  2, q   q . 3) Do vai trò như nhau của 2 màu xanh ,đỏ nên ta có R  p, q   R  q, p  . Bổ đề 2.1.3 R  p, q   R  p  1, q   R  p, q  1 . Chứng minh Đặt n  R  p  1, q   R  p, q  1 xét đồ thị 2 màu đầy đủ n đỉnh kí hiệu là K n . Gọi A là một đỉnh bất kì thuộc đồ thị. 7 Kí hiệu: BA = {Tập tất cả các đỉnh thuộc K n mà cạnh nối nó với A có màu xanh} RA = {Tập tất cả các đỉnh thuộc K n mà cạnh nối nó với A có màu đỏ} Vì K n là đồ thị đầy đủ nên BA  RA  n  1 . Nếu BA  R  p  1, q  và RA  R  p, q  1 thì BA  RA  n  2 vô lí. Vậy BA  R  p  1, q  hoặc RA  R  p, q  1 . Giả sử BA  R  p  1, q  suy ra hoặc tồn tại p  1 đỉnh mà tất cả các cạnh có màu xanh thì p  1 đỉnh này cùng với A tạo thành đồ thị có p đỉnh mà tất cả các cạnh có màu xanh hoặc tồn tại q đỉnh mà tất cả các cạnh có màu đỏ .Vậy khi n  R  p  1, q   R  p, q  1 thì luôn tồn tại p đỉnh mà tất cả các cạnh có màu xanh hoặc tồn tại q đỉnh mà tất cả các cạnh có màu đỏ tức là R  p; q   n  R  p  1, q   R  p, q  1 . Chứng minh Định lí 2.1.1 Ta sẽ chứng minh Định lí 2.1.1 bằng cách quy nạp theo p, q . Theo Bổ đề 2.1.2 ta có R  p, 2   p ; 2) R  2, q   q . Giả sử R  p, q  1 và R  p  1, q  là tồn tại theo Bổ đề 2.1.3 ta có R  p, q   R  p  1, q   R  p, q  1 suy ra định lí được chứng minh. 2. Số Ramsey Định nghĩa 2.1.4 Số R  p, q  trong Định lí 2.1.1 được gọi là số Ramsey. 8 Ta thấy bài toán 1.2.1 là một trường hợp đặc biệt của định lí Ramsey lúc này R  3, 3  6 . Bài toán 2.1.5 Chứng minh rằng R  3, 4   9 . Chứng minh Hình bên là một đồ thị gồm 8 đỉnh K8 có các cạnh được tô màu đỏ hoặc xanh (đỏ– đường nét liền; xanh–đường nét đứt) không chứa đồ thị con K 3 có tất cả các cạnh màu xanh, cũng không chứa đồ thị con K 4 nào có tất cả các cạnh màu đỏ. Như vậy R  3, 4   8 . 1 1 8 2 8 7 3 7 6 6 3 4 6 4 5 5 Ta phải chứng minh rằng trong đồ thị hai màu K 9 thì luôn tồn tại một đồ thị con K 3 có tất cả các cạnh màu xanh hoặc một đồ thị con K 4 có tất cả các cạnh màu đỏ. Gọi x1 là một đỉnh nào đó của K 9 . Nối x1 với tám đỉnh còn lại thì theo nguyên lí Dirichlet phải có tối thiểu bốn đỉnh nối với x1 bởi các cạnh hoặc màu đỏ hoặc màu xanh. 9 Trường hợp 1:Có ít nhất bốn đỉnh được đánh số là x2 , x3 , x4 , x5 nối với x1 bởi các cạnh màu xanh. Nếu tồn tại một cặp hai điểm trong số bốn đỉnh x2 , x3 , x4 , x5 , thí dụ, x2 , x3 được nối với nhau bởi cạnh màu xanh, thì ta có đồ thị con K3   x1 , x2 , x3 có tất cả các cạnh màu xanh. Nếu không tất cả các cạnh tạo bởi bốn điểm x2 , x3 , x4 , x5 phải đều là màu đỏ, khi ấy ta lại có đồ thị con K 4   x2 , x3 , x4 , x5 có tất cả các cạnh màu đỏ. Trường hợp 2:Có nhiều nhất ba đỉnh nối với x1 bởi các đoạn màu xanh, nghĩa là có ít nhất năm đỉnh được nối với x1 bởi các đoạn màu đỏ. Nếu tất cả các đỉnh được nối với 8 đỉnh còn lại bởi năm cạnh màu đỏ và ba cạnh màu xanh.Bây giờ ta xét đồ thị con đơn sắc (monochromatic subgraphs). Trong đồ thị con đơn sắc màu xanh, có tất cả 9 đỉnh, mỗi đỉnh có bậc 3 (có ba cạnh xuất phát từ một đỉnh có màu xanh). Suy ra số cạnh màu xanh là 9.3 27 (vì mỗi cạnh  2 2 được tính 2 lần).Vô lí. Vậy phải tồn tại đồ thị K 6 được tạo bởi 6 đỉnh, kí hiệu là x2 , x3 , x4 , x5 , x6 , x7 , được nối với x1 bởi các đoạn màu đỏ. Đồ thị K 6 có các cạnh đều được tô màu đỏ hoặc màu xanh. Từ Bài toán 1.6 tồn tại tam giác có ba cạnh màu đỏ hoặc ba cạnh màu xanh. Nếu tam giác này có ba cạnh màu xanh thì nó cũng là tam giác có ba cạnh màu xanh của K 9 . Còn nếu tồn tại một tam giác, kí hiệu là x2 x3 x4 có ba cạnh màu đỏ.Khi đó vì x2 , x3 , x4 được nối với x1 bởi các cạnh màu đỏ nên đồ thị gồm các đỉnh K 4   x2 , x3 , x4 , x1 có tất cả bốn cạnh màu đỏ. 10 Vậy trong mọi trường hợp thì đồ thị 2 màu K 9 luôn tồn tại một đồ thị con K 3 có tất cả các cạnh màu xanh hoặc một đồ thị con K 4 có tất cả các cạnh màu đỏ. Suy ra R  3, 4   9 . Vậy R  3, 4   9 . Bài toán 2.1.6 Chứng minh rằng R  3,5   14 . Chứng minh 13 13 1 2 1 2 12 12 3 3 11 11 4 4 10 10 5 5 9 9 6 8 8 7 6 7 Theo Bổ đề 2.1.3 ta có R  3,5   R  2,5   R  3,4   5  9  14 . Mặt khác, hình bên là một đồ thị gồm 13 đỉnh K13 có các cạnh được tô màu đỏ hoặc xanh (đỏ – đường nét liền; xanh – đường không nối hai đỉnh bất kì ) không chứa đồ thị con K 3 có tất cả các cạnh màu đỏ, cũng không chứa đồ thị con K 5 nào có tất cả các cạnh màu xanh. Như vậy R  3,5   13 . Vậy R  3,5   14 . 11 Bài toán 2.7 Chứng minh rằng R  4,4   18 . Chứng minh 17 1 16 17 2 1 16 2 3 3 15 15 4 4 14 14 5 13 5 13 6 6 12 12 7 11 10 9 7 11 8 10 9 8 Theo Bổ đề 2.1.3 ta có R  4,4   R  3,4   R  4,3  9  9  18 . Mặt khác hình bên là một đồ thị gồm 17 đỉnh K17 có các cạnh được tô màu đỏ hoặc xanh (đỏ–đường nét liền; xanh–đường nét đứt) không chứa đồ thị con K 4 có tất cả các cạnh màu xanh, cũng không chứa đồ thị con K 4 nào có tất cả các cạnh màu đỏ. Như vậy R  4,4   17 . Vậy R  4,4   18 . 12 3. Định lí Ramsey tổng quát Định lí 2.1.8 Cho r số tự nhiên p1, p2,..., pr . Khi ấy tồn tại số tự nhiên nhỏ nhất R  p1 , p2 ,..., pr  chỉ phụ thuộc vào các số p1, p2,..., prsao cho mọi đồ thị đầy đủ n đỉnh r màu với n  R  p1 , p2 ,..., pr  luôn tồn tại một đồ thị con đầy đủ p1 đỉnh mà tất cả các cạnh được tô màu k1 hoặc p2 đỉnh mà tất cả các cạnh được tô màu k2 hoặc ... hoặc pr đỉnh mà tất cả các cạnh được tô màu kr . Chứng minh Ta sẽ chứng minh Định lí 2.1.8 bằng phép quy nạp theo r. Với r  1: R  p1   p1 Với r  2 : Đây chính là Định lí 2.1.1 Giả sử Định lí đúng đến r  1. Ta sẽ chứng minh định lí đúng đến r . Theo giả thiết tồn tại q  R  p1 ,..., pr 1  sao cho mọi đồ thị đầy đủ q đỉnh r  1 màu luôn tồn tại một đồ thị con đầy đủ p1 đỉnh mà tất cả các cạnh được tô màu k1 hoặc p2 đỉnh mà tất cả các cạnh được tô màu k 2 ... hoặc pr 1 đỉnh mà tất cả các cạnh được tô màu kr 1 . Ta tô màu k r là màu đỏ còn các màu k1 , ..., kr 1 là màu xanh. Theo Định lí 2.1.1 tồn tại số n  R  q, pr  sao cho mọi đồ thị đầy đủ n đỉnh hai màu luôn tồn tại một đồ thị con đầy đủ q đỉnh mà tất cả các cạnh được tô màu xanh hoặc pr đỉnh mà tất cả các cạnh được tô màu đỏ. Vậy luôn tồn tại số tự nhiên R  p1 , p2 ,..., pr  sao cho mọi đồ thị đầy đủ n đỉnh 13 r màu, n  R  p1 , p2 ,..., pr  luôn tồn tại một đồ thị con đầy đủ p1 đỉnh mà tất cả các cạnh được tô màu k1 hoặc p2 đỉnh mà tất cả các cạnh được tô màu k 2 ... hoặc pr đỉnh mà tất cả các cạnh được tô màu k r . Bài toán 2.9 Chứng minh rằng R  3,3,3  17 . Chứng minh (Đồ thị Clebsch) Ta thấy trên đồ thị Clebsch có 16 đỉnh các cạnh được tô bởi 3 màu xanh, đỏ, vàng nhưng không có tam giác nào có 3 cạnh cùng màu. Suy ra R  3,3,3  16 . Bấy giờ ta xét một đồ thị đầy đủ 17 đỉnh. Các cạnh của đồ thị được tô bởi một trong ba màu xanh, đỏ, vàng. Ta cần chứng minh trong đồ thị tồn tại ba đỉnh mà các cạnh được nối với nhau bởi cùng một màu. Kí hiệu một đỉnh là A. Vì A nối với 16 đỉnh còn lại bởi ba màu nên theo nguyên tắc Dirichlet tồn tại 6 đỉnh nối với A bởi cùng một màu. Giả sử sáu đỉnh là B, C, D, E, F, G nối với A bởi màu xanh. Nếu trong sáu đỉnh có hai đỉnh nối với nhau bởi màu xanh, giả sử là B,C thìba đỉnh A,B,C được nối với nhau cùng một màu. 14 Nếu trong sáu đỉnh không có hai đỉnh nào nối với nhau bởi màu xanh. Suy ra trong 6 đỉnh B,C,D,E,F,G các cạnh được nối với nhau bởi hai màu đỏ và vàng theo bài toán 1.2.1 tồn tại ba đỉnh mà các cạnh được nối với nhau bởi một màu. Vậy trong 17 đỉnh luôn tồn tại ba đỉnh mà các cạnh được nối với nhau bởi cùng một màu. Vậy R  3,3,3  17 . §2.2 Định lí Ramsey trong tập hợp hữu hạn 1. Định lí Ramsey Giả sử S là tập hợp gồm s phần tử. Kí hiệu  r  S  là họ tất cả các tập con của S , mỗi tập có đúng r phần tử, r  1 . Ta nói họ  r  S  được phân hoạch thành hai họ các tập hợp A và B nếu A và B khác rỗng và thỏa mãn điều kiện:  r  S   A  B; A  B   . Định lí 2.2.1 (Ramsey, 1930) Giả sử họ  r  S  được phân hoạch thành hai họ các tập hợp A và B ; p và q là hai số nguyên sao cho r  p, q  s . Khi ấy tồn tại số nguyên nhỏ nhất R  p, q, r  chỉ phụ thuộc vào các số p, q, r mà không phụ thuộc vào tập S , sao cho nếu s  R  p, q, r  thì tồn tại một tập P gồm p phần tử của S , mà tất cả các tập con r phần tử của P đều thuộc A , hoặc tồn tại một tập Q gồm q phần tử của S , mà tất cả các tập con r phần tử của Q đều thuộc B . Số R  p, q, r  tìm được trong Định lí 2.2.1 được gọi là số Ramsey. Các số Ramsey rất được quan tâm vì có nhiều ứng dụng, nhưng rất khó tính được nó. Ta mới chỉ tính được một vài số Ramsey nhỏ. Thậm chí rất khó tìm ra các công thức đánh giá các số Ramsey. 15 Trong trường hợp r  2 , ta có thể phát biểu lại Định lí 2.1 dưới ngôn ngữ của lí thuyết đồ thị như sau. Giả thiết rằng s  R  p, q,2  và các cạnh của đồ thị K s đã được tô bởi hai màu đỏ hoặc xanh. Chia các cạnh của đồ thị thành hai lớp: lớp A gồm các cạnh màu đỏ và lớp B gồm các cạnh màu xanh. Định lí 2.1 nói rằng, đồ thị K s phải chứa đồ thị con K p có tất cả các cạnh màu đỏ hoặc chứa đồ thị con K q có tất cả các cạnh màu xanh. Kết quả của Bài toán 1.6có thể viết lại thành: R  3,3, 2   6 . Bổ đề 2.2.2 1) R( p, q,1)  p  q  1 ; 2) R(r, q, r )  q ; 3) R ( p, r, r )  p . Chứng minh 1) Trường hợp r  1 đưa ta trở về nguyên lí Dirichlet. Giả sử S là tập gồm s phần tử. Vì r  1 nên có tất cả s tập con một phần tử. Chia s tập con một phần tử này thành hai lớp. Nếu s  p  q  2 thì s  p  q  2   p  1   q  1 nên ta có thể chia tập hợp S thành hai lớp, lớp thứ nhất chứa nhiều nhất p  1 phần tử và lớp thứ hai chứa nhiều nhất q  1 phần tử. Nghĩa là trong cách chia này, ta không có tập nào chứa p hoặc q phần tử cả. Do đó R ( p, q,1)  p  q  2 . Nếu s  p  q thì hoặc là lớp thứ nhất chứa k1 phần tử với k1  p , hoặc nếu lớp thứ nhất chứa k1 phần tử với k1  p thì lớp thứ hai chứa k 2 phần tử với k2  s  k1   p  q   p  q . Nghĩa là hoặc lớp thứ nhất chứa tối thiểu p phần tử, hoặc lớp thứ hai chứa tối thiểu q phần tử. Nếu s  p  q  1 thì mọi phép chia tập hợp S thành hai lớp thì hoặc lớp thứ nhất chứa p  k  p phần tử, k  0 và lớp thứ hai chứa q  1  k phần tử; hoặc lớp thứ nhất chứa p  k  1 phần tử và lớp thứ hai chứa q  k  q phần tử. 16 Do đó R ( p, q,1)  p  q  1 . 2) Trường hợp p  r . Số phần tử s của tập hợp S phải ít nhất là bao nhiêu để ta có thể bảo đảm chắc chắn rằng trong S hoặc là tồn tại tập P gồm r phần tử của S mà tất cả các tập con r phần tử của P nằm trong A hoặc là tồn tại tập Q gồm q phần tử của S mà tất cả các tập con r phần tử của Q nằm trong B , trong đó A và B là một phân hoạch của  r  S  , tức là A và B là họ các tập con r phần tử và  r  S   A  B; A  B   ? Vì A   nên A phải chứa ít nhất một tập gồm r phần tử. Do p  r và r  q  s nên bắt buộc s  q (để tin tưởng chắc chắn rằng S chứa tập q phần tử). Do đó R(r, q, r )  q . 3) Trường hợp q  r . Chứng minh tương tự trường hợp p  r ta có R( p, r, r )  p . Bổ đề 2.2.2 được chứng minh. Chứng minh Định lí 2.2.1 Theo Bổ đề 2.2.2 thì Định lí 2.2.1 đúng cho r  1 . Ta chứng minh qui nạp theo r . Giả thiết rằng định lí đúng cho r  1 . Bây giờ ta lại sử dụng qui nạp theo p  q , bằng cách sử dụng khẳng định 2) và 3) của Bổ đề 2.2.2. Như vậy, theo giả thiết qui nạp, các số p1  R  p  1, q, r  và q1  R  p, q  1, r  tồn tại. Ta khẳng định rằng R ( p, q, r )  R ( p1 , q1 , r  1)  1 . Để chứng minh điều này, ta xét tập S gồm s  R ( p1 , q1 , r  1)  1 phần tử. Giả sử họ  r  S  các tập con r phần tử của S được tô bởi hai màu: đỏ và xanh. Tương tự như trong chứng minh Bài toán 1.2.1 (cho K 6 ), ta lấy ra một phần tử của S và kí hiệu nó là a . Bây giờ ta xác định các tập con tô màu r  1 phần tử của tập S  : S \   như sau: 17 Tập X  S  có r  1 phần tử được tô màu trùng với màu của X  a . Vì S có số phần tử là s  R ( p1 , q1 , r  1)  1 nên S  có số phần tử s  R( p1 , q1 , r  1). Theo giả thiết qui nạp, hoặc S  chứa tập con A có p1 phần tử sao cho mọi tập con r  1 của nó phải là màu đỏ hoặc S  chứa tập con B có q1 phần tử sao cho mọi tập con r  1 của nó phải là màu xanh. Không hạn chế tổng quát, giả sử xảy ra trường hợp 1, tức là A có p1 phần tử sao cho mọi tập con r  1 của nó có màu đỏ. Bởi vì p1  R  p  1, q, r  nên có thể có hai khả năng. Trường hợp 1 Hoặc A có tập con Q gồm q phần tử, mọi tập con r phần tử của nó có màu xanh. Bởi vì Q cũng là tập con q phần tử của S nên S chứa tập con Q gồm q phần tử, mọi tập con r phần tử của nó màu xanh. Như vậy, ta có khẳng định của định lí. Trường hợp 2 Hoặc A có tập con A gồm p  1 phần tử, mọi tập con r phần tử của nó có màu đỏ. Trong trường hợp này tập con P : A    cũng có tính chất đó, vì A  A , tức là P có p phần tử, mọi tập con r phần tử của nó có màu đỏ. Nhưng P cũng là tập con của S nên P chính là tập cần tìm. Và ta có khẳng định của định lí. Trường hợp S  chứa tập con B có q1 phần tử sao cho mọi tập con r  1 của nó phải là màu xanh được chứng minh hoàn toàn tương tự. Điều đó chứng tỏ rằng, R ( p, q, r )  R ( p1 , q1 , r  1)  1 . Định lí Ramsey được chứng minh. 18
- Xem thêm -

Tài liệu liên quan