|
|
Erdos-Szekeres type theorems
Eliáš, Marek ; Matoušek, Jiří (vedoucí práce) ; Cibulka, Josef (oponent)
Nech P = (p1, p2, . . . , pN ) je postupnosť bodov v rovine, kde pi = (xi, yi) a x1 < x2 < · · · < xN . Slávna Erdős-Szekeresova veta z roku 1935 hovorí, že každá taká postupnosť P obsahuje monotónnu podpostupnosť S dĺžky√ N . Iná, podobne slávna veta z toho istého článku hovorí, že každá taká po- stupnosť P obsahuje konvexnú alebo konkávnu podpostupnosť dĺžky Ω(log N). Najprv definujeme (k + 1)-ticu K ⊆ P ako pozitívnu, keď leží na grafe funkcie s nezápornou k-tou deriváciou a podobne tiež negatívnu (k + 1)-ticu. Ďalej hovoríme, že S ⊆ P je monotónna k-teho rádu, keď jej (k + 1)-tice sú buďto všetky pozitívne alebo všetky negatívne. V tejto práci skúmame kvantitatívne odhady pre zodpovedajúce Ramseyovské funkcie. Dostávame Ω(log(k−1) N) ako dolný odhad. Taktiež uvádzame vylepšené odhady pre súvisiace problémy ako Order types a One-sided sets of hyperplanes. 1
|
host ::
RSS.