Theorem on Friends & Strangers: Infinite Possibilities

[cragar]

Theorem on friends and strangers:
If we have 6 people in a room, then 3 of them know each other or 3 of them don't know each other. Or should it say that at least 3 people don't know anyone or at least 3 people are friends? Then my teacher said we can extend this to infinite sets, saying there is an infinite amount of people that don't know each other or there is an infinite amount of people that know each other. But it seems like I could have both with infinite sets. We could have all the even number people be friends with their squares, And all the odd numbered people be friends with their squares and we will make sure that the even and odd number people are friends.
This is not homework.

 

[Norwegian]

Hi Cragar,

You may have slightly misunderstood the statements of the theorems. The first one says that in any group of six people, we can either find a subgroup of three where all three are friends to each other, or a subgroup of three, all of whom are strangers (to the others in the subgroup).

Your attempt of reformulation misses that the required friendship, or lack thereof, is only for the subgroup, and your remark about the infinite case seems to be a confusion of the statement "A or B", which does allow for the case of both A and B happening at once.

These theorems are part of Ramsey theory, a very fun part of combinatorics, with plenty of accessible statements not yet proven. The friendship theorem can be stated as r(3,3)=6, meaning that 6 is the lowest number of people you can have to be guaranteed either 3 friends or 3 strangers. r(5,5) is the lowest case not yet determined. Among 49 people you can always find 5 friends or 5 strangers, but this may be true all the way down to 43.

 

[cragar]

ok so when we say " A or B '' one or both could be true or both could be true to make that statement true.

 

[awkward]

Here is another way to state the theorem which may be easier to visualize.

Suppose you have a graph consisting of 6 vertices connected by edges. Each point is connected to every other point by a single edge. In other words, we have the complete graph on 6 vertices. Each edge is colored either red or blue. Then either there is a triangle with all blue edges, or there is a triangle with all red edges.

 

[cragar]

Ok I think understand the graph thing.
So for example I could also have 3 groups of 2 people where they each knew each other.
so If I pick someone from one of the groups and wouldn't know someone from any of the other 2 groups.
And then I think for the next Ramsey number, if we want a group where 4 people know or don't know each other we need 18 people to make sure of this, but it seems like 7 would work.

 

[Norwegian]

A very simple example is having 3 groups of 3 friends, where friendship only exists within the groups, then you have 9 people without any 4 friends or 4 strangers. Such examples can be made all the way up to 17 (number the people 0,1,...,16, and assume x and y are friends iff x and y differ by either 1, 2, 4 or 8 modulo 17), showing that r(4,4)>=18. To prove the upper bound, you need to work your way to r(4,3)=9 first, and then use the relation r(m,n)<=r(m,n-1)+r(m-1,n) which is a nice easy exersize to show.

 

[cragar]

I don't know if I understand your example with 3 groups of 3 friends, where the friendship only exists within the groups. If the friendship only exists in the groups then I could take one person from a group and he wouldn't know any of the other people in another group so I would have 4 strangers. Do you know a good book to learn about Ramsey theory.