Теорема Эрдёша-Секереша

Цепь из четырёх рёбер с положительным наклоном на множестве из 17 точек. Если образовать последовательность y-координат этих точек, в порядке их x-координат, теорема Эрдёша-Секереша гарантирует, что существует либо цепь такого типа, либо цепь той же длины, в которой все наклоны отрицательны. Однако, если центральная точка отсутствует, такая цепь не существовала бы.

В математике теорема Эрдёша-Секереша уточняет одно из следствий теоремы Рамсея для финитного случая. В то время как теорема Рамсея облегчает доказательство того, что каждая последовательность разных действительных чисел содержит или монотонно возрастающую бесконечную подпоследовательность, или монотонно убывающую бесконечную подпоследовательность, этот результат, доказанный Полом Эрдёшем и Дьёрдем (Джорджем) Секерешем, идёт дальше. Для данных r, s они показали, что любая последовательность длины по крайней мере (r-1)(s-1)+1 содержит или монотонно возрастающую подпоследовательность длины r, или монотонно убывающую длины s. Доказательство появилось в той же самой работе 1935 года, что и задача о счастливом конце.^[1]

Пример

Для r=3 и s=2, формула говорит, что любая перестановка трёх чисел имеет возрастающую подпоследовательность длиной три или убывающую подпоследовательность длиной два. Из шести перестановок чисел 1,2,3:

• 1,2,3 имеет возрастающую подпоследовательность длиной три
• 1,3,2 имеет убывающую подпоследовательность 3,2
• 2,1,3 имеет убывающую подпоследовательность 2,1
• 2,3,1 имеет две убывающие подпоследовательности, 2,1 и 3,1
• 3,1,2 имеет две убывающие подпоследовательности, 3,1 and 3,2
• 3,2,1 имеет три убывающие подпоследовательности длины 2, 3,2, 3,1, и 2,1.

Геометрическая интерпретация

Позиции чисел в последовательности можно интерпретировать как x-координаты точек в евклидовой плоскости, а сами числа как y-координаты; с другой стороны, для любого множества точек в плоскости, y-координаты этих точек, упорядоченные по их x-координатам, образуют последовательность чисел (если только два числа не имеют двух одинаковых x-координат). При такой связи между последовательностями и множествами точек, теорему Эрдёша-Секереша можно интерпретировать как утверждение, что в любом множестве с по крайней мере rs - r - s + 2 точек найдётся ломаная либо из r - 1 положительно наклоненных отрезков, либо из s - 1 отрезков с отрицательным наклоном. Например, при r = s = 5 произвольное множество с по крайней мере 17 точками имеет цепь из четырёх рёбер, в котором все наклоны имеют одинаковый знак.

Доказательство

Теорема Эрдёша-Секереша может быть доказана несколькими разными способами; Майкл Стил дает обзор шести разных доказательств теоремы, в том числе с использованием принципа Дирихле и теоремы Дилворта.^[2] Прочие способы доказательства, приводимые Стилом, включают оригинальное доказательство Эрдёша и Секереша и доказательство Блэквелла, Ловаса и самого Стила.^{[3] [4][5]}

Принцип Дирихле

Теорема Дилворта

См. также

• Задача поиска наибольшей увеличивающейся подпоследовательности

Примечания

1. ↑ Erdős, Paul; Szekeres, George (1935), "A combinatorial problem in geometry", Compositio Mathematica Т. 2: 463–470, <http://www.numdam.org/item?id=CM_1935__2__463_0> 
2. ↑ Steele, J. Michael (1995), "Variations on the monotone subsequence theme of Erdős and Szekeres", in Aldous, David; Diaconis, Persi & Spencer, Joel et al., Discrete Probability and Algorithms, vol. 72, IMA Volumes in Mathematics and its Applications, Springer-Verlag, pp. 111–131, <http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf> .
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 .
4. ↑ Hammersley, J. M. (1972), "A few seedlings of research", Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, pp. 345–394 .
5. ↑ Lovász, László (1979), "Solution to Exercise 14.25", Combinatorial Problems and Exercises, North-Holland .

Источники

• Weisstein, Eric W. Erdős-Szekeres Theorem (англ.) на сайте Wolfram MathWorld.