For all $n\geq3$ does there always exist an $n$ vertex tournament without induced acyclic subgraphs of size $4$ or more?

Question

For all $n\geq3$ does there always exist an $n$ vertex tournament without induced acyclic subgraphs of size $4$ or more?

Context: causal graphs in relativistic quantum information

Answer 1

Let $f(k)$ be the mimimum number of vertices for which a tournament must have an acyclic induced subgraph of size $k$.

We prove $f(k)$ exists for all $k$.

Notice $f(2)=2$.

We now prove $f(k) \leq 2f(k-1)$ for $k\geq 3$ by induction.

Suppose a graph with $2f(k-1)$ vertices exists. Take a vertex $x$ and separate the remaining vertices depending on whether the edge to $x$ goes in or out.

Notice one of these groups has size at least $f(k-1)$ and must therefore contain an acyclic induced subgraph of size $k-1$, which is still acyclic when we add $x$ to it.

It follows $f(k)\leq 2^{k-1}$.