Skip to main content
added 47 characters in body
Source Link
David E Speyer
  • 156.4k
  • 14
  • 422
  • 763

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.

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 comes with a natural $S_n$-action.

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.

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.

Source Link
David E Speyer
  • 156.4k
  • 14
  • 422
  • 763

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 comes with a natural $S_n$-action.

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.