2
$\begingroup$

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))
  add(x,A)
  discard(x,nconn)
 else
  add(x,B)
  discard(x,conn)

The set $A$ now contains nodes that form a clique and $B$ contains nodes that form an independent set.

Can anyone explain this algorithm and its relationship with the proof of upper bound(if exists)?

In the book the solution is written as follows:

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.

$\endgroup$
2
  • $\begingroup$ The algorithm closely follows the inductive proof of the upper bound on $R(s,t)$ that you mention. $\endgroup$ Feb 16, 2021 at 13:16
  • $\begingroup$ @Yuval i didn't read the proof but accepted it as is. However your comment is what all i need. Thanks $\endgroup$ Feb 16, 2021 at 15:09

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.