1
$\begingroup$

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.

  • 0
    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 \}$2012-10-30
  • 0
    Sorry I don't understand, what do you refer to exactly "breaking into 1's and 3's"?2012-10-30
  • 0
    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.2012-10-30
  • 0
    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?2012-10-30
  • 0
    Exactly. This is an infinite class but still rare2012-10-30
  • 0
    I wonder is there any nice way to classify the sequences for whom the answer is "1"? Seems the obvious question. Assuming we haven't already finished doing so.2012-10-30

0 Answers 0