Định lý Erdős–Szekeres

Bách khoa toàn thư mở Wikipedia
Một cung gồm bốn đoạn thẳng với hệ số góc dương trong một tập hợp 17 điểm. Nếu ta xét dãy các tọa độ y của các điểm theo thứ tự tọa độ x tăng dần, định lý Erdős–Szekeres đảm bảo rằng tồn tại một dãy không giảm như thế hoặc một dãy không tăng cùng độ dài 4. Tuy nhiên nếu điểm chính giữa bị loại đi thì không tồn tại dãy nào như vậy.

Trong toán học, định lý Erdős–Szekeres là một kết quả lượng hóa một hệ quả của định lý Ramsey. Theo định lý Ramsey, một dãy vô hạn số thực khác nhau luôn chứa hoặc một dãy con tăng vô hạn, hoặc một dãy con giảm vô hạn. Định lý của Paul Erdős và George Szekeres làm rõ hơn mối liên hệ giữa độ dài các dãy. Với mọi r, s, họ chứng minh rằng mọi dãy số với độ dài (r − 1)(s − 1) + 1 tồn tại hoặc một dãy con không giảm có độ dài r, hoặc một dãy con không tăng có độ dài s. Chứng minh nằm trong cùng bài báo năm 1935 của họ đề cập đến bài toán kết thúc có hậu.[1]

Ví dụ[sửa | sửa mã nguồn]

Với r = 3 và s = 2, công thức cho thấy một dãy 3 số nguyên khác nhau luôn chứa một dãy con tăng độ dài 3 hoặc một dãy con giảm độ dài 2. Trong sáu hoán vị của 1,2,3:

  • 1,2,3 có một dãy con tăng gồm cả ba số
  • 1,3,2 có một dãy con giảm 3,2
  • 2,1,3 có một dãy con giảm 2,1
  • 2,3,1 có hai dãy con giảm 2,1 và 3,1
  • 3,1,2 có hai dãy con giảm 3,1 và 3,2
  • 3,2,1 có ba dãy con giảm độ dài 2 là 3,2; 3,1, và 2,1.

Ý nghĩa hình học[sửa | sửa mã nguồn]

Ta có thể xem thứ tự của các số trong dãy là tọa độ x của các điểm trên mặt phẳng Euclid, và giá trị các số là tọa độ y; ngược lại, với mọi tập hợp các điểm trên mặt phẳng, tọa độ y của các điểm, sắp xếp theo thứ tự tọa độ x tăng dần, tạo thành một dãy số (trừ phi có hai điểm với cùng tọa độ x). Với ánh xạ giữa dãy số và tập hợp điểm như trên, định lý Erdős–Szekeres có thể được hiểu là với mọi tập hợp rs − r − s + 2 điểm luôn tồn tại một đường đa giác gồm hoặc r − 1 đoạn thẳng với hệ số góc không âm hoặc s − 1 đoạn thẳng với hệ số góc không dương. Chẳng hạn, với r = s = 5, mọi tập hợp 17 điểm luôn chứa một đường gồm 4 đoạn thẳng với hệ số góc cùng dấu.

Một ví dụ của rs − r − s + 1 không chứa một đường như vậy, và cho thấy định lý này là chặt, là một lưới với kích thước hai chiều là (r − 1) và (s − 1) được quay đi một chút.

Chứng minh[sửa | sửa mã nguồn]

Có nhiều cách chứng minh định lý Erdős–Szekeres; Steele (1995) liệt kê 6 cách chứng minh định lý Erdős–Szekeres, trong đó có hai cách dưới đây.[2] Các chứng minh khác được Steele liệt kê bao gồm chứng minh đầu tiên của Erdős và Szekeres và các chứng minh của Blackwell (1971),[3] Hammersley (1972),[4] và Lovász (1979).[5]

Chứng minh bằng nguyên lý Dirichlet[sửa | sửa mã nguồn]

Xét một dãy gồm (r − 1)(s − 1) + 1 số khác nhau. Ứng với mỗi số ni trong dãy, ta xác định một cặp số (ai,bi), trong đó ai là độ dài dãy con tăng dài nhất kết thúc ở ni và bi là độ dài dãy con giảm dài nhất kết thúc ở ni. Hai số khác nhau trong dãy ứng với hai cặp số khác nhau: nếu i < j và ni < nj thì ai < aj, mặt khác nếu ni > nj thì bi < bj. Nhưng chỉ có (r − 1)(s − 1) cặp số với ai không quá r − 1 và bi không quá s − 1, nên theo nguyên lý Dirichlet tồn tại số thứ tự i sao cho ai hoặc bi nằm ngoài khoảng này. Nếu ai nằm ngoài khoảng thì ni là số cuối trong một dãy con tăng độ dài r, và nếu bi nằm ngoài khoảng thì ni là số cuối trong một dãy con giảm độ dài s.

Theo Steele (1995), chứng minh này là của Seidenberg (1959) và gọi nó là "chứng minh đẹp nhất và hệ thống nhất" trong các chứng minh ông liệt kê.[2][6]

Chứng minh bằng định lý Dilworth[sửa | sửa mã nguồn]

Một chứng minh khác sử dụng định lý Dilworth về phân tích chuỗi trong một quan hệ thứ tự hoặc đối ngẫu của nó là định lý Mirsky.

Ta xác định một quan hệ thứ tự giữa các số trong dãy: x là nhỏ hơn hoặc bằng y trong quan hệ thứ tự nếu x ≤ y về giá trị và x không nằm sau y trong dãy. Mỗi chuỗi theo thứ tự này là một dãy đơn điệu tăng và một phản chuỗi là một dãy đơn điệu giảm. Theo định lý Mirsky, hoặc tồn tại một chuỗi độ dài r, hoặc dãy có thể được chia thành r − 1 phản chuỗi; nhưng trong trường hợp đó phản chuỗi dài nhất tạo thành một dãy con giảm với độ dài ít nhất

Một lập luận khác, thông qua định lý Dilworth, là như sau: hoặc tồn tại một phản chuỗi độ dài s, hoặc dãy có thể được chia thành ít nhất s − 1 chuỗi, độ dài của chuỗi dài nhất là ít nhất r.

Xem thêm[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Erdős, Paul; Szekeres, George (1935), “A combinatorial problem in geometry”, Compositio Mathematica, 2: 463–470.Quản lý CS1: nhiều tên: danh sách tác giả (liên kết)
  2. ^ a b Steele, J. Michael (1995), “Variations on the monotone subsequence theme of Erdős and Szekeres”, trong Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (biên tập), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications, 72, Springer-Verlag, tr. 111–131.
  3. ^ Blackwell, Paul (1971), “An alternative proof of a theorem of Erdős and Szekeres”, American Mathematical Monthly, 78 (3): 273–273, doi:10.2307/2317525, JSTOR 2317525.
  4. ^ Hammersley, J. M. (1972), “A few seedlings of research”, Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, tr. 345–394. Theo trích dẫn của Steele (1995).
  5. ^ Lovász, László (1979), “Solution to Exercise 14.25”, Combinatorial Problems and Exercises, North-Holland. Theo trích dẫn của Steele (1995).
  6. ^ Seidenberg, A. (1959), “A simple proof of a theorem of Erdős and Szekeres” (PDF), Journal of the London Mathematical Society, 34: 352.

Liên kết ngoài[sửa | sửa mã nguồn]

Lấy từ “https://vi.wikipedia.org/w/index.php?title=Định_lý_Erdős–Szekeres&oldid=62867993”