7
$\begingroup$

Prove that

$r(k,k) + k \leq r(k + 1, k + 1)$,

where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes.

There are three theorems I know in the area. I tried to prove it using all of them, but I can't find a solution.

$ r(k, l) \leq r(k -1, l) + r(k, l-1) $ $ r(k,k) \geq 2^{\frac{k}{2}} $ $ r(k,l) = r(l,k) $

  • 0
    Your three theorems will not be enough so you will need to think some more. You could use them to prove $2r(k,k) \ge r(k+1,k+1)$, but the inequality is pointing in the wrong direction.2011-09-20

2 Answers 2

2

Complements to Brian's answer. When G' has a $(k+1)$-clique: Since G' is the disjoint union of $G$ and $K_k$, in addition $K_k$ doesn't contain a $(k+1)$-clique, we get $G$ has a $(k+1)$-clique thus $G$ clearly has a $k$-clique. When G' has a stable set of $(k+1)$ vertices: Since $K_k$ has one and only one indepentdent vertice(if there're two, they are connected due to the completeness of $K_k$, a contradiction). Thus $G$ has a stable set of $(k+1)-1=k$ vertices. Thus $G$ has either a $k$-clique or a stable set of $k$ vertices.

1

Suppose that $G$ is a graph with at least $r(k+1,k+1) - k$ vertices. Let G' be the disjoint union of $G$ and $K_k$, the complete graph on $k$ vertices. Then G' has at least $r(k+1,k+1)$ vertices, so it has either a $(k+1)$-clique or a stable set of $(k+1)$ vertices. Can you see how to use these to find either a $k$-clique or a stable set of $k$ vertices in $G$?