# Relationship between proof and algorithm of Ramsey's Theorem

The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14:

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 $$\frac{1 }{2} \log_{2} n$$ nodes.

In other words: Prove $$R(t,t) \le 2^{2t}$$ from this answer, Call it A1 The answer in A1 uses the upper bound $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \;$$ to prove this inequality but the selected answer given in the book uses the following algorithm (modified for readability):

Let $$A$$ and $$B$$ be two empty sets, $$remNodes(G)$$ is a function on $$G$$ which returns the number of remaining nodes in $$G$$ ,$$discard(n,con|ncon,G)$$ be a function that discards all the nodes connected or not by some edge given to $$n$$ by argument $$con$$,$$ncon$$ from the graph $$G$$, $$deg(x)$$ is a function that returns degree of node $$x$$ and $$add(x,S)$$ is a function to add an element to set $$S$$.

while (remNodes(G)) do
Remove x from G
if deg(x) > (1/2)(remNodes(G))
else

The set $$A$$ now contains nodes that form a clique and $$B$$ contains nodes that form an independent set.
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 $$\log_{2} 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 $$\frac{1}{2} \log_{2} n$$ nodes. The A pile contains the nodes of a clique and the B pile contains the nodes of an anti-clique.
• The algorithm closely follows the inductive proof of the upper bound on $R(s,t)$ that you mention. Feb 16, 2021 at 13:16