<p>I am looking about the following Ramseyish theorem with additional structure on tournament (see [1]). </p>

<blockquote>
  <p>For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ colored with $k$ colors, there exists necessary a path of length $2$ monochromatic.</p>
</blockquote>

<p>It is a direct consequence of Ramsey theorem when applied to triangle on the underlying colored graph. Now, I am looking for estimate on $T(k)$, that is the minimum size such that we are certain that a path of length $2$ exists. Remarks that $T(k)$ has to be at least larger than $k$. Indeed, otherwise you can associate to each vertices a unique color that you use to label its outgoing edges.</p>

<p>Actually, I don't really need the  precise value but simply to know if it is polynomial or exponential. Note that the same question for coloring numbers in $[n]$ (i.e. the tournament is a full order) sounds already non trivial, or maybe I miss something? </p>

<p>[1]: Wikipedia page for tournament <a href="https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Ramsey_theory" rel="noreferrer">https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Ramsey_theory</a> </p>

CC BY-SA 4.0
2018-07-07T08:51:22.607Z
Yes, it is coloring the edge and length is about number of edges as well.
C.P.
CC BY-SA 4.0
2018-07-07T09:04:09.050Z
No, it is not working, $T(k)$ has to be large. If $T(k)<k$ you have an obvious counter-example by associating each vertices to a unique color labeling its outgoing edges.
C.P.
CC BY-SA 4.0
2018-07-07T09:04:46.007Z
(Sorry, I posted this in my replies as en edit but it seems to have disappear ... the question is edited to take this remark into account)
C.P.
CC BY-SA 4.0
2018-07-07T11:24:25.807Z
I didn't notice that you are talking about tournaments not complete graphs
Saeed
<graph-theory><ramsey-theory>
Ramsey number for path in a colored tournament
C.P.
# Ramsey number for path in a colored tournament

(Asked by: username_0 on 2018-07-06)

I am looking about the following Ramseyish theorem with additional structure on tournament (see [1]).

> For all number of colors $k$, there exists $n=T(k)$ such that all tournaments of size $n$ colored with $k$ colors, there exists necessary a path of length $2$ monochromatic.

It is a direct consequence of Ramsey theorem when applied to triangle on the underlying colored graph. Now, I am looking for estimate on $T(k)$, that is the minimum size such that we are certain that a path of length $2$ exists. Remarks that $T(k)$ has to be at least larger than $k$. Indeed, otherwise you can associate to each vertices a unique color that you use to label its outgoing edges.

Actually, I don't really need the precise value but simply to know if it is polynomial or exponential. Note that the same question for coloring numbers in $[n]$ (i.e. the tournament is a full order) sounds already non trivial, or maybe I miss something?

[1]: Wikipedia page for tournament <https://en.wikipedia.org/wiki/Tournament_(graph_theory)#Ramsey_theory>

**Tags:** graph-theory, ramsey-theory

> **Comments:**
> **username_0**: Yes, it is coloring the edge and length is about number of edges as well.  
> **username_0**: No, it is not working, $T(k)$ has to be large. If $T(k)<k$ you have an obvious counter-example by associating each vertices to a unique color labeling its outgoing edges.  
> **username_0**: (Sorry, I posted this in my replies as en edit but it seems to have disappear ... the question is edited to take this remark into account)  
> **username_1**: I didn't notice that you are talking about tournaments not complete graphs  

---

## 0 answers

