#ramsey's theorem

[trivalentlinks]

Suppose there are six major characters in a show. Further suppose that for any two characters, I either ship them or I don’t. (There’s no quantum superposition state.)

Can you show that there must be either three characters such that I ship any two of them, or three characters such that I don’t ship any two of them?

Can you show that this is not necessarily true for a show with five characters?

[eatsleepmath]

This paper is primarily concerned with a special case of one of the leading problems of mathematical logic, the problem of finding a regular procedure to determine the truth or falsity of any given logical formula. But in the course of this investigation it is necessary to use certain theorems on combinations which have an independent interest and are most conveniently set out by themselves beforehand.

Frank Ramsey, before proving Ramsey’s theorem

[wiskwa-en]

Ramsey’s Theorem, II

This is part two of a translation of an article that appeared in the April 2005 issue of Pythagoras.

In this part we state and prove the finite version of Ramsey's theorem for pairs.

Ramsey numbers

Last time we investigated how large a party should bein order for there to be groups of people who all do or who all don not know each other. Ramsey's theorem states that you can always find large enough groups provided the party has enough guests.

Ramsey's theorem for pairs. For every two natural numbers k and l there is a natural number N such that at every party with N guests there will be a group of k people that all know each other or a group of l people that all do not know each other.

The smallest number that works for k and l will be written R(k,l); the R(k,l) are called Ramsey numbers, after the logician Frank Ramsey who proved in 1929 that these numbers actually exist. The theorem is often presented as one about graphs: given natural numbers k and l there is a natural number N such that no matter how we color the lines connecting N points green and red there will be k points such that all lines between these are green or l points with all lines between them red.

The story about the party with six people shows that R(3,3)≤6 and the special party with five guests shows that R(3,3)&gr;5 and so R(3,3)=6.

To show that the numbers R(k,l) actually exist we shall derive upper bounds for them. Before we do that we make two simple observations.

First: by interchanging `knowing' and `not knowing' (or green and red) we see that R(k,l)=R(l,k). Second: R(k,2)=k, because at a party with k guests everyone knows each other or two people do not.

The argument that we used to show R(3,3)≤6 can be used to show the following inequality:

This works as follows: suppose you have R(k,l-1)+R(k-1,l) people at your party. Pick one guest and divide the rest into two groups: d people that she does know and n people that she does not know. Then we have, of course

We cannot have both d<R(k-1,l) and n<R(k,l-1) because then we would have d+n≤R(k,l-1)+R(k-1,l)-2. So, we have two possible cases.

Case 1 d≥R(k-1,l). Then there will be among those d people either l people that all do not know each other (and we are done) or there are k-1 people that all do know each other and together with the special guest they form a group of k people as desired.

Case 2 n≥R(k,l-1). You can deal with this case yourself.

If you look back at our first argument then you will see that it proves R(3,3)≤R(3,2)+R(2,3). After that we used the exact same argument to prove that R(3,4)≤R(3,3)+R(2,4)≤6+4=10. Then we used a more detailed argument to show that, in fact R(3,4)≤9 and then, by an example, that R(3,4)>8 and hence R(3,4)=9.

We ended the last post with an exercise to find an upper bound for R(4,4) and maybe you had already discovered that R(4,4)≤R(4,3)+R(3,4)=9+9=18.

Exercise. Find an upper bound for R(5,5). How many steps would it take to find an upper bound for R(10,10)?

Exercise. Draw a regular 17-gon, number the vertices 1 through 17 and color the line connecting i and j red if j-i is equal to 1, 2, 4, 8, 9, 13,15, or 16 and green otherwise, see the picture below. Now verify carefully that there is no set of four points with all connecting lines of the same color. Conclusion: R(4,4)=18.

A general formula

You may have noticed that our inequality looks a bit like a well-known equality for binomial coefficients

As we just saw we have R(k,2)=k and we can write that as

The last form makes the 2 visible. Using the principle of mathematical induction you can extend this to the following theorem:

Theorem. For every k and l the following inequality holds.

This shows that the numbers R(k,l) exist and it gives us an idea of their size.

Small improvements

The inequality in the theorem is not sharp. We saw that with R(3,4) and R(4,4). The theorem gives

but we already know that R(3,4)=9 and R(4,4)=18. The more precise argument that gave us R(3,4)≤9 can be used to prove the following: if R(k-1,l) and R(k,l-1) are both even then

We need just one person with d≥R(k-1,l) or n≥R(k,l-1); if that never happens then always d=R(k-1,l)-1 and n=R(k,l-1)-1 and that would, again, lead to an odd number that should be even.

The exact value of R(k,l) is known for very few pairs (k,l). People are still looking for better estimates, from below and from above). At this address you can find a table and further references. You will see that R(5,5) is still not known; what is known is 43≤R(5,5)≤49.

[wiskwa-en]

Ramsey’s Theorem, I

This is part one of a translation of an article that appeared in the April 2005 issue of Pythagoras.

When you distribute very many things over very few boxes then at least one box will get quite full. Many results in mathematics rest on this simple observation; Ramsey’s theorem is one of the most beautiful examples of this.

If you write down five different natural numbers then you know for sure that at least three will have parity (the same remainder upon division by 2). In other words if you only use the property `odd or even’ to distinguish numbers then in a set of five there will be three indistinguishable numbers.

You make many variations on this theme: put 367 people together and you know that there will be two that share a birthday (remember leap years). If you pick thirteen (real) numbers from the interval (-½π,½π) then two will differ by less than π/12. You can formulate a general theorem.

Theorem. If m and n be natural numbers and if you distribute n×m+1 things over m boxes then at least one box contains at least n+m things.

Ramsey’s theorem, which we discuss in this post, says that things like this will happen always: if you write down a finite number of properties then given a natural number n you can always find a natural number N such that in every group of N people you will find n people that cannot be distinguished using these properties. The properties that Ramsey’s theorem speaks about can also apply to pairs, triples and so on. In this post we will deal with pairs only.

Do you know each other?

At a party you can determine of every two guests whether they know each other or not. If there are six people present then you can make a group of three such that all~three know each other or such that all three do not know each other. Here is how. Pick one guest and divide the five others into two groups: those she knows and those she does not know. As we saw above if you divide five things into two groups one group has at least three members. So, for example, our one guest knows three other people. If none of the three know each other then we are done. If two of these know each other then they with the one guest form a group of three where everybody know each other. See the pictures below, where a green line means `know each other’ and a red line means `do not know each other’; the dashed lines represent the two cases that we had to consider.

Five guests only. With just five guests this argument will not work and, indeed, you can create a situation where no group of three as desired can be found.

Again green means `knowing’ and red means `not knowing’; there is no triangle with all sides of the same color

On to four

The next logical step would be to see how large the party should be in order to get a `homogeneous’ group of four people; homogeneous means that all pairs have the same property. We shall do this but it turns out to be easier to look at non-symmetric situations too. Therefore we first look for a meeting where there are either four people that know each other or three that do not know each other.

Four that know each other or three that do not. We follows the earlier strategy: set aside one guest and divide the rest of the guests into two groups, those she knows and those she does not know. In the following, favorable, situations we can deduce that there are four people that all know each other or three that do not.

Situation 1: she knows six people at the party. This gives us two cases:

three of these do not know each other and we are done

three of these do know each other and with our separate guest this gives a group of four that all know each other

Situation 2: there are four people that she does not know. Again we have two cases:

all four know each other, and we are done

two of these do not know each other and with our separate guest this gives a group of three that do not know each other

From this we see that it suffices to have nine other guests; then one of the favorable situations must present itself. This shows that ten guests is enough.

Nine guests is enough. But even at party with nine guests is large enough. The point is that we need just one guest for whom one of the good situations occurs (with ten guests we get that for everybody). For every guest there are eight “others’ and if there is never a favorable situation then everybody knows exactly five people and does not know exactly three. Draw a line between every pair of guests that knows each other. This makes everybody an end point of five lines, there are nine people and hence 45 end points in total. But that is impossible: every line has two end points, so there must be an even number of end points.

Eight is not enough. Look at the following picture.

As before green means `knowing’ and red means `not knowing’. Number the points 1 through 8, anti-clockwise. If you look closely you will see that there is a green line between i and j if the difference j-i is equal to 2, 3, 5, or 6; it is red if the difference is 1, 4, or 7. There is no red triangle, for let i

Four that know each other or four that do not. With what we learned so far it is not very difficult to determine an N such that at every party with N guests there will be four that all know each other of that all do not know each other.

Exercise. Determine an N that suffices for the four-four situation. Is your N the smallest possible one?

Next time we shall use the method of setting one guest aside to tackle the general problem: with many people can we be sure that there are k people that know each other or l people that do not know each other?

[idease]

An illustrated proof of a theorem on friends and strangers

among six people, a group of three of them are mutual friends or strangers

Let's consider a group of six people, perhaps standing together at a Halloween party. To simplify things, we'll draw them as dots.

We'll also assume that each pair of people is either a pair of friends or a pair of strangers. So we can draw their relationships as follows, letting a green line indicate a pair of friends and an orange line indicate a pair of strangers.

We can see a group of three people who are all friends (green) with each other—in fact, there are two, which we've highlighted. There's also a group of three people who are all strangers (orange) to each other. (Formally, the diagram is a "graph" and the groups of three are "monochromatic triangles".) Notice that every pair is connected by a line of one color or the other (this property means that the graph is "complete").

The theorem is that no matter who is friends with who, there will always be at least one group of three friends or three strangers, as above. (We can say this more formally: no matter how we color the lines of the complete graph on 6 vertices, there will always be a monochromatic triangle.)

Now let's prove it. We first pick one person of the six; it could be anyone, but let's say it's Cleo. There are five lines connected to Cleo, one for each of the other five people. The distribution of these five lines could range from all friends to all strangers, but in any case at least three will be the same color.

Let's assume that at least three of Cleo's connections are green ("without loss of generality"; the following argument works just as well with orange instead). So we can draw Cleo with three of her friends.

Of these three friends (excluding Cleo), if at least one pair is friendly, then we have a group of three friends, namely Cleo and the two in that friendly pair, and we're done.

But if none of the three are friends with each other, then they must all be strangers, creating a group of three strangers.

Any way, our group of six has a group of three friends or three strangers, as promised. As is customary, we end the successful proof with a celebratory tombstone: ∎

Note that six is the smallest number that guarantees a monochromatic triangle. That is, a monochromatic triangle may not exist between five or fewer people, as in

What we just proved is one case of Ramsey's Theorem. We could say that instead of a group of three friends or strangers, we want a group of four people, all of whom are friends with each other or strangers with each other. This condition is guaranteed with 18 people at the least. The sizes of these groups are Ramsey numbers: R(3,3)=6 and R(4,4)=18. (There are two 3s and two 4s because we can stipulate different group sizes for friends and strangers.) Ramsey's Theorem says that R(f,s) exists for all natural numbers f and s. (This theorem has been proven in full generality, so we don't have to check each case individually (which would be impossible because there are infinitely many).) Somewhat amazingly, we don't know the exact values of R(5,5) and above, because they get very difficult to calculate.