Counting tournament score sequences

DOI10.1090/PROC/16425MaRDI QIDQ6106038zbMATH OpenOpenAlexFDO

Authors Anders Claesson, Mark Dukes, Atli Fannar Franklín, Sigurdur Örn Stefánsson

Publication date 27 June 2023

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.03925

zbMATH Keywords

quadratic time algorithm for counting score sequences

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19) Enumeration in graph theory (05C30)

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.

Recommendations

• scientific article; zbMATH DE number 7732125
• Score sets in multitournaments. I. Mathematical results
• scientific article; zbMATH DE number 568801
• Asymptotic enumeration of tournaments with a given score sequence
• An algorithm to generate tournament score sequences

Cites work

• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 3102822 (Why is no real title available?)
• An extension of a formula of Jovovic
• Computation of the Number of Score Sequences in Round-Robin Tournaments
• Decompositions of Rational Convex Polytopes
• Erratum
• Forests and score vectors
• The On-Line Encyclopedia of Integer Sequences
• The Theory of Round Robin Tournaments
• The number of score sequences in tournaments

Cited in

(17)

• Calculating the frequency of tournament score sequences
• scientific article; zbMATH DE number 840688 (Why is no real title available?)
• Computing tournament sequence numbers efficiently with matrix techniques
• Asymptotic enumeration of tournaments with a given score sequence
• Tournament scoring problem
• Counting the number of round-robin tournament schedules
• scientific article; zbMATH DE number 7732125 (Why is no real title available?)
• On scores in tournaments
• Tournament Coding of Integer Sequences
• The stochastic sandpile model on complete graphs
• Construction of tournaments with a given score sequence
• scientific article; zbMATH DE number 4152408 (Why is no real title available?)
• Permutations with few inversions
• A note on the lacking polynomial of the complete bipartite graph
• Counting tournament brackets
• An algorithm to generate tournament score sequences
• Tournament sequences and Meeussen sequences

This page was built for publication: Counting tournament score sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106038)