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

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

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

Пример

Для ${\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}$.

См. также

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