On the capacity of digraphs (Q1378288): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2055579046 / rank | |||
Normal rank |
Latest revision as of 22:00, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the capacity of digraphs |
scientific article |
Statements
On the capacity of digraphs (English)
0 references
7 September 1998
0 references
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.
0 references
digraph
0 references
capacity
0 references
tournament
0 references