MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Hi. For k,l positive integers let h(k,l) be the least integer with the property that in graph on h(k,l) vertices either there is a closed circuit of k or fewer lines or that the graph contains l independent points. It is given that for sufficiently large l, h(k,l)>l^{1+1/2k}. Now how do we conclude from here that for all r, there is an r-chromatic graph with no k-polygon in it. Clearly a graph on floor(r^{1+1/2k}) vertices will not have a k-polygon in it, but how can we construct it in such a way that it is also r-chromatic?

share|cite|improve this question
Homework? – Thomas Kalinowski May 4 '11 at 15:24
No it isnt homework. I am trying to read from a paper by Erdos. – Shahab May 5 '11 at 8:05
If you want to get a graph that has girth at least $k$ and needs at least $r$ colors, take an $n$ (number of vertices) so large that $nr^{1+1/2k}\leqslant n^{1+1/2k}$ and apply your given inequality with $l=n/r$. – Thomas Kalinowski May 5 '11 at 8:35

Your Answer


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

Browse other questions tagged or ask your own question.