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

В математике теорема Эрдёша -Секереша утверждает, что при заданных r , s любая последовательность различных действительных чисел с длиной не менее ( r  − 1)( s  − 1) + 1 содержит монотонно возрастающую подпоследовательность длины  r или монотонно убывающую подпоследовательность длины  s . Доказательство появилось в той же статье 1935 года, в которой упоминается проблема Happy Ending . ^[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 и 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 ), в любом наборе из по крайней мере n точек мы можем найти многоугольный путь из по крайней мере ⌊ √ n -1 ⌋ ребер с наклонами одного знака. Например, если r  =  s  = 5, то любой набор из не менее 17 точек имеет четырехреберный путь, в котором все наклоны имеют одинаковый знак.

Пример rs  −  r  −  s  + 1 точек без такого пути, показывающий, что эта граница тесна, можно получить, применив небольшой поворот к сетке ( r  − 1) на ( s  − 1).

Теорему Эрдёша–Секереша можно также интерпретировать на языке шаблонов перестановок как утверждение, что каждая перестановка длины не менее ( r  - 1)( s  - 1) + 1 должна содержать либо шаблон 12⋯ r , либо шаблон s ⋯21.

Теорему Эрдёша–Секереша можно доказать несколькими различными способами; Стил (1995) рассматривает шесть различных доказательств теоремы Эрдёша–Секереша, включая следующие два. ^[2] Другие доказательства, рассмотренные Стилом, включают оригинальное доказательство Эрдёша и Секереша, а также доказательства Блэквелла (1971), ^[3], Хаммерсли (1972), ^[4] и Ловаса (1979). ^[5]

Дана последовательность длины ( r  − 1)( s  − 1) + 1, обозначим каждое число n _i в последовательности парой ( a _i , b _i ), где a _i — длина самой длинной монотонно возрастающей подпоследовательности, заканчивающейся на n _{i ,} а b _i — длина самой длинной монотонно убывающей подпоследовательности, заканчивающейся на n _i . Каждые два числа в последовательности обозначим другой парой: если i < j и n _i < n _{j ,} то a _i < a _j , и с другой стороны, если n _i > n _{j ,} то b _i < b _j . Но существует только ( r  − 1)( s  − 1) возможных меток, если a _i не больше r  − 1 и b _i не больше s  − 1, поэтому по принципу ящика должно существовать значение i, для которого a _i или b _i находятся вне этого диапазона. Если a _i находится вне диапазона, то n _i является частью возрастающей последовательности длиной не менее r , а если b _i находится вне диапазона, то n _i является частью убывающей последовательности длиной не менее s .

Стил (1995) приписывает это доказательство одностраничной статье Зайденберга (1959) и называет его «самым гладким и систематическим» из рассмотренных им доказательств. ^{[2] [6]}

Другое доказательство использует теорему Дилворта о цепных разложениях в частичных порядках или ее более простую двойственную теорему ( теорему Мирского ).

Чтобы доказать теорему, определим частичный порядок на членах последовательности, в котором x меньше или равен y в частичном порядке, если x  ≤  y как числа и x не позже y в последовательности. Цепь в этом частичном порядке является монотонно возрастающей подпоследовательностью, а антицепь является монотонно убывающей подпоследовательностью. По теореме Мирского либо существует цепь длины r , либо последовательность может быть разбита не более чем на r  − 1 антицепей; но в этом случае наибольшая из антицепей должна образовывать убывающую подпоследовательность длиной не менее

${\displaystyle \left\lceil {\frac {rs-r-s+2}{r-1}}\right\rceil =s.}$

В качестве альтернативы, согласно теореме Дилворта, либо существует антицепь длины s , либо последовательность можно разбить не более чем на s  − 1 цепей, самая длинная из которых должна иметь длину не менее  r .

Результат также может быть получен как следствие соответствия Робинсона–Шенстеда .

Напомним, что соответствие Робинсона–Шенстеда сопоставляет каждой последовательности таблицу Юнга P, элементы которой являются значениями последовательности. Таблица P обладает следующими свойствами:

• Длина самой длинной возрастающей подпоследовательности равна длине первой строки P.
• Длина самой длинной убывающей подпоследовательности равна длине первого столбца P.

Теперь невозможно разместить ( r  − 1)( s  − 1) + 1 записей в квадратном поле размером ( r  − 1)( s  − 1) так, чтобы либо первая строка имела длину не менее r , либо последняя строка имела длину не менее s .

• Проблема наибольшей возрастающей подпоследовательности

• Вайсштейн, Эрик В. , «Теорема Эрдеша-Секереша», MathWorld