2
$\begingroup$

Hello,

I am wondering, if we have a complete graph on $n$ vertices, and we have $k$ colours so that every edge of the graph is coloured with one of these colours, what is the least $n$ such that we will always be able to find a monochromatic cycle of length $m$?

It would be great to find a function F($k,m$) to give such a least $n$, or at least find good lower and upper bounds on it.

Improve this question
$\endgroup$
2
  • $\begingroup$ This is bounded above by the $n$ needed to guarantee a monochromatic $K_m$, which is a Ramsey number. $\endgroup$
    – Will Sawin
    Commented Jul 15, 2012 at 13:51
  • $\begingroup$ Will Sawin is right, but I would expect that a considerably smaller $n$ would work, once $m$ is larger than 3. $\endgroup$
    – Andreas Blass
    Commented Jul 15, 2012 at 13:54

2 Answers 2

Reset to default
2
$\begingroup$

You in the realms of extensions of Ramsey Theory here, so general, precise answers may be a bit thin on the ground.

There are at least a couple of known results:

$2^{k} \leq F(k,3) \leq 3k!$

and

$F(k,4) \leq k^{2} + k + 1$

These lecture slides give a start: https://www.dpmms.cam.ac.uk/~dc340/Ramsey-course.html

Improve this answer
$\endgroup$
2
$\begingroup$

A lot of data regarding specific instances of this problem can be found in Radziszowski's survey, see the part "survey" starting on page 36.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .