Ramsey theory
B.I. Titulaer (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Klaas Pieter Hart – Mentor (TU Delft - Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.