Print Email Facebook Twitter Ramsey theory Title Ramsey theory Author Titulaer, Björn (TU Delft Electrical Engineering, Mathematics and Computer Science) Contributor Hart, K.P. (mentor) Degree granting institution Delft University of Technology Date 2020-08-31 Abstract In this report we will take a look at various proofs of Ramsey's theorem, some of the bounds that result from those proofs and applications of Ramsey's theorem. We will consider the proof of Ramsey himself, the proof of Skolem, the proof given by Erd\H{o}s and Szekeres and the proof of again Erd\H{o}s and Rado. The best upper bound for higher order Ramsey numbers is obtained by following the proof of Erd\H{o}s and Rado and this bound has only marginally improved since then. We will also state and prove the lower bound given by Erd\H{o}s and Hajnal. In the end we will apply Ramsey's theorem to both the Happy Ending problem and the monotone subsequence problem. The bounds we get for both problems using Ramsey's theorem, however, are quite weak compared to bounds that do not use Ramsey's theorem, so the theorem is more useful in proving the existence of a certain number than it is to find strong bounds for it. Subject RamseyColoringHypergraph To reference this document use: http://resolver.tudelft.nl/uuid:ab1aab60-e7ad-4d32-bb82-1a5e2efd78fd Part of collection Student theses Document type bachelor thesis Rights © 2020 Björn Titulaer Files PDF BEP_1_.pdf 280.63 KB Close viewer /islandora/object/uuid:ab1aab60-e7ad-4d32-bb82-1a5e2efd78fd/datastream/OBJ/view