Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There are a lot of papers on degree/score sequences of tournaments, starting on a given sequence, and constructing a tournament that has that degree sequence, and so forth.

But what if you start at a given score sequence, and ask "how many tournaments, up to isomorphism, have this score sequence?" For {0, 1, 2, ..., n-1} the answer is 1, and for a few other sequences.

If we set aside the transitive tournaments for a moment, are these other sequences (for whom the answer is 1) simply miscellaneous? It seems as the sequences get longer the number of possible tournaments grows, so is it the case that these "miscellaneous" sequences eventually stop?

Or is there some nontrivial infinite class that I am not noticing?

I suppose one could ask about connected digraphs too, not only tournaments.

share|improve this question
For infinite classes, note that you can break the tournament into 1's and 3's. So $\{1,1,1,3,4,\ldots n-1\}$ is an example, as is $\{1,1,1,4,5,5,5,7,8,\ldots n-1 \}$ –  Ross Millikan Oct 30 '12 at 19:44
Sorry I don't understand, what do you refer to exactly "breaking into 1's and 3's"? –  John Smith Oct 30 '12 at 20:08
With three players you can have each go 1-1 and know what happened up to isomorphism. With more you can make groups of 1 and 3, have it transitive between groups, and 1-1 in the groups of 3. –  Ross Millikan Oct 30 '12 at 20:25
So you mean a round robin of 3, followed by a guy who beat them all, followed by a round robin of 3 who beat all those guys, followed by a guy who beat everyone mentioned so far... Is that what you mean? –  John Smith Oct 30 '12 at 20:58
Exactly. This is an infinite class but still rare –  Ross Millikan Oct 30 '12 at 21:00
show 1 more comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.