# Rock-paper-scissors…

A directed graph whose underlying undirected graph is complete is called a tournament. Let us call a (finite) directed graph balanced if every vertex has as many incoming as outgoing edges. The question is: Have balanced tournaments been classified? (The weakest form of "classify" might be: given $n$, determine the number of balanced tournaments on $n$ vertices up to isomorphism.)

Here are some elementary observations:

• for even $n$ there is no balanced tournament on $n$ vertices.

• for odd $n$ there is a standard balanced tournament on $n$ vertices: take as vertex set $\{0,\ldots,n-1\}$ and include an arrow from $i$ to $i+j \mod n$ for $1 \le j \le (n-1)/2$. (The automorphism group is cyclic of order $n$.)

• for $n=1$, $n=3$, and $n=5$ the only balanced tournament is the standard one.

• for $n=7$ there is a non-standard balanced tournament: to construct it invert an appropriate $3$-cycle in the standard b.t., to see that it is non-standard look at the "out-link" of an appropriate vertex. (The automorphism group is trivial.)

• One can take a sort of wreath product to construct examples whose automorphism groups are abelian, non-cyclic. There are other constructions to produce examples.

The motivation for this question is simply the following: the b.t. on $3$ vertices encodes the game rock-paper-scissors. The one on $5$ vertices encodes the game rock-paper-scissors-lizard-Spock (if you don't know it, you can figure it out once you know that "lizard poisons Spock" [edit, thanks to Ramiro de la Vega:] and that "paper disproves Spock"). From $7$ on there is some choice, how much and which?

Also: does someone know the proper expression for "balanced"? [edit: according to David Speyer the term in this context is "regular tournament"]

-
"balanced" seems to be the correct terminology, see en.wikipedia.org/wiki/Directed_graph –  Koen S Apr 10 '12 at 15:26
One way of approaching this problem would be to decompose the complete graph into cycles. Adding orientation to these cycles gives you a balanced tournament. Moreover each balanced tournament arises in this way. There is a lot of literature on such decompositions. For example decompositions into 3-cycles are equivalent with Steiner triple systems. –  Koen S Apr 10 '12 at 15:49
"lizard poisons Spock" is not enough to figure it out. What if "paper dries lizard" instead of "lizard eats paper"? –  Ramiro de la Vega Apr 10 '12 at 16:05
Just a small nitpick: enumeration is not, I think, a weak from of classification. it's a whole different problem. –  Felix Goldberg Apr 10 '12 at 16:20
I guess "classification" is a soft term. For me, a classification is a one-to-one correspondence to a set of data together with a dictionary that allows you to just read off the answers to many interesting questions about the original objects, or at least answer them easily. In non-trivial cases, a classification will never enable you to answer all questions easily, so one has to specify "interesting questions". In this case "what is the number of instances of a given order?" should be one and if it's the only one, then classification in the sense above reduces to enumeration. –  Stefan Witzel Apr 12 '12 at 6:32

Your sequence is Sloane A096368. Sloane links to this page, which has files of all examples up to $13$ vertices. MathSciNet has 30 papers with "regular tournament" in the title, none of which seem to know much about enumeration up to isomorphism. A quick scan of the papers with "balanced tournament" in the title suggests that that term means something else, so I would search on "regular tournament".

McKay proves an asymptotic formula for the number of LABELED regular tournaments of the form $2^{\binom{n}{2}} e^{-O(n \log n)}$. (See his paper for a much more precise statement.) Since the size of $n!$ is "only" $e^{O(n \log n)}$, we can deduce that the number of isomorphism classes is also $2^{\binom{n}{2}} e^{-O(n \log n)}$, and in particular goes to $\infty$ as $n \to \infty$.

I can say a bit more about the labeled problem, where we don't quotient by automorphism. This is Sloane A007079.

The number we want is the coefficient of $\prod_{i=1}^{n} x_i^{(n-1)/2}$ in $\prod_{1 \leq i < j \leq n} (x_i+x_j)$; each factor corresponds to an edge and choosing $x_i$ or $x_j$ corresponds to orienting this edge. This polynomial is the Schur polynomial $s_{(n-1)(n-2)\cdots 321}(x_1, \ldots, x_n)$; this follows from the ratio of alternants formula. So you are looking for the Kotska number $$K_{(n-1)(n-2)\cdots 321,\ mmm \cdots m} \ \mbox{where} \ m=(n-1)/2.$$

I don't think there is a closed formula for this Kotska number.

Here's something interesting that I couldn't get to work, but maybe will help someone else. Essentially by definition, this Kostka number is the dimension of the space of diagonal invariants in the representation of $SL_n$ associated to the partition $(n-1, n-2, \cdots, 2,1)$. And this vector space comes with a natural $S_n$-action, from the embedding of $S_n$ into $SL_n$.

Unfortunately, they don't match! When $n=3$, there are two labeled tournaments. (Orient the triangle clockwise or counterclockwise.) So a permutation $\sigma$ in $S_3$ either preserves or switches the tournaments based on the sign of $\sigma$. The corresponding permutation representation of $S_3$ is the direct sum of the trivial and the sign rep. By way of contrast, the representation of $S_3$ on the diagonal invariants of $V_{21}$ is the $2$-dimensional irrep of $S_3$.

Still, it would be really cool if we could find a deeper relation between these two representations of $S_n$ than simply the fact that they have the same dimension. In particular, remember that the number of orbits in a permutation representation is always the multiplicity of the trivial rep, so one could imagine counting isomorphism classes by representation theory if we can find a good alternate description of the tournament representation.

-
The McKay paper is available [here][1] [1]: cs.anu.edu.au/~bdm/papers/rt.pdf –  Kristal Cantwell Apr 10 '12 at 17:23
A few small comments: (1) It is Kostka, not Kotska. ;) (2) The average number of automorphisms of a regular tournament is $1+o(1)$, as proved in cs.anu.edu.au/~bdm/papers/tourn_dig.pdf (Random Structures and Algorithms, 16 (2000) 47-57) so the asymptotic number of isomorphism types is the asymptotic number of labelled ones divided by $n!$ . (3) All automorphisms of a tournament have odd order, if that helps. (4) It would very exciting if the ideas you mention could lead to more understanding of these questions. –  Brendan McKay Apr 11 '12 at 1:40