Original title:
Erdos-Szekeres type theorems
Translated title:
Erdos-Szekeres type theorems
Authors:
Eliáš, Marek ; Matoušek, Jiří (advisor) ; Cibulka, Josef (referee) Document type: Master’s theses
Year:
2012
Language:
eng Abstract:
[eng][cze] Let P = (p1, p2, . . . , pN ) be a sequence of points in the plane, where pi = (xi, yi) and x1 < x2 < · · · < xN . A famous 1935 Erdős-Szekeres theorem asserts that every such P contains a monotone subsequence S of √ N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log N) points. First we define a (k + 1)-tuple K ⊆ P to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k + 1)-tuple. Then we say that S ⊆ P is kth-order monotone if its (k + 1)- tuples are all positive or all negative. In this thesis we investigate quantitative bound for the corresponding Ramsey-type result. We obtain an Ω(log(k−1) N) lower bound ((k − 1)-times iterated logarithm). We also improve bounds for related problems: Order types and One-sided sets of hyperplanes. 1Nech 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
Keywords:
divided difference; Erdős--Szekeres theorem; k-th-order monotone subset; order type; Ramsey theory; Erdosova-Szekeresova věta; Ramseyova teorie
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/40183