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