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

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

В математике теорема Эрдеша-Секереша утверждает, что при заданных r , s любая последовательность различных действительных чисел длиной не менее ( r - 1) ( s - 1) + 1 содержит монотонно возрастающую подпоследовательность длины r или монотонно убывающую подпоследовательность. подпоследовательность длины s . Доказательство появилось в той же статье 1935 года, где упоминается проблема счастливого конца . ^{[ 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.

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

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

Положения чисел в последовательности можно интерпретировать как х -координаты точек евклидовой плоскости , а сами числа — как y -координаты; и наоборот, для любого набора точек на плоскости координаты y точек, упорядоченные по их координатам x , образуют последовательность чисел (если только две точки не имеют равные координаты x ). С помощью этого перевода между последовательностями и множествами точек теорему Эрдеша – Секереша можно интерпретировать как утверждение, что в любом наборе, состоящем не менее чем из rs − r − s + 2 точек, мы можем найти ломаный путь либо из r − 1 ребер с положительным наклоном, либо из 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 антицепь; но в этом случае наибольшая из антицепей должна образовывать убывающую подпоследовательность длиной не менее

\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 .

См. также

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

Ссылки

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

Внешние ссылки

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

[1] Эрдос, Пол ; Секерес, Джордж (1935), «Комбинаторная задача в геометрии» , Compositio Mathematica , 2 : 463–470, doi : 10.1007/978-0-8176-4842-8_3 , ISBN 978-0-8176-4841-1 , Збл 0012.27010 .

[steele-2] Jump up to: ^а ^б Стил, Дж. Майкл (1995), «Вариации на тему монотонной последовательности Эрдеша и Секереса», у Олдоса, Дэвида ; Диаконис, Персия ; Спенсер, Джоэл ; Стил, Дж. Майкл (ред.), Дискретная вероятность и алгоритмы (PDF) , Тома IMA по математике и ее приложениям, том. 72, Springer-Verlag, стр. 111–131, ISBN. 0-387-94532-6 .

[3] Блэквелл, Пол (1971), «Альтернативное доказательство теоремы Эрдеша и Секереша», American Mathematical Monthly , 78 (3): 273, doi : 10.2307/2317525 , JSTOR 2317525 .

[4] Хаммерсли, Дж. М. (1972), «Несколько саженцев исследований», Proc. 6-й симпозиум Беркли. Математика. Стат. Проб. , University of California Press, стр. 345–394 . Цитируется Стилом (1995) .

[5] Ловас, Ласло (1979), «Решение упражнения 14.25», Комбинаторные задачи и упражнения , Северная Голландия . Цитируется Стилом (1995) .

[6] Зайденберг, А. (1959), «Простое доказательство теоремы Эрдеша и Секереша», Журнал Лондонского математического общества , 34 (3): 352, doi : 10.1112/jlms/s1-34.3.352

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]