6
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • $\begingroup$ Yes, it is coloring the edge and length is about number of edges as well. $\endgroup$ – C.P. Jul 7 '18 at 8:51
  • $\begingroup$ 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. $\endgroup$ – C.P. Jul 7 '18 at 9:04
  • $\begingroup$ (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) $\endgroup$ – C.P. Jul 7 '18 at 9:04
  • $\begingroup$ I didn't notice that you are talking about tournaments not complete graphs $\endgroup$ – Saeed Jul 7 '18 at 11:24

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.