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 rchromatic graph with no kpolygon in it. Clearly a graph on floor(r^{1+1/2k}) vertices will not have a kpolygon in it, but how can we construct it in such a way that it is also rchromatic?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
