Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
"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
1  
"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
2  
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

1 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.

share|improve this answer
    
The McKay paper is available [here][1] [1]: cs.anu.edu.au/~bdm/papers/rt.pdf –  Kristal Cantwell Apr 10 '12 at 17:23
5  
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

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.