У математиці, теорема Ердеша—Секереша є результат про скінченні множини, що уточнює один з наслідків теореми Рамсея. Тоді як теорема Рамсея полегшує доведення того, що кожна послідовність різних дійсних чисел містить або монотонно зростаючу нескінченну підпослідовність, або монотонно спадну нескінченну підпослідовність, цей результат, доведений Паулем Ердешем та Дьйордем Секерешем іде далі. Для даних r, s вони показали, що будь-яка послідовність довжини принаймні (r − 1)(s − 1) + 1 містить або монотонно зростаючу підпослідовність довжини r, або монотонно спадну довжини s. Доведення з'явилося у той самій роботі 1935 року, що й .
Приклад
Для 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) робить огляд шести різних доведень теореми, включно з наступними двома. Other proofs surveyed by Steele include the original proof by Erdős and Szekeres as well as those of Blackwell, (1971), Hammersley, (1972), and Lovász, (1979).
Принцип Дирихле
Для даної послідовності довжини (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) і називає її «найхитрішим та найбільш систематичним» з доведень, що входять до його огляду.
Теорема Ділуорса
Ще одне з доведень використовує теорему Ділуорса щодо ланцюгових декомпозицій у часткових порядках, або її простіший двоїстий аналог ().
Для доведення теореми, визначимо частковий порядок на елементах послідовності, у якому x є меншим або дорівнює y у цьому частковому порядку якщо x ≤ y як числа та x знаходиться не пізніше y у цій послідовності. Ланцюг у цьому частковому порядку є монотонно зростаючою підпослідовністю, а антиланцюг є монотонно спадною підпослідовністю. За теоремою Мирського, існує або ланцюг довжини r, або послідовність може бути розбита на не більше як r − 1 антиланцюгів; але у такому випадку найбільший з антиланцюгів має утворювати спадну підпослідовність з довжиною принаймні:
За теоремою Ділуорса, існує або антиланцюг довжини s, або послідовність може бути розбита на не більш як s − 1 ланцюгів, найбільший з яких мусить мати довжину принаймні r.
Див. також
Посилання
- Erdős, Paul; Szekeres, George (1935), A combinatorial problem in geometry, Compositio Mathematica, 2: 463—470.
- (1995), Variations on the monotone subsequence theme of Erdős and Szekeres, у ; ; ; (ред.), Discrete Probability and Algorithms (PDF), IMA Volumes in Mathematics and its Applications, т. 72, Springer-Verlag, с. 111—131.
- 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.
- (1972), A few seedlings of research, Proc. 6th Berkeley Symp. Math. Stat. Prob., University of California Press, с. 345—394. As cited by Steele, (1995).
- Lovász, László (1979), Solution to Exercise 14.25, Combinatorial Problems and Exercises, North-Holland. As cited by Steele, (1995).
- (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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U matematici teorema Erdesha Sekeresha ye rezultat pro skinchenni mnozhini sho utochnyuye odin z naslidkiv teoremi Ramseya Todi yak teorema Ramseya polegshuye dovedennya togo sho kozhna poslidovnist riznih dijsnih chisel mistit abo monotonno zrostayuchu neskinchennu pidposlidovnist abo monotonno spadnu neskinchennu pidposlidovnist cej rezultat dovedenij Paulem Erdeshem ta Djordem Sekereshem ide dali Dlya danih r s voni pokazali sho bud yaka poslidovnist dovzhini prinajmni r 1 s 1 1 mistit abo monotonno zrostayuchu pidposlidovnist dovzhini r abo monotonno spadnu dovzhini s Dovedennya z yavilosya u toj samij roboti 1935 roku sho j Lancyug z chotiroh reber z pozitivnim nahilom u mnozhini z 17 tochok Yaksho odna utvoryuye poslidovnist y koordinat cih tochok u poryadku yihnih x koordinat teorema Erdosha Sekeresha garantuye sho isnuye abo lancyug cogo tipu abo lancyug toyi zh dovzhini u yakomu vsi nahili e 0 Prote yaksho centralna tochka vidsutnya takij lancyug ne isnuvav bi PrikladDlya r 3 ta s 2 formula govorit nam bud yake perestavlennya troh chisel maye zrostayuchu pidposlidovnist dovzhini tri abo spadnu pidposlidovnist dovzhini dva Mizh shistma perestavlennyami chisel 1 2 3 1 2 3 maye zrostayuchu pidposlidovnist dovzhini tri 1 3 2 maye spadnu pidposlidovnist 3 2 2 1 3 maye spadnu pidposlidovnist 2 1 2 3 1 maye dvi spadni pidposlidovnisti 2 1 ta 3 1 3 1 2 maye dvi spadni pidposlidovnisti 3 1 and 3 2 3 2 1 maye tri spadni pidposlidovnisti dovzhini 2 3 2 3 1 and 2 1 Geometrichna interpretaciyaPoziciyi chisel u poslidovnosti mozhna interpretuvati yak x koordinati tochok u Evklidovij ploshini i chisla yak y koordinati z inshogo boku dlya bud yakoyi mnozhini tochok na ploshini y koordinati cih tochok uporyadkovani za yih x koordinatami utvoryuyut poslidovnist chisel yaksho tilki dva chisla ne mayut dvoh odnakovih x koordinat Z takim peretvorennyam mizh poslidovnostyami ta mnozhinami tochok teorema Erdosha Sekeresha mozhe interpretuvatisya yak taka sho stverdzhuye sho u bud yakij mnozhini z prinajmni rs r s 2 tochok znajdetsya z abo r 1 rebrami z pozitivnim nahilom abo s 1 rebrami z vid yemnim nahilom Napriklad beruchi r s 5 dovilna mnozhina z prinajmni 17 tochok maye lancyug z chotiroh reber u yakomu vsi nahili mayut odnakovij znak Priklad z rs r s 1 tochok bez takogo lancyuga sho pokazuye tochnist ciyeyi ocinki utvoryuyetsya zastosuvannyam obernennya do gratki rozmiru r 1 na s 1 DovedennyaTeorema Erdosha Sekeresha mozhe buti dovedena dekilkoma riznimi sposobami Steele 1995 robit oglyad shesti riznih doveden teoremi vklyuchno z nastupnimi dvoma Other proofs surveyed by Steele include the original proof by Erdos and Szekeres as well as those of Blackwell 1971 Hammersley 1972 and Lovasz 1979 Princip Dirihle Dlya danoyi poslidovnosti dovzhini r 1 s 1 1 poznachte kozhne chislo ni v cij poslidovnosti paroyu ai bi de ai ye dovzhinoyu najdovshoyi monotonno zrostayuchoyi pidposlidovnosti sho zakinchuyetsya na ni ta bi ye dovzhinoyu najdovshoyi monotonno spadnoyi pidposlidovnosti sho zakinchuyetsya na ni Kozhni dva chisla u cij poslidovnosti poznacheni riznoyu paroyu yaksho i lt j i ni lt nj todi ai lt aj ta z inshogo boku yaksho ni gt nj todi bi lt bj Ale isnuye tilki r 1 s 1 mozhlivih poznachen u yakih ai ye ne bilshe nizh r 1 i bi ye ne bilshe nizh s 1 zvidki za principom Dirihle musit isnuvati znachennya i dlya yakogo ai abo bi poza cimi obmezhennya Yaksho ai ye poza obmezhennyam todi ni ye chastinoyu zrostayuchoyi poslidovnosti dovzhini prinajmni r ta yaksho bi ye poza obmezhennyam todi ni ye chastinoyu spadnoyi poslidovnosti dovzhini prinajmni s Steele 1995 pripisuye ce dovedennya statti z odnoyi storinki Seidenberg 1959 i nazivaye yiyi najhitrishim ta najbilsh sistematichnim z doveden sho vhodyat do jogo oglyadu Teorema Diluorsa She odne z doveden vikoristovuye teoremu Diluorsa shodo lancyugovih dekompozicij u chastkovih poryadkah abo yiyi prostishij dvoyistij analog Dlya dovedennya teoremi viznachimo chastkovij poryadok na elementah poslidovnosti u yakomu x ye menshim abo dorivnyuye y u comu chastkovomu poryadku yaksho x y yak chisla ta x znahoditsya ne piznishe y u cij poslidovnosti Lancyug u comu chastkovomu poryadku ye monotonno zrostayuchoyu pidposlidovnistyu a antilancyug ye monotonno spadnoyu pidposlidovnistyu Za teoremoyu Mirskogo isnuye abo lancyug dovzhini r abo poslidovnist mozhe buti rozbita na ne bilshe yak r 1 antilancyugiv ale u takomu vipadku najbilshij z antilancyugiv maye utvoryuvati spadnu pidposlidovnist z dovzhinoyu prinajmni r s r s 2 r 1 s displaystyle left lceil frac rs r s 2 r 1 right rceil s Za teoremoyu Diluorsa isnuye abo antilancyug dovzhini s abo poslidovnist mozhe buti rozbita na ne bilsh yak s 1 lancyugiv najbilshij z yakih musit mati dovzhinu prinajmni r Div takozhZadacha pro najdovshu zrostayuchu pidposlidovnistPosilannyaErdos Paul Szekeres George 1935 A combinatorial problem in geometry Compositio Mathematica 2 463 470 1995 Variations on the monotone subsequence theme of Erdos and Szekeres u red Discrete Probability and Algorithms PDF IMA Volumes in Mathematics and its Applications t 72 Springer Verlag s 111 131 Blackwell Paul 1971 An alternative proof of a theorem of Erdos and Szekeres American Mathematical Monthly 78 3 273 273 doi 10 2307 2317525 JSTOR 2317525 1972 A few seedlings of research Proc 6th Berkeley Symp Math Stat Prob University of California Press s 345 394 As cited by Steele 1995 Lovasz Laszlo 1979 Solution to Exercise 14 25 Combinatorial Problems and Exercises North Holland As cited by Steele 1995 1959 A simple proof of a theorem of Erdos and Szekeres PDF Journal of the London Mathematical Society 34 352 DzherelaWeisstein Eric W Erdos Szekeres Theorem angl na sajti Wolfram MathWorld