
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.
Extremal problems in graph theory, Computational Theory and Mathematics, capacity, Directed graphs (digraphs), tournaments, Geometry and Topology, digraph, tournament, Theoretical Computer Science
Extremal problems in graph theory, Computational Theory and Mathematics, capacity, Directed graphs (digraphs), tournaments, Geometry and Topology, digraph, tournament, Theoretical Computer Science
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 22 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
