Friends and Strangers on a Party: Ramsey Numbers

Ramsey numbers

One of the amazing stories in logic and math consists of two theorems by Frank Plumpton Ramsey, important in math (combinatorics etc) and math logic, (model theory etc), and computer science. There is an infinite version and a finite version. The first implies the second by using the Compactness Theorem. The finite Ramsey theorem, leading to the astonishing Ramsey numbers, is described in detail in this Aha-insight story.

Ramsey rosettes, corrected

The Ramsey rosette 17-gon counterexample in the Aha-insight Friends and Strangers, copied from a published excellent introductory book on graph theory, was wrong as Joerg Endrullis noticed, august 2023, personal communication. He found using a Sat-solver a correct counterexample rosette as in the figure here, the superposition of the red and the blue one. It is rotation invariant, facillitating its verification that it contains no red or blue quartet; see the verification figures under the rosettes. Included with Joerg’s consent: it will appear in our book in statu nascendi about abstract Reduction Systems, the Core of Computation, 2023 or 2024.