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

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

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

Пример

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

• 123 имеет возрастающую подпоследовательность длиной три;
• 132 имеет убывающую подпоследовательность 32;
• 213 имеет убывающую подпоследовательность 21;
• 231 имеет две убывающие подпоследовательности: 21 и 31;
• 312 имеет две убывающие подпоследовательности: 31 и 32;
• 321 имеет три убывающие подпоследовательности длины два: 32, 31, и 21.

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

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

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

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

Доказательство через принцип Дирихле

Основная статья: Принцип Дирихле

В последовательности длины ${\displaystyle (r-1)(s-1)+1}$ пометим каждое число ${\displaystyle n_{i}}$ парой ${\displaystyle (a_{i},b_{i})}$, где ${\displaystyle a_{i}}$ — длина наибольшей монотонно возрастающей подпоследовательности, заканчивающейся на ${\displaystyle n_{i}}$, ${\displaystyle b_{i}}$ длина наибольшей монотонно убывающей подпоследовательности, заканчивающейся на ${\displaystyle n_{i}}$. Все числа в последовательности помечены различными парами: если ${\displaystyle i<j}$ и ${\displaystyle n_{i}\leq n_{j}}$, то ${\displaystyle a_{i}<a_{j}}$; если ${\displaystyle n_{i}\geq n_{j}}$, то ${\displaystyle b_{i}<b_{j}}$. Но есть всего ${\displaystyle (r-1)(s-1)}$ возможных пар, если ${\displaystyle a_{i}\leq r-1}$, а ${\displaystyle b_{i}\leq s-1}$, так что по принципу Дирихле существует ${\displaystyle i}$, для которого ${\displaystyle a_{i}}$ или ${\displaystyle b_{i}}$ выходит за пределы этого ограничения. Если ${\displaystyle a_{i}}$ выходит за пределы, то ${\displaystyle n_{i}}$ — часть возрастающей подпоследовательности длины не меньше ${\displaystyle r}$, если ${\displaystyle b_{i}}$ выходит за пределы, то ${\displaystyle n_{i}}$ — часть убывающей подпоследовательности длины не меньше ${\displaystyle s}$.

См. также

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

Примечания

1. Erdős, Paul; Szekeres, George (1935), A combinatorial problem in geometry, Compositio Mathematica, 2: 463–470, Архивировано из оригинала 19 февраля 2019, Дата обращения: 13 июля 2011.
2. Steele, J. Michael (1995), Variations on the monotone subsequence theme of Erdős and Szekeres, in Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (eds.), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications, vol. 72, Springer-Verlag, pp. 111–131, Архивировано из оригинала (PDF) 11 июня 2019, Дата обращения: 13 июля 2011.
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, pp. 345–394.
5. Lovász, László (1979), Solution to Exercise 14.25, Combinatorial Problems and Exercises, North-Holland.
6. Комбинаторная теория, 1982, с. 514.

Источники

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

Литература

• Айгнер М. Комбинаторная теория. — М.: Мир, 1982. — 555 с.