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

  • $\begingroup$ 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. $\endgroup$ – bof Mar 28 at 23:31
  • $\begingroup$ See OEIS A122027. $\endgroup$ – 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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.