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

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