-1
$\begingroup$

Let $T=(V,E)$ be a tournament. We call it regular if all vertices have the same out-degree. It is not hard to see that there are no regular tournaments on an even number of points.

Let $n>0$ be an integer. If $T_1, T_2$ are regular tournaments on $2n+1$ vertices, do we always have $T_1\cong T_2$?

$\endgroup$

3 Answers 3

5
$\begingroup$

No. Start with a $K_9$ and compose a tournament of directed cycles built by chords of same "length" in the 9-gon. So there are three $C_9$ and one $3C_3$ involved. Now if you reverse the orientation of just one $C_3$, the resulting tournament should be non isomorphic.

$\endgroup$
2
  • $\begingroup$ Where you have written "one $3C_3$', did you mean "three $C_3$"? $\endgroup$ Jul 26, 2016 at 22:50
  • 1
    $\begingroup$ @GerryMyerson Yes if you want. I looked at it as a 2-factor. :-) $\endgroup$
    – Wolfgang
    Jul 27, 2016 at 5:14
5
$\begingroup$

For $n=1$ you have the rock-paper-scissors tournament, and for $n=2$ it's the rock-paper-scissor-lizard-Spock tournament :). Already for $n=3$ there are three nonisomorphic tournaments which satisfy your regularity condition. You can see them here "Rock-Paper-Scissors Meets Borromean Rings", by Marc Chamberland and Eugene A. Herman. You can find the first few numbers of such tournaments in OEIS A096368.

$\endgroup$
3
$\begingroup$

For questions like this you should head for OEIS: http://oeis.org/A096368 .

Also, the asymptotic number of regular tournaments grows much faster than $n!$, so the number of isomorphism types must also grow fast. Combinatorica, 10 (1990) 367-377 .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.