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

10.01.2016 19:33

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

У математицітеорема Ердеша—Секереша є результат про скінченні множини, що уточнює один знаслідків теореми Рамсея. Тоді як теорема Рамсея полегшує доведення того, що кожна послідовність різних дійсних чисел містить або монотонно зростаючу нескінченну підпослідовністьабо монотонно спадну нескінченну підпослідовність, цей результат, доведений Паулем Ердешем та Джорджем Секерешем іде далі. Для даних rs вони показали, що будь-яка послідовність довжини принаймні (r − 1)(s − 1) + 1 містить або монотонно зростаючу підпослідовність довжини rабо монотонно спадну довжини s. Доведення з’явилося у той самій роботі 1935 року, що й Задача про щасливий кінець.

Для 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).