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

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

Пример

Для 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 и 3,2
  • 3,2,1 имеет три убывающие подпоследовательности длины 2: 3,2, 3,1, и 2,1.

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

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

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

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

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

ТеоремаДилуорса