Định lý Erdős–Szekeres

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.
Ví dụ.
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:
Ý nghĩa hình học.
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.
Có nhiều cách chứng minh định lý Erdős–Szekeres; liệt kê 6 cách chứng minh định lý Erdős–Szekeres, trong đó có hai cách dưới đây. 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 , , và .
Chứng minh bằng nguyên lý Dirichlet.
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 và thì , mặt khác nếu thì . 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 , chứng minh này là của 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ê.
Chứng minh bằng định lý Dilworth.
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".