Register to reply

Ramsey's theorem help..~

by RyozKidz
Tags: ramsey, theorem
Share this thread:
Jan11-10, 05:59 PM
P: 26
1. The problem statement, all variables and given/known data

Ramsey's theorem. Let G be a graph . A clique in G is a subgraph in which every two nodes are connected by an edge . An anti-clique , also called an independent set , is a subgraph in which every two nodes are not connected by an edge . Show that every graph with n nodes contains either a clique or an anti-clique with at least 1/2log2n nodes.

2. Relevant equations

[b]3. The attempt at a solution[/b

Make space for two piles of nodes , A and B . Then , starting with the entire graph , repeatedly add each remaining node x to A if its degree is greater than one half the number of remaining nodes and to B otherwise , and discard all nodes to which x isn't(is) connected if it was added to A(B) . Continue until no nodes are left. At most half of the nodes are discarded at each of these steps , so at least log2 n steps will occur before the process terminates . Each step adds a node to one of the piles , so one of the piles ends up with at least 1/2log2 n nodes. The pile contains the nodes of a clique and the B pile contains the nodes of an anti-clique.

I cant interpret this solution ..~ can anyone help me out..~ pls...
Phys.Org News Partner Science news on
'Office life' of bacteria may be their weak spot
Lunar explorers will walk at higher speeds than thought
Philips introduces BlueTouch, PulseRelief control for pain relief

Register to reply

Related Discussions
Rolles Theorem/ Mean Value Theorem + First Derivative Test Calculus & Beyond Homework 6
Greens theorem and cauchy theorem help Calculus & Beyond Homework 4
Gauss' Theorem/Stokes' theorem Advanced Physics Homework 2
Applications of Ramsey's Theorem General Math 0
Gauss's Divergance Theorem and Stokes's Theorem Classical Physics 1