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

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

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

Пример

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

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

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

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

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

Теорема Эрдёша — Секереша может быть доказана несколькими разными способами. Майкл Стил дает обзор шести разных доказательств теоремы, в том числе с использованием принципа Дирихле и теоремы Дилуорса. Прочие способы доказательства, приводимые Стилом, включают оригинальное доказательство Эрдёша и Секереша и доказательство Блэквелла, Ловаса и самого Стила.Доказательство также есть в книгеШаблон:Sfn.

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

Шаблон:MainВ последовательности длины $(r-1)(s-1)+1$ пометим каждое число $n_i$ парой $(a_i,b_i)$, где $a_i$ — длина наибольшей монотонно возрастающей подпоследовательности, заканчивающейся на $n_i$, $b_i$ длина наибольшей монотонно убывающей подпоследовательности, заканчивающейся на $n_i$. Все числа в последовательности помечены различными парами: если $i<j$ и $n_i\le n_j$, то $a_i<a_j$; если $n_i\ge n_j$, то $b_i<b_j$. Но есть всего $(r-1)(s-1)$ возможных пар, если $a_i\le r-1$, а $b_i\le s-1$, так что по принципу Дирихле существует $i$, для которого $a_i$ или $b_i$ выходит за пределы этого ограничения. Если $a_i$ выходит за пределы, то $n_i$ — часть возрастающей подпоследовательности длины не меньше $r$, если $b_i$ выходит за пределы, то $n_i$ — часть убывающей подпоследовательности длины не меньше $s$.

См. также

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

Источники

• Шаблон:Mathworld

Литература

• Шаблон:Книга