Section 3.1 Script
\({\Large {\textbf{Introduction:}}}\) Welcome to drawing the evolution of Ramsey Theory! Ramsey theory itself takes a look at the mathematics of colouring and our fundamental question: Can we find order to the chaos?
We will take a look at this course in a non-chronological matter. Each notable mathematician who contributed to Ramsey theory is connected together to display the concept of complete chaos.
\({\Large {\textbf{Frank Ramsey:}}}\) We begin our story of Ramsey theory in Cambridge, England where Frank Ramsey was born in 1903. He studied at Trinity College earning himself senior scholar with a first-class degree in Mathematics. Before his untimely death, Ramsey sat down and crafted arguably his most notable contribution to Math history in his paper “On a Problem of Formal Logic.”
In order to grasp Ramsey's theorem, we will do a quick introduction to the pigeonhole principle with an example.
Say we have 9 pigeonholes and 10 pigeons. When placing each pigeon into their own individual pigeonhole we will be left with one pigeon that must share a pigeonhole. This is one way of visualizing the pigeonhole principle which states “suppose you have \(k\) pigeonholes and \(n\) pigeons to be placed in them. If \(n>k\) then at least one pigeonhole contains at least two pigeons.”
Ramsey's theorem: A special case of Ramsey's theorem states that for any edge 2-colouring of the complete graph \(K_6\) will yield a monochromatic \(K_3\text{.}\)
A real world understanding of Ramsey's theorem can be demonstrated by considering 6 individual people. The relationships between them create a complete graph on the 6 vertices or people. What we want to show is that if we consider a blue edge between two people to mean they are friends and a red edge to represent strangers that there exists either 3 strangers or 3 friends in any group of 6.
We can see by considering the relationships between one individual and the 5 others in the group. By the pigeonhole principle, we can see a 2 colouring of these relations will result in at least 3 edges of the same colour, say blue. If any one of the edges between the 3 connected vertices is blue we have a resulting monochromatic \(K_3\) or 3 friends. If none of the 3 edges are blue and instead red then we again have a \(K_3\text{,}\) but in this case 3 strangers proving this special case of Ramsey's theorem.
Let's go back in time to 1927 in Amsterdam where we will meet our next big contributor in Ramsey theory.
\({\Large {\textbf{Bartel van der Waerden:}}}\) Bartel van der Waerden was born in 1903 to a family of mathematicians. He stuck closely to the field of mathematics all throughout his childhood before entering the University of Amsterdam where he also completed his doctorate.
van der Waerden's theorem, published in 1927, was a proof of Baudet?s conjecture. While one of the earliest theorems of Ramsey theory, it is most easily understood when considering the later discovered Ramsey theorem.
\(\textbf{van der Waerden's Theorem:}\) For any integers \(i\) and \(k\) there is some number \(N\) such that the colouring of the integers \(\{1, 2,\ldots , N\}\) with \(k\) different colours, results in a monochromatic \(i\)-term arithmetic progression.
\(\textbf{Example:}\) Let's take the integers \(1-8\) as an example, we can colour these using two colours and avoid any 3-term monochromatic arithmetic progressions. However, when we add 9, now we have either a blue 3-term arithmetic progression on the integers 1, 5, and 9, or we have a red 3-term arithmetic progression on the integers 3, 6, and 9.
Turning back the clocks once more, we are in 1917. This is the year Issai Schur published the earliest theorem in Ramsey theory.
\({\Large {\textbf{Issai Schur:}}}\) Issai Schur was a Russian-born mathematician who worked in Germany for most of his life. He was born on January 10, 1875 in Mogilev, Russia (now Belarus). He was born to a merchant family, his father Moses Schur and mother Golde. He became fluent in German when he went to Latvia at the age of 13 and attended the Gymnasium in Libau.
In 1894, Schur entered the University of Berlin, with concentration in mathematics and physics.
Schur's Theorem was found while trying to solving Fermat's Last Theorem. He however, failed to prove it, but instead published Schur's theorem in his 1916 paper. His theorem was not recognized on its own until later on from its discovery.
Schur's Theorem actually preceded Ramsey?s theorem, as it was published in 1916.
The main idea of this theorem is that the set of positive \(N\) integers, for \(N\) big enough, if finitely covered, then you can always have three numbers \(x,y\text{,}\)and \(z\) that have the same colour such that \(x+y=z\text{.}\) We are now looking at a set of colours defined \(c_1,c_2,\ldots ,c_r\text{.}\)
Let us see this theorem in practice.
Let's take an example, with a \(2\)-colouring of red and blue of interval \([1,5]\) and see if we can avoid monochromatic Schur triple: We see that \(1,1,2\) and \(2,2,4\) are Schur triples.
\({\Large {\textbf{Richard Rado:}}}\) In Richard Rado's 1933 thesis, Studien zur Kombinatorik, he generalised a basic result, proved by his supervisor Issai Schur which gives what is known today as Rado's Theorem.
Schur's theorem was generalized by Rado. For Rado, Schur's theorem was about monochromatic solutions of a homogeneous linear equation \(x+y-z=0\text{,}\) and so Rado generalized the Schur Theorem to a vast class of homogeneous linear equations.
Now, we will state Rado's theorem: The equation \(c_1 x_1 + c_2 x_2 + \ldots + c_n x_n = 0\) is partition regular over \(\mathbb{N}\) if and only if there is \(J \subseteq [n]\) such that \(\sum_{i\in J}c_i=0.\)
We now move across the water to America where at California Institute of Technology,
\({\Large {\textbf{Hales-Jewett:}}}\) Alfred W. Hales and Robert I. Jewett are American mathematicians who met at Caltech university during their graduate studies. They became fast friends over their joint love for mathematics and volleyball. This then led them to create the Hales-Jewett Theorem in 1963.
\(\textbf{The Hales-Jewett Theorem:}\) Let \(m, k \in \mathbb{N}\) and let \(A\) be an alphabet on \(m\) symbols. There exists an \(n \in \mathbb{N}\) such that whenever \(A^n\) is \(k\)-coloured there exists a monochromatic line.
This theorem is integral to Ramsey Theory; it is one of the most useful techniques of Ramsey theory and it has played an important role in the different proofs of theorems related to Ramsey theory, but ultimately, it is a big reason for what turned Ramseyan theorems into Ramsey theory.
And with the closing of Hales-Jewett Theorem, that brings an end to our video on Ramsey theory. We hope this brings some order to the chaos!