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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
This is basically a question in Ramsey theory. The Ramsey number $R(s, t)$ is the minimum integer $n$ for which every redblue 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), 173207) 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. 

