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, 2018 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, 2018 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, 2018 at 9:04
  • $\begingroup$ I didn't notice that you are talking about tournaments not complete graphs $\endgroup$
    – Saeed
    Jul 7, 2018 at 11:24

0

Reset to default

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.