Ramsey’s Theorem

Ramsey’s theorem is a fundamental theorem in combinatorial mathematics, and initiated the combinatorial theory called Ramsey Theory. This theory aims to seek regularity in disorder: “general conditions for the existence of substructures with regular properties“.

Ramsey’s theorem states that:

“for each pair of positive integers k and l there exists an integer R(k,l) such that any graph with R(k,l) nodes contains a clique with at least k nodes or an independent set with at least l nodes.


Clique:

A clique of agraph G is a complete subgraph of G.

Clique_950.gif
Source: MathWorld

Independent Set:

An independent vertex set of a graph is a subset of the vertices such that no two vertices in the subset represent an edge of the graph. Below are some examples:

IndependentSet_900.gif
Source: MathWorld

Another formulation of the theorem states that “there exists a least positive integer R(rs) for which every blue-red edge colouring of the complete graph on R(rs) vertices contains a blue clique on vertices or a red clique on s vertices”. Extending this theorem, we can apply this to n colours rather than just 2.

For a proof of this theorem, click here.

Ramsey Numbers

The numbers R(r,s) in Ramsey’s theorem are called Ramsey numbers. Ramsey numbers give the solution to the party problem that asks:

“the minimum number of guests, R(mn), that must be invited so that at least m will know each other or at least n will not know each other”

Connecting Ramsey numbers to graph theory, the Ramsey number is the minimum number of vertices, v = R(m,n), needed in order for all undirected graphs of order v to contain a clique of order m or an independent set of order n. Ramsey’s theorem tells us that this exists for all m and n.

Click here for an article on how to calculate R(4,3).

M x

NEWS: World’s Largest Proof

Recently, a trio of mathematicians – Marijn Heule from the University of Texas, Victor Marek from the University of Kentucky, and Oliver Kullmann from Swansea University – have solved a problem in mathematics and the solution takes up 200 terabytes of basic text (just consider the fact that 1 terabyte can hold 337,920 copies of War and Peace)! This breaks the previous recorded of a 13-gigabyte proof, which was published in 2014.

The mathematics problem is named the ‘Boolean Pythagorean Triples problem’, and was posed by Ronald Graham in the 1980s, who offered a $100 prize for the solution.

The problem is part of Ramsey theory and asks:

“Is it possible to colour all the integers either red or blue so that no Pythagorean triple of integers a, b, c, satisfying a^2+b^2=c^2 are all the same colour. For example if you would colour a and b red, and c blue, this would successfully not satisfy the tested triple, but all triples would have to be tested.”

Andrew Moseman from Popular Mechanics details how:

“What makes it so hard is that one integer can be part of multiple Pythagorean triples. Take 5. So 3, 4, and 5 are a Pythagorean triple. But so are 5, 12, and 13. If 5 is blue in the first example, then it has to be blue in the second, meaning either 12 or 13 has to be red.

The proof found that it is only possible to colour the numbers in such a way up to the number 7,824 and that 102,300 such colourings exist. Hence, there is no solution to the problem question. The proof took a supercomputer two days to solve, and generated 200TB of data!

The paper describing the proof was published on arXiv on the 3rd of May 2016.

Although the computer has proved that the colouring is impossible, it has not provided the underlying reason why this is, or explored why the number 7,824 is important. This highlights the objection to the value of computer-assisted proofs; yes, they may be correct, but to what extent are they mathematics?

Sources: 1 | 2

Let me know what you think of computer assisted proofs below! M x

Maths Bite: Graham’s Number

Graham’s number, named after Ronald Graham, is a large number that is the upper bound (just like Skewes’ Number) on the solution to a problem in Ramsey theory.

Expressing Graham’s Number

As Graham’s number is so large, it can’t be expressed using the conventional notation of powers, and powers of powers.

\left.
 \begin{matrix}
  G &=&3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots\cdots \uparrow}3 \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow}3 \\
    & &\underbrace{\qquad\;\; \vdots \qquad\;\;} \\
    & &3\underbrace{\uparrow \uparrow \cdots\cdot\cdot \uparrow}3 \\
    & &3\uparrow \uparrow \uparrow \uparrow3
 \end{matrix}
\right \} \text{64 layers}
Source: Wikipedia

Grahams number is defined using Knuth’s up-arrow notation, introduced by Donal Knuth in 1976. The number of arrows in each layer, starting from the top layer, is specified by the value of the next layer below it. In cleaner notation:

G = g_{64},\text{ where }g_1=3\uparrow\uparrow\uparrow\uparrow 3,\  g_n = 3\uparrow^{g_{n-1}}3,

Equivalently,

G = f^{64}(4),\text{ where }f(n) = 3 \uparrow^n 3,

Not only does Graham’s number have an incomprehensibly large magnitude, it is also useful to mathematicians, and that is what makes this number so well known.

Ramsey Theory and Context

Ramsey theory is an area in mathematics which studies conditions under which order will appear. Graham’s number is concerned with the following problem in Ramsey theory:

“Connect each pair of geometric vertices of an n-dimensional hypercube to obtain a complete graph on 2n vertices. Colour each of the edges of this graph either red or blue. What is the smallest value of n for which every such colouring contains at least one single-coloured complete subgraph on four coplanar vertices?”


Terminology:

Hypercube – a generalisation of a 3-cube to n dimensions.

Complete Graph – a graph in which each pair of graph vertices is connected by an edge

CompleteGraphs
Source: Wolfram Math World

 

An answer – N* – was proved to exist by Graham and Rothschild in 1971. The weak upper bound for N* is given by Graham’s number, and was found in Graham’s unpublished work, eventually being published and named by Martin Gardner in Scientific American in November 1977.

Sources: 1 | 2

Hope you enjoyed the second instalment of ‘Maths Bite’. M x