Let $r > 1$ be an integer. Prove that there is an integer $n_0$ such that for every integer $n\geq n_0$ and every directed graph $G = (\{1,...,n\}, E)$ without loops, $G$ has an induced subgraph $H$ with $r$ vertices and $H$ is a linear/total order OR $H$ has no directed edges at all, OR $H$ has edges in both directions between any two distinct vertices.
Hints: Find a appropriate 4-coloring of $[\{1,...,n\}]^2$ and use the Ramsey number $R(2,4,r)$
I don't really know where to start to be honest. I guess I show use the Ramsey theorem in some form but I'm confused because I can't find any examples or figuring out by myself how to use it when I have a directed graph to begin with.
How can I show that a subgraph in the above case must have any of these three properties as above?
Any help would be highly appreciated. I wish I could present more effort on my part but I really find Ramsey theory quite challenging.
Remember that if $n = R(2,4,r)$ then any 4-coloring of the edges of the complete graph $K_n$ yields a monochromatic $K_r$.
Let $G$ be a directed graph on $n = R(2,4,r)$ vertices. Now consider the coloring $c$ of the edges of $K_n$ as follow:
$c(\{i, j\}) = \begin{cases} 0 & (i,j) \notin E(G) \text{ and } (j,i) \notin E(G) \\ 1 & i \lt j \text{ and } (i,j) \in E(G)\\ 2 & i \lt j \text{ and } (j,i) \in E(G)\\ 3 & (i,j) \in E(G) \text{ and } (j,i) \in E(G) \end{cases}$
By the definition of $n$, we must have a monochromatic $K_r$. If the color of $K_r$ is $0$ then we have an $H$ with no directed edges, if it is $1$ or $2$ we have an $H$ which is a total order and if it is $3$ we have an $H$ with edges in both directions.