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)$?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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).

Improve this answer
$\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
    Commented 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
    Commented 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)$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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