ON RAMSEY-TYPE THEOREMS AND THEIR PROVABILITY IN WEAK FORMAL SYSTEMS (WAERDEN, SZEMEREDI, HINDMAN).

摘要

This dissertation deals with four important theorems in Ramsey Theory: the Simpson-Carlson dual Ellentuck theorem: Hindman's theorem; van der Waerden's theorem; and Szemeredi's theorem. It uses the dual Ellentuck theorem to prove that there exist infinite partitions of the natural numbers with no coarsenings of higher degree, and proves that Hindman's theorem is false in recursive arithmetic. It shows that a standard lower bound on van der Waerden's function can be improved by a factor of two by considering colorings of Z/nZ, and gives an empirically useful technique for finding colorings of Z/pZ for p prime that avoid containing long monochromatic arithmetic sequences. It shows that functions related to Szemeredi's theorem are greatly simplified when they are altered to refer to Z/nZ rather than to sets of n consecutive integers. Finally, it presents conjectures on affine transformations of finite fields that generalize Szemeredi's theorem, and proves partial results supporting these conjectures.