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
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems

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