MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

For $k,l$ positive integers let $h(k,l)$ be the least integer with the property that in a graph on $h(k,l)$ vertices either there is a closed circuit of $k$ or fewer lines, or the graph contains $l$ independent points.

It is given that for sufficiently large $l$, that $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 $\lfloor r^{1+1/2k}\rfloor$ 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? mathoverflow.net/faq – 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
2  
@ThomasKalinowski Why not leave this comment as an answer? – Yemon Choi Jun 3 at 13:20

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

share|cite|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.