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$?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Where you have written "one $3C_3$', did you mean "three $C_3$"? $\endgroup$
    – Gerry Myerson
    Commented Jul 26, 2016 at 22:50
  • 1
    $\begingroup$ @GerryMyerson Yes if you want. I looked at it as a 2-factor. :-) $\endgroup$
    – Wolfgang
    Commented 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.

Improve this answer
$\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 .

Improve this answer
$\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.

Improve this answer
$\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$
    – Jun_Gitef17
    Commented Feb 17 at 21:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .