7
$\begingroup$

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.

What are the best known upper and lower bounds for $P(k,c)$?

$\endgroup$

2 Answers 2

8
$\begingroup$

For $c=2$, it is a theorem of Gerencsér and Gyárfás that $P(k,2)=\lfloor (3k-2)/2 \rfloor$.

For $c=3$, Gyárfás, Ruszinkó, Sárközy and Szemerédi proved that for sufficiently large $k$, $P(k,3)=2k-1$ if $k$ is odd, and $2k-2$ if $k$ is even.

The exact asymptotics are unknown for larger values of $c$ (as far as I know).

$\endgroup$
2
  • $\begingroup$ I think these results would be for paths with $k$ vertices; the question is about paths of length $k$, so $k+1$ vertices. $\endgroup$
    – Jan Kyncl
    Apr 15, 2015 at 17:08
  • $\begingroup$ Yes, you are right that these results are for paths with $k$ vertices. For this question, I conveniently regarded a path of length $k$ as a path with $k$ vertices (the notion of the length of a path is somewhat ambiguous, although I usually consider the length as the number of edges). $\endgroup$
    – Tony Huynh
    Apr 15, 2015 at 17:11
5
$\begingroup$

For the multi-color Ramsey numbers of even cycles, Luczak, Simonovits and Skokan proved that $R(C_k;c)\le ck+o(k)$ for fixed number $c$ of colors and $k\rightarrow \infty$.

For odd cycles, Bondy and Erdos claim that $R(C_k;c)\le (c+2)!k$.

Both upper bounds apply also for paths with $k$ vertices since $P(k-1,c) \le R(C_k;c)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.