Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose the independent number of a graph is bounded. How small the clique number can be? linear? It seems to be a natural problem to ask. but I could not find any reference. Thanks.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

This is basically a question in Ramsey theory. The Ramsey number $R(s, t)$ is the minimum integer $n$ for which every red-blue coloring of the edges of a complete $n$-vertex graph induces either a red complete graph of order $s$ or a blue complete graph of order $t$. So for example Kim (Random Structures and Algorithms 7 (1995), 173-207) showed that $R(3,t)\asymp t^2/\log t$. Roughly speaking this means that a graph with $t^2/\log t$ vertices with independence number at most 2 must have a clique of size $t$. So in this case the clique number grows like the square root of the number of vertices of the graph. I'm not sure what the best known results are in general but this should point you to the right literature.

share|improve this answer
    
Thanks a lot! this is exact what i want. –  Jian Li May 20 '10 at 14:36

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.