Introduction to Ramsey Theory: Lecture notes for undergraduate course

Edward Nelson was born on May 4, 1932, in Decatur, Georgia. He is a professor in the Mathematics Department at Princeton University.

Leo Moser was a professor of mathematics at the University of Alberta. William Moser a was a professor of Mathematics at the University of Saskatchewan, the University of Manitoba and McGill University.

Be generous and patient as teachers, be active in projects which benefit the mathematical community and, above all, have as long and as happy a mathematical life as I have had, and am still having. — W. Moser in 2003. (Source MacTutor.)

Start by choosing a point\(A\) in the plane and then draw a circle with the centre at \(A\) and radius \(1\text{.}\) Denote this circle by \(C_1\text{.}\) Next, choose a point \(B\) on the circle \(C_1\text{.}\) Draw the line segment \(\overline{AB}\text{.}\)

Draw a circle with the centre at \(B\) and radius \(1\text{.}\) Denote this circle by \(C_2\text{.}\) Let \(C\) be the intersection point of \(C_1\) and \(C_2\text{.}\) Draw a circle, call it \(C_3\text{,}\) with the centre at \(C\) and radius \(1\text{.}\) Observe that the point \(A\) belongs to both \(C_2\) and \(C_3\text{.}\) Let \(D\) be the the other intersection point of \(C_2\) and \(C_3\text{.}\) Draw the line segments \(\overline{AC}\text{,}\) \(\overline{BC}\text{,}\) \(\overline{BD}\text{,}\) and \(\overline{CD}\text{.}\) Observe that all those line segments are of length 1.

Draw a circle, call it \(C_4\text{,}\) with the centre at \(D\) and radius \(1\text{.}\) Draw a circle with the centre at \(A\) and passing through the point \(D\text{.}\) Denote this circle by \(C_5\) Next, choose a point \(E\) in the intersection of \(C_4\) and \(C_5\text{.}\) Draw the line segment \(\overline{DE}\text{.}\) Observe that \(|\overline{DE}|=1\text{.}\)

Draw a circle with the centre at \(E\) and radius \(1\text{.}\) Denote this circle by \(C_6\text{.}\) Let \(F\) and \(G\) be the intersection point of \(C_1\) and \(C_6\text{.}\)

Draw the line segments \(\overline{AF}\text{,}\) \(\overline{AG}\text{,}\) \(\overline{EF}\text{,}\) and \(\overline{EG}\text{.}\) Observe that all those line segments are of length 1.

The Moser Spindle

Start by choosing a point \(A\) in the plane and then draw a circle with the centre at \(A\) and radius \(1\text{.}\) Denote this circle by \(C_1\text{.}\) Suppose that \(c(A)=\color{green}{\bullet}\text{.}\) If there is a green point on the circle \(C_1\text{,}\) then we have two points coloured by the same colour that are one unit apart. Suppose that all points on the circle \(C_1\) are coloured either blue or red. Next, choose a point \(B\) on the circle \(C_1\) and suppose that \(c(B)=\color{red}{\bullet}\text{.}\) There are two points on \(C_1\) that are one unit apart from \(B\text{.}\) (Why?) If one of them is red, we are done. Suppose that both of them are blue and pick one of them. Call it \(C\text{.}\)

Draw a circle with the centre at $A$ and radius \(\sqrt{3}\text{.}\) Denote this circle by \(C_2\text{.}\) Let \(D\) be the intersection point of the circle \(C_2\) and the line of symmetry of the line segment \(\overline{BC}\) that is not on the same side of the line \(BC\) as the point \(A\text{.}\) Observe that \(|\overline{BD}|=|\overline{CD}|=1\text{.}\) (Why?) If the point \(D\) is coloured red or blue then we have two points that are one unit apart and of the same colour. Suppose that \(c(D)=\color{green}{\bullet}\text{.}\)

Let \(E\) be a point on the circle \(C_2\) such that \(|\overline{DE}|=1\text{.}\) Draw a circle with the centre at \(E\) and radius \(1\text{.}\) Denote this circle by \(C_3\text{.}\) Observe that \(C_3\) intersects the circle \(C_1\) at two points, \(F\) and \(G\) and that \(|\overline{FG}|=1\text{.}\) (Why?) Recall our assumption that all points on the circle \(C_1\) are coloured or blue or red. Colour \(E\) by any of the three colours. What happens?

Draw a circle with the centre at \(A\) and radius \(1\text{.}\) Denote this circle by \(C_1\text{.}\) Let \(BCDEFG\) be a regular hexagon inscribed in the circle \(C_1\text{.}\)

Draw a circle with the centre at \(A\) and radius \(\frac{\sqrt{3}}{3}\text{.}\) Denote this circle by \(C_2\text{.}\) Draw a circle with the centre at \(C\) and radius \(1\text{.}\) Let \(H\) be an intersection point of \(C_2\) and \(C_3\text{.}\) Observe that \(|\overline{CH}|= 1\text{.}\)

Let \(\triangle HIJ\) be an equilateral triangle inscribed in \(C_2\text{.}\) Observe that, since the radius of \(C_2\) equals to \(\frac{\sqrt{3}}{3}\text{,}\) \(|\overline{HI}|= |\overline{HJ}|=|\overline{IJ}|=1\text{.}\)

Let \(r\) be the clockwise rotation by\(\frac{2\pi}{3}\) with the centre at \(A\text{.}\) Then \(r(C)=G\) and \(r(H)=J\text{.}\) Since \(r\) is an isometry it follows that \(|\overline{GJ}|=|\overline{CH}|=1\text{.}\) Similarly, \(|\overline{EI}|= |\overline{CH}|=1\text{.}\)

The Golomb Graph.

Suppose that the point \(A\) is coloured red and that each triangle that has \(A\) as a vertex is a rainbow triangle.

If \(H\) is coloured green, then there are two points, \(C\) and \(H\text{,}\) at the unit distance coloured by the same colour. Suppose that the point \(H\) is coloured blue. What are our options for colouring \(I\) and \(J\text{?}\) What if we assume that the point \(H\) is coloured red?

Consider the grid in which the length of the side of each square in the grid equals \(\frac{0.9}{\sqrt{2}}\text{.}\) Observe that the length of the diagonal of each grid cell is \(d=0.9\text{.}\)

A 9-colouring in which all neighbours of each square are of different colours. Is it possible to find two points of the same colour that are one unit apart?

A 7-colouring of a tessellation of the plane by regular hexagons, with diameter slightly less than one. Observe that each hexagon is surrounded by hexagons of a different colour.

7-colouring by László Székely: Start with a row of squares of diagonal 1, with cyclically alternating colours from 0 to 6 of the squares. Obtain the consecutive rows of coloured squares by shifting the previous row by 2.5 squares. Upper and right boundaries are included in each square, except for the upper left and lower right corner.

Closer look: Upper and right boundaries are included in each square, except for the upper left and lower right corner.

“In seeking graphs that can serve as \(M\) in our construction, we focus on graphs that contain a high density of Moser spindles. The motivation for exploring such graphs is that a spindle contains two pairs of vertices distance \(\sqrt{3}\) apart, and these pairs cannot both be monochromatic. Intuitively, therefore, a graph containing a high density of interlocking spindles might be constrained to have its monochromatic \(\sqrt{3}\)-apart vertex pairs distributed rather uniformly (in some sense) in any \(4\)-colouring. Since such graphs typically also contain regular hexagons of side- length 1, one might be optimistic that they could contain some such hexagon that does not contain a monochromatic triple in any 4-colouring of the overall graph, since such a triple is always an equilateral triangle of edge \(\sqrt{3}\) and thus constitutes a locally high density, i.e. a departure from the aforementioned uniformity, of monochromatic \(\sqrt{3}\)-apart vertex pairs.” — de Grey, Aubrey D.N.J. (2018), “The Chromatic Number of the Plane Is at least 5”, Geombinatorics, 28: 5–18, arXiv:1804.02385.

Consider a Moser spindle and observe that \((A,C)\) and \((A,D)\) are two pairs of vertices distance \(\sqrt{3}\) apart. Also, observe that the measure of the angle \(\angle DAC\) is \(\alpha=\arccos \left(\frac{5}{6}\right)\approx 33.56^0\text{.}\)

Rotate the Moser spindle through \(\alpha\) about the point \(A\) to obtain another Moser spindle. Observe that the two spindles share four vertices and five edges.

An additional clockwise rotation by \(\frac{\alpha}{2}\) produces “three tightly linked Moser spindles.”