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

Improve this question
$\endgroup$
4
  • $\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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.