Теорема Эрдеша – Секереса - Erdős–Szekeres theorem

Путь из четырех наклонных вверх ребер в наборе из 17 точек. По теореме Эрдеша – Секереса каждый набор из 17 точек имеет путь такой длины, который идет либо вверх, либо вниз. Подмножество из 16 точек с удаленной центральной точкой не имеет такого пути.

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

Пример

За р = 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.

Альтернативные интерпретации

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

Положение чисел в последовательности можно интерпретировать как Икс-координаты точек в Евклидова плоскость, а сами числа как у-координаты; и наоборот, для любой точки, установленной на плоскости, у-координаты точек, упорядоченные по их Икс-координаты, образует последовательность чисел (если две точки не имеют равных Икс-координаты). При таком переводе между последовательностями и точечными наборами теорему Эрдеша – Секереса можно интерпретировать как утверждающую, что в любом наборе по крайней мере RS − р − s + 2 балла мы можем найти многоугольный путь либо р - 1 ребро с положительным уклоном или s - 1 кромка с отрицательным уклоном. В частности (принимая р = s), в любом наборе не менее п точек мы можем найти многоугольный путь не менее ⌊√п-1⌋ кромки с наклонами одного знака. Например, взяв р = s = 5, любой набор из не менее 17 точек имеет путь с четырьмя ребрами, все склоны которого имеют одинаковый знак.

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

Интерпретация шаблона перестановки

Теорема Эрдеша – Секереша также может быть интерпретирована на языке шаблоны перестановок как утверждая, что каждая перестановка длины не менее RS + 1 должен содержать либо образец 1, 2, 3, ..., р + 1 или узор s + 1, s, ..., 2, 1.

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

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

Принцип голубятни

Учитывая последовательность длины (р − 1)(s - 1) + 1, обозначить каждое число п_я в последовательности с парой (а_я,б_я), куда а_я - длина самой длинной монотонно возрастающей подпоследовательности, оканчивающейся на п_я и б_я - длина самой длинной монотонно убывающей подпоследовательности, оканчивающейся на п_я. Каждые два числа в последовательности помечены разными парами: если я < j и п_я ≤ п_j тогда а_я < а_j, а с другой стороны, если п_я ≥ п_j тогда б_я < б_j. Но есть только (р − 1)(s - 1) возможные метки, если а_я самое большее р - 1 и б_я самое большее s - 1, так что по принцип голубятни должно существовать значение я для которого а_я или же б_я находится за пределами этого диапазона. Если а_я вне диапазона тогда п_я является частью возрастающей последовательности длиной не менее р, и если б_я вне диапазона тогда п_я является частью убывающей последовательности длиной не менее s.

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

Теорема Дилворта

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

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

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

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

Применение корреспонденции Робинсона – Шенстеда

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

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

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

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

Смотрите также

• Задача самой длинной возрастающей подпоследовательности

Рекомендации

1. Эрдеш, Пол; Секерес, Джордж (1935), «Комбинаторная задача геометрии», Compositio Mathematica, 2: 463–470, Дои:10.1007/978-0-8176-4842-8_3, Zbl  0012.27010.
2. Стил, Дж. Майкл (1995), "Вариации на монотонную тему подпоследовательности Эрдеша и Секереша", в Олдос, Дэвид; Диаконис, Перси; Спенсер, Джоэл; Стил, Дж. Майкл (ред.), Дискретная вероятность и алгоритмы (PDF), Объемы IMA по математике и ее приложениям, 72, Springer-Verlag, стр. 111–131, ISBN  0-387-94532-6.
3. Блэквелл, Пол (1971), "Альтернативное доказательство теоремы Эрдеша и Секереша", Американский математический ежемесячный журнал, 78 (3): 273–273, Дои:10.2307/2317525, JSTOR  2317525.
4. Хаммерсли, Дж. М. (1972), «Несколько саженцев исследований», Proc. 6-й симпозиум в Беркли. Математика. Стат. Вероятность., University of California Press, стр. 345–394.. Как цитирует Стил (1995).
5. Ловас, Ласло (1979), «Решение упражнения 14.25», Комбинаторные задачи и упражнения, Северная Голландия. Как цитирует Стил (1995).
6. Зайденберг, А. (1959), «Простое доказательство теоремы Эрдеша и Секереша» (PDF), Журнал Лондонского математического общества, 34: 352, Дои:10.1112 / jlms / s1-34.3.352.

внешняя ссылка

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