On the capacity of digraphs (Q1378288): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    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

    Identifiers