Ramsey’s theorem: does every node belong to a clique?

[leyou]

Ramsey’s theorem: does every node belong to a clique?

Hello !

So, I'm coming here because I don't even know how to start my answer.
The problem is the number 11 of this file : http://www.cs.uiowa.edu/~rus/Courses/Theory/assign1.pdf

Just one thing... Knowing that every nodes are 1-clique, we could say that every nodes belongs to a clique ?
I don't understand...

Moreover, I'm not a native english speaker so it's possible I misunderstanted something...

An idea :/ ?

Thanks in advance

 

[Deleted member 4993]

Re: Ramsey’s theorem

Hello !

So, I'm coming here because I don't even know how to start my answer.
The problem is the number 11 of this file : http://www.cs.uiowa.edu/~rus/Courses/Theory/assign1.pdf

Just one thing... Knowing that every nodes are 1-clique, we could say that every nodes belongs to a clique ?
I don't understand...

Moreover, I'm not a native english speaker so it's possible I misunderstanted something...

An idea :/ ?

Thanks in advance

Go to:

http://www.math.niu.edu/~rusin/known-math/99/ramsey

 

[leyou]

Re: Ramsey’s theorem: does every node belong to a clique?

Thanks for your reply, but I'm becoming completely crazy with this problem...

The first little bit of _Ramsey Theory_ by Graham, Rothschild, and Spencer gives an argument which is good enough for your exercise. Sketch: show by induction that there is a sequence of verticies v1,...,v_{2k-1} such that for each v_i, either v_i has an edge with v_j for all j>i, or v_i does not have an edge with v_j for any j>i. (Hint: take any vertex as v1.) Then take whichever subset of the sequence is more numerous.

How ?!

I wrote :
Let G be a simple graph with n nodes.\\
Among this n nodes, we have a node called p_1, which is linked to at least n/2 other nodes, or not linked to at least n/2 other nodes.\\
Let's assume we are in the first case, and we call the set of nodes linked to p_1, S_1.\\
Among S_1, we have at least one node linked to n/4 other nodes belonging or not linked to at least n/4 other nodes.
...

I know I'm in the wrong way and I haven't progressed since 6 hours...

Argg :x Damn exercice