Rock-paper-scissors...

Question

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"]

Answer 1

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.