Counting tournament score sequences

EUROCOMB’23

Anders Claesson Mark Dukes Atli Fannar Franklín Sigurður Örn Stefánsson

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-040

PDF
Abstract
The score sequence of a tournament is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The problem of counting score sequences of a tournament with $n$ vertices is more than 100 years old (MacMahon 1920). In 2013 Hanna conjectured a surprising and elegant recursion for these numbers. We settle this conjecture in the affirmative by showing that it is a corollary to our main theorem, which is a factorization of the generating function for score sequences with a distinguished index. We also derive a closed formula and a quadratic time algorithm for counting score sequences.

Pages:
290–297
References

Max Alekseyev. https://oeis.org/A145855/a145855.txt, 2008.

Arthur Cayley. A theorem on trees, volume 13 of Cambridge Library Collection - Mathematics, pages 26--28. Cambridge University Press, 2009.

Shane Chern. An extension of a formula of Jovovic. Integers, 19:Paper No. A47, 2019.

Anders Claesson, Mark Dukes, Atli Fannar Franklín, and Sigurdur Örn Stefánsson. Counting tournament score sequences. Proceedings of the American Mathematical Society, to appear. doi:10.1090/proc/16425. arXiv:2209.03925.
https://doi.org/10.1090/proc/16425

P. Erdős, A. Ginzburg, and A. Ziv. Theorem in the additive number theory. Bull. Res. Council Israel Sect. F, 10F(1):41-43, 1961.

Frank Harary and Leo Moser. The theory of round robin tournaments. Amer. Math. Monthly, 73:231-246, 1966.
https://doi.org/10.1080/00029890.1966.11970749

OEIS Foundation Inc. The Online Encyclopedia of Integer Sequences. https://oeis.org, 2021.

Daniel J Kleitman and Kenneth J Winston. Forests and score vectors. Combinatorica, 1(1):49-54, 1981.
https://doi.org/10.1007/BF02579176

H. G. Landau. On dominance relations and the structure of animal societies: III. The condition for a score structure. Bull. Math. Biophys., 15:143-148, 1953.
https://doi.org/10.1007/BF02476378

P. A. MacMahon. An American tournament treated by the calculus of symmetric functions. Quart. J. Math., 49:1-36, 1920. Reprinted in Percy Alexander MacMahon Collected Papers, Volume I, George E. Andrews, ed., MIT Press, 1978.

T. V. Narayana and D. H. Bent. Computation of the number of score sequences in round-robin tournaments. Can. Math. Bull, 7(1):133-136, 1964.
https://doi.org/10.4153/CMB-1964-015-1

John Riordan. The number of score sequences in tournaments. J. Combinatorial Theory, 5:87-89, 1968.
https://doi.org/10.1016/S0021-9800(68)80032-8

John Riordan. Erratum: "The number of score sequences in tournaments". J. Combinatorial Theory, 6:226, 1969.
https://doi.org/10.1016/S0021-9800(69)80130-4

Richard P. Stanley. Decompositions of rational convex polytopes. In J. Srivastava, editor, Combinatorial Mathematics, Optimal Designs and Their Applications, volume 6 of Annals of Discrete Mathematics, pages 333-342. Elsevier, 1980.
https://doi.org/10.1016/S0167-5060(08)70717-9

Paul K. Stockmeyer. Counting various classes of tournament score sequences. arXiv:2202.05238v1, 2022.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Anders Claesson, Mark Dukes, Atli Fannar Franklín, Sigurður Örn Stefánsson

PDF