Skip to main content
1 of 3
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147