Find the number of different tournaments with 5 vertices

Question

We consider tournaments $A$ and $B$ to be equal if they are isomorphic or if $V[A]=V[B]$ and $\forall_{v, w\in V[A]}\{v,w\}\in E[A] \iff \{w,v\}\in E[A]$, that is if $A$ can be obtained by reversing every edge in B. There's only one such tournament for $n=1$ and $2$, and there's two for $n=3$, but for both $4$ and $5$ it becomes too tedious to calculate by hand. Is this supposed to be done using something from group theory? Early 3 numbers look like Fibonacci, but it's too little to conjecture anything yet.

Answer 1

This can be solved nicely using the Burnside's Lemma.

For $n=5$, the group of transformations to consider is $G = S_5 \oplus \mathbb{Z}_2$ ($S_5$ for permutations of vertices and $\mathbb{Z}_2$ for reversing or not reversing the edges). Now we have to calculate the sum $\frac{1}{|G|}\sum_{g \in G}{|X_g|}$, where $X_g$ is the set of fixed points of transformation $g$, i.e. all tournaments that are left unchanged after applying $g$. Note that we require that they remain exactly the same, not just isomorphic.

We have $5! \cdot 2 = 240$ possible transformations, which is a lot, but permutations with the same cycle notation are equivalent. So we have:

• Identity permutation, $1$: if we don't reverse the edges, there are $2^{10} = 1024$ fixed points (all tournaments); if we do reverse the edges, we always get a completely different tournament, so the number of fixed points is $0$.

• [a,b][c][d][e], $\binom{5}{2} = 10$: when we permute the 2 vertices in the cycle, the edge between them gets reversed, so in order to get the initial tournament we would have to reverse it once more - but we can only reverse either all edges or none, so the number of fixed points is $0$.

• [a,b][c,d][e], $\frac{1}{2} \cdot \binom{5}{2} \cdot \binom{3}{2} = 15$: the number of fixed points without reversing the edges is again $0$, but when we do reverse the edges, we can actually get the initial tournament; there are 2 edges ($a-b$ and $c-d$) that can be directed arbitrarily, and 4 cycles with 2 edges, where in each cycle edges must point in opposing directions (e.g. $a\rightarrow c$ and $d\rightarrow b$ or $c\rightarrow a$ and $b\rightarrow d$) so that after permuting the vertices and reversing the edges we get the same tournament; hence there are $2^6=64$ fixed points.

• [a,b,c][d][e], $2 \cdot \binom{5}{3} = 20$: there is an odd-length vertex cycle here, so there are no fixed points when we reverse the edges; without reversing the edges we have 1 free edge and 3 edge cycles, where in each cycle all edges must point in the same direction, so there are $2^4=16$ fixed points.

• [a,b,c][d,e], $2 \cdot \binom{5}{3} = 20$: the 2-cycle requires reversing the edges, but there is also the 3-cycle, so no fixed points here.

• [a,b,c,d][e], $3! \cdot 5 = 30$: again no fixed points, because of the diagonals in the 4-cycle.

• [a,b,c,d,e], $4! = 24$: there are 2 odd-length edge cycles, so only $2^2 = 4$ fixed points without reversing the edges.

Now we sum everything up and get: $$\frac{1}{|G|} \cdot (1024 + 15 \cdot 64 + 20 \cdot 16 + 24 \cdot 4) = \frac{2400}{240} = 10$$

Hence there are $10$ different tournaments with 5 vertices.