2
$\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$

4 Answers 4

8
$\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
8
$\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$
4
$\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$
2
$\begingroup$

The picture in this tweet gives you the minimal counterexample which is $n=3$. https://twitter.com/Jun_Gitef17/status/456056921405935617 The pairs that come in the diagonals of the hexagon are directed so that everyone has $d_{\mathrm{in}}=d_{\mathrm{out}}$.

For each pairs, a "paper can cover rock"-style explanation is provided in Japanese, but since it's out of topic, I'll leave it to your imagination.

$\endgroup$
1
  • $\begingroup$ To be more precise, this directed graph is not isomorphic to the "trivial construction", where you line up $n=7$ vertices in an $n$-gon shape, and then have directed edges connecting vertices that are distance $1,2,\ldots,(n-1)/2$ apart always in the (say) clock-wise direction. $\endgroup$ Feb 17 at 21:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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