On the capacity of digraphs (Q1378288)

For a digraph \(G= (V,E)\) let \(\omega(G^n)\) denote the maximum possible cardinality of a subset \(S\) of \(V^n\) in which for every ordered pair of \(n\)-tuples \((u_1, u_2,\dots, u_n)\) and \((v_1, v_2,\dots, v_n)\) of members of \(S\) there is some \(i\) with \(1\leq i\leq n\) such that \((u_i,v_i)\in E\). The capacity \(C(G)\) of \(G\) is \(C(G)= \lim_{n\to\infty} [(\omega(G^n))^{1/n}]\). It is shown that if \(G\) has maximum outdegree \(d\), then \(C(G)\leq d+1\). It is also shown that for every \(n\) there is a tournament \(T\) on \(2n\) vertices whose capacity is at least \(\sqrt{n}\), whereas the maximum number of vertices in a transitive subtournament of \(T\) is only \(O(\log n)\). This disproves a conjecture of Körner and Simonyi.