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

| cite | improve this answer | |
$\endgroup$
  • $\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 '15 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 '15 at 17:11
4
$\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)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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