Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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) $$

share|improve this question
    
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. –  Henry Sep 20 '11 at 22:14

2 Answers 2

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$?

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.