Ramsey theory

Ramsey theory

Titulaer, Björn (TU Delft Electrical Engineering, Mathematics and Computer Science)

Hart, K.P. (mentor)

Delft University of Technology

2020-08-31

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.

Ramsey
Coloring
Hypergraph

http://resolver.tudelft.nl/uuid:ab1aab60-e7ad-4d32-bb82-1a5e2efd78fd

Student theses

bachelor thesis

© 2020 Björn Titulaer