Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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)}|$.

share|improve this answer

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.