Теорема Ердеша — Секереша

Ланцюг з чотирьох ребер з позитивним нахилом у множині з 17 точок. Якщо одна утворює послідовність y-координат цих точок, у порядку їхніх x-координат, теорема Ердьоша-Секереша гарантує, що існує або ланцюг цього типу або ланцюг тої ж довжини, у якому всі нахили э ≤ 0. Проте, якщо центральна точка відсутня, такий ланцюг не існував би.

У математиці, теорема Ердеша—Секереша є результат про скінченні множини, що уточнює один з наслідків теореми Рамсея. Тоді як теорема Рамсея полегшує доведення того, що кожна послідовність різних дійсних чисел містить або монотонно зростаючу нескінченну підпослідовність, або монотонно спадну нескінченну підпослідовність, цей результат, доведений Паулем Ердешем та Дьйордем Секерешем іде далі. Для даних 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 and 3,2
  • 3,2,1 має три спадні підпослідовністі довжини 2, 3,2, 3,1, and 2,1.

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

Позиції чисел у послідовності можна інтерпретувати як x координати точок у Евклідовій площині, і числа як y-координати; з іншого боку, для будь-якої множини точок на площині, y-координати цих точок, упорядковані за їх x-координатами, утворюють послідовність чисел (якщо тільки два числа не мають двох однакових x-координат). З таким перетворенням між послідовностями та множинами точок, теорема Ердьоша-Секереша може інтерпретуватися як така, що стверджує, що у будь-якій множині з принаймні rs − r − s + 2 точок знайдеться полігональний ланцюг з або r − 1 ребрами з позитивним нахилом або s − 1 ребрами з від'ємним нахилом. Наприклад, беручи r = s = 5, довільна множина з принаймні 17 точок має ланцюг з чотирьох ребер, у якому всі нахили мають однаковий знак.

Приклад з rs − r − s + 1 точок без такого ланцюга, що показує точність цієї оцінки, утворюється застосуванням обернення до ґратки розміру (r − 1) на (s − 1).

Доведення

Теорема Ердьоша-Секереша може бути доведена декількома різними способами; Steele, (1995) робить огляд шести різних доведень теореми, включно з наступними двома.[2] Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell, (1971),[3] Hammersley, (1972),[4] and Lovász, (1979).[5]

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

Для даної послідовності довжини (r − 1)(s − 1) + 1, позначте кожне число ni в цій послідовності парою (ai,bi), де ai є довжиною найдовшої монотонно зростаючої підпослідовності, що закінчується на ni та bi є довжиною найдовшої монотонно спадної підпослідовності, що закінчується на ni. Кожні два числа у цій послідовності позначені різною парою: якщо i < j і ni < nj тоді ai < aj, та з іншого боку якщо ni > nj тоді bi < bj. Але існує тільки (r − 1)(s − 1) можливих позначень, у яких ai є не більше ніж r − 1 і bi є не більше ніж s − 1, звідки за принципом Діріхле мусить існувати значення i для якого ai або bi поза цими обмеження. Якщо ai є поза обмеженням, тоді ni є частиною зростаючої послідовності довжини принаймні r, та якщо bi є поза обмеженням, тоді ni є частиною спадної послідовності довжини принаймні s.

Steele, (1995) приписує це доведення статті з одної сторінки Seidenberg, (1959) і називає її «найхитрішим та найбільш систематичним» з доведень, що входять до його огляду.[2][6]

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

Ще одне з доведень використовує теорему Ділуорса щодо ланцюгових декомпозицій у часткових порядках, або її простіший двоїстий аналог (теорему Мирського).

Для доведення теореми, визначимо частковий порядок на елементах послідовності, у якому x є меншим або дорівнює y у цьому частковому порядку якщо x ≤ y як числа та x знаходиться не пізніше y у цій послідовності. Ланцюг у цьому частковому порядку є монотонно зростаючою підпослідовністю, а антиланцюг є монотонно спадною підпослідовністю. За теоремою Мирського, існує або ланцюг довжини r, або послідовність може бути розбита на не більше як r − 1 антиланцюгів; але у такому випадку найбільший з антиланцюгів має утворювати спадну підпослідовність з довжиною принаймні:

За теоремою Ділуорса, існує або антиланцюг довжини s, або послідовність може бути розбита на не більш як s − 1 ланцюгів, найбільший з яких мусить мати довжину принаймні r.

Див. також

Посилання

  1. ↑ Erdős, Paul; Szekeres, George (1935), A combinatorial problem in geometry, Compositio Mathematica, 2: 463—470.
  2. ↑ а б Steele, J. Michael (1995), Variations on the monotone subsequence theme of Erdős and Szekeres, у Aldous, David; Diaconis, Persi; Spencer, Joel; Steele, J. Michael (ред.), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications, т. 72, Springer-Verlag, с. 111—131.
  3. ↑ Blackwell, Paul (1971), An alternative proof of a theorem of Erdős and Szekeres, American Mathematical Monthly, 78 (3): 273—273, doi:10.2307/2317525, JSTOR 2317525.
  4. ↑ Hammersley, J. M. (1972), A few seedlings of research, Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, с. 345—394. As cited by Steele, (1995).
  5. ↑ Lovász, László (1979), Solution to Exercise 14.25, Combinatorial Problems and Exercises, North-Holland. As cited by Steele, (1995).
  6. ↑ Seidenberg, A. (1959), A simple proof of a theorem of Erdős and Szekeres (PDF), Journal of the London Mathematical Society, 34: 352.

Джерела

  • Weisstein, Eric W. Erdős-Szekeres Theorem(англ.) на сайті Wolfram MathWorld.