# Graph theory and Burnside's lemma

How many are non isomorphic tournaments (directed clique) with $n=5$ vertices?

I'm not sure how to understand isomorphism here. This problem was in the set of problems on Burnside's lemma but it's different than the rest, I think. Normally I was asked to count the number of significantly different colorings of necklace or chessboard which was very nice and the group for Burnside's lemma was given explicit - simply all rotations. But here I don't know what is the group, how to approach this.

Is it very difficult to solve this in general - for $n\in\mathbb{N}$?

Will it be useful here the term: graph automorphism? How to understand it? Because I have it in the next problem.

-

## 1 Answer

Judging from the question, a lot of the confusion is converting from group actions terminology to graph theory terminology. I'll try to clarify.

Let $\mathcal{A}$ be the set of labelled tournaments on the vertex set $\{1,2,\ldots,5\}$. We know $$|\mathcal{A}|=2^{{5 \choose 2}}=1024$$ since each edge can go in one of two directions. The symmetric group $S_5$ acts on $\mathcal{A}$ by permuting the vertex labels.

Pick an arbitrary tournament $T \in \mathcal{A}$ and an arbitrary permutation $\alpha \in S_5$.

• We say that $T$ and $\alpha(T)$ are isomorphic (which we intuitively interpret as meaning structurally equivalent).

• We can define an equivalence relation on the set of $5$-vertex tournaments, with tournaments $A$ and $B$ being equivalent if $\alpha(A)=B$ for some $\alpha \in S_5$. The equivalence classes are called isomorphism classes or orbits. The number of non-isomorphic tournaments, is the number of orbits.

Burnside's Lemma gives a formula the number of orbits under a group action. However, to use it, we need to find a way of counting the number of tournaments $T$ that are "fixed" by each $\alpha \in S_5$.

• If $\alpha(T)=T$, then $\alpha$ is said to be an automorphism of $T$. (Alternatively, we can say that $\alpha$ stabilises $T$.) This is our notion of "fixed".

Thus, to use Burnside's Lemma, for each $\alpha \in S_5$, we need to find the size of $$F_\alpha:=\{T \in \mathcal{A}:\alpha(T)=T\}$$ which gives the number of orbits (the number of non-isomorphic tournaments) as: $$\frac{1}{|S_5|} \sum_{\alpha \in S_5} |F_\alpha|.$$

This might sound horrid (since $|S_5|=120$), but it's made much easier by the observation that $|F_\alpha|$ varies only with the cycle structure of $\alpha$.

The possible cycle structures are:

• (1,1,1,1,1),
• (2,1,1,1),
• (2,2,1),
• (3,1,1),
• (3,2),
• (4,1),
• (5).

For each of these cycle structures, e.g. (2,2,1), we can pick a representative, e.g. $\beta=(12)(34)(5)$, and find $|F_\beta|$.

• Hint: The number of permutations with a given cycle structure is given here, for example.

• Hint: Automorphisms of tournaments must have odd order. (Why?) This means we need only consider the cycle structures $(1,1,1,1,1)$, $(3,1,1)$ and $(5)$.

Thus, the question is really asking for $|F_{(1)(2)(3)(4)(5)}|=1024$, $|F_{(123)(4)(5)}|$ and $|F_{(12345)}|$.

-