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

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

• Nope. Any tournament on $2^n$ vertices contains a transitive tournament on $n+1$ vertices. (Not sharp,) Proof: easy induction on $n$. Pick any vertex in your tournament of order $2^n$; either its in-degree or its out-degree is at least $2^{n-1}$. Etc. – bof Mar 28 at 23:31
• See OEIS A122027. – bof Mar 28 at 23:36

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}$$.