Ramsey's Theory

We will pause our journey through the Solar System in search of water and life to briefly dwell on the problem raised last week.

we remember the problem in summary version: Given ten people such that in any group of three of them there are at least two that are not known, to show that there is at least one group of four people in which no one knows another


The discussion between our "featured users" Manuel Amorós and Francisco Montesinos (see comments last week) leads to a clue: to solve the problem, it may be useful to address this one first:

"Demonstrate that, in a group of six people, there are either at least three who know each other, or there are at least three who do not know each other.

These kinds of problems refer to the so-called "Ramsey theory" (in honor of the British mathematician and philosopher Frank P. Ramsey), which studies the conditions to be met so that a certain type of order appears in a given set. Or, more specifically, how many items must be in a set for a given property to appear.

The "beginning of the dovecote" can be considered a simple case of Ramsey's theory, since we can enunciate it thus: How many pigeons must there be so that, given a set of n dovecotes, there is at least one dovecote with more than one pigeon? The answer, in this case, is obvious: there must be more pigeons than pigeons; that is, if we call m to the number of pigeons, the condition ordered is m > n. A less simple example could be a misanthropic riddle raised a few months ago in these same pages: If 70% of men are ugly, 70% are dumb and 70% are bad, what will be, at least, the percentage of men who meet the three "qualities", that is, who are both ugly, foolish and bad


The theorem of friendship

The problem of the six people above is, in fact, a whole theorem, known as "friendship theorem", and also as "theorem of friends and strangers".

A group of six people in which each relates in some way to each of the others, can be represented schematically by a hexagon with all its diagonals. In theory, it is a complete graph, as each node (each vertex of the hexagon) is attached to all others. Well, if the people who meet them join them with a red stroke and those who do not know each other with a blue stroke, the friendship theorem shows that there will be at least one red triangle or a blue triangle (i.e. a group of three acquaintances or a group of three strangers). How do you prove it? And if there were only five people, could we say the same thing


The "happy ending problem", named after Paul Erds (for extra-mathematical reasons), is closely related to Ramsey's theory, and says so:

Any set of five points on the plane in general position (without three or more in a straight line) has a subset of four points that are the vertices of a convex quadrilateral.

but that's another article,