Abstract | ||
---|---|---|
An n-tournament is a complete labelled digraph on n vertices without loops or multiple arcs. A tournament's score sequence is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The number Sn of distinct score sequences arising from all possible n-tournaments, as well as certain generalizations are investigated. A lower bound of the form Sn > C14nn52 (C1 a constant) and an upper bound of the form Sn < C24nn2 are proved. A q-extension of the Catalan numbers c1(q)=1 and cn(q)=∑i−1n−1ci(q)cn−1(q)qi(n−i−1)is defined. It is conjectured that all coefficients in the polynomial Cn(q) are at most O(4nn3). It is shown that if this conjecture is true, then Sn<C34nn52 |
Year | DOI | Venue |
---|---|---|
1983 | 10.1016/0097-3165(83)90008-0 | Journal of Combinatorial Theory, Series A |
Field | DocType | Volume |
Discrete mathematics,Tournament,Combinatorics,Polynomial,Vertex (geometry),Upper and lower bounds,Catalan number,Asymptotic analysis,Conjecture,Digraph,Mathematics | Journal | 35 |
Issue | ISSN | Citations |
2 | 0097-3165 | 8 |
PageRank | References | Authors |
2.84 | 4 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Kenneth J. Winston | 1 | 52 | 7.83 |
Daniel J. Kleitman | 2 | 854 | 277.98 |