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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Ланцюг з чотирьох ребер з позитивним нахилом у множині з 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 has спадну підпослідовність 3,2
  • 2,1,3 has спадну підпослідовність 2,1
  • 2,3,1 has дві спадні підпослідовністі, 2,1 та 3,1
  • 3,1,2 has дві спадні підпослідовністі, 3,1 and 3,2
  • 3,2,1 has три спадні підпослідовністі довжини 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 антиланцюгів; але у такому випадку найбільший з антиланцюгів має утворювати спадну підпослідовність з довжиною принаймні:\left\lceil\frac{rs-r-s+2}{r-1}\right\rceil=s.

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

  1. Erdős, Paul; Szekeres, George (1935), «A combinatorial problem in geometry», Compositio Mathematica 2: 463–470, http://www.numdam.org/item?id=CM_1935__2__463_0. 
  2. а б Steele, J. Michael (1995), «Variations on the monotone subsequence theme of Erdős and Szekeres», у Aldous, David; Diaconis, Persi; Spencer, Joel та ін., Discrete Probability and Algorithms, IMA Volumes in Mathematics and its Applications, 72, Springer-Verlag, сторінки 111–131, http://www-stat.wharton.upenn.edu/~steele/Publications/PDF/VOTMSTOEAS.pdf .
  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 .
  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», Journal of the London Mathematical Society 34: 352, http://jlms.oxfordjournals.org/cgi/reprint/s1-34/3/352.pdf .

Джерела[ред.ред. код]