2

The question I am looking to answer asks the following:

How many non-isomorphic size 5 tournaments exist?

The most straightforward way to approach this problem is Burnside's Lemma, which states that:

$$|X/G| = (\frac{1}{|G|})\sum_{∈G}|_|$$

where |X/G| is the number of orbits, |G| is the size of the group, and $|_|$ is the number of fixed points of set X under a given symmetry ∈ G. In terms of a tournament, T, of size 5, the size of the group is equal to the number of permutations of the vertices of T, which is simply 5! = 120.

Further, the number of fixed points varies with the cycle structure of T. There are seven cycle structures of T, namely:

  1. (1, 1, 1, 1, 1): This is the identity; fixes every tournament. There are 5 choose 2 edges; each edge can go both ways. Results in $2^{\binom{5}{2}}=1024$.
  2. (2, 1, 1, 1): If two vertices are swapped naturally the resulting graph isn't the original since the edge can't change direction.
  3. (2, 2, 1): Same as above.
  4. (3, 1, 1): Formula, (given by this post gives the number of fixed points as 20.
  5. (3, 2): See 2; the number of fixed points is 0.
  6. (4, 1): The number of fixed points is 0 because the diagonals can't be preserved.
  7. (5): The aforementioned formula gives the number of fixed points to be 24.

Applying Burnside's Lemma gives an answer of $\frac{1024+20+24}{120}$ which is not only incorrect but is not even an integer. It's well known that there are exactly 12 non-isomorphic tournaments of size 5, so what went wrong exactly in my reasoning? No matter how many times I check my work I can't figure out how the numerator can possibly ever equal 1440.

ancient mathematician
  • 14,102
  • 2
  • 16
  • 31
Jaculex9000
  • 43
  • 1
    I think that you need to explain how you are using your reference in (4) and (7). In (7) for example I see $24$ 5-cycles, but each seems to me to fix $4$ tournaments. In (4) I see $20$ 3-cycles, but each seems to me to fix $16$ tournaments. – ancient mathematician Feb 27 '21 at 11:56

1 Answers1

4

You have already (correctly) shown that the only permutation types with fixed points are the identity (one permutation) and those of types "3+1+1" (20 permutations) and 5 (24 permutations).

Now, as you have (also correctly) stated, the identity fixes all 1024 tournaments, but you haven't taken into account the numbers of fixed tournaments of the other two permutation types. These are

  • 16 tournaments for a permutation of type "3+1+1" and
  • 4 tournaments for a permutation of type "5".

Thus, the number of non-isomorphic tournaments is

$$\frac{1\cdot1024+20\cdot16+24\cdot4}{120}=\frac{1440}{120}=12.$$

jpvee
  • 3,563