User stefan witzel - MathOverflow

Rock-paper-scissors...

2012-04-10T15:17:29Z

A directed graph whose underlying undirected graph is complete is called a tournament. Let us call a (finite) directed graph balanced if every vertex has as many incoming as outgoing edges. The question is: Have balanced tournaments been classified? (The weakest form of "classify" might be: given $n$, determine the number of balanced tournaments on $n$ vertices up to isomorphism.)

Here are some elementary observations:

for even $n$ there is no balanced tournament on $n$ vertices.
for odd $n$ there is a standard balanced tournament on $n$ vertices: take as vertex set $\{0,\ldots,n-1\}$ and include an arrow from $i$ to $i+j \mod n$ for $1 \le j \le (n-1)/2$. (The automorphism group is cyclic of order $n$.)
for $n=1$, $n=3$, and $n=5$ the only balanced tournament is the standard one.
for $n=7$ there is a non-standard balanced tournament: to construct it invert an appropriate $3$-cycle in the standard b.t., to see that it is non-standard look at the "out-link" of an appropriate vertex. (The automorphism group is trivial.)
One can take a sort of wreath product to construct examples whose automorphism groups are abelian, non-cyclic. There are other constructions to produce examples.

The motivation for this question is simply the following: the b.t. on $3$ vertices encodes the game rock-paper-scissors. The one on $5$ vertices encodes the game rock-paper-scissors-lizard-Spock (if you don't know it, you can figure it out once you know that "lizard poisons Spock" [edit, thanks to Ramiro de la Vega:] and that "paper disproves Spock"). From $7$ on there is some choice, how much and which?

Also: does someone know the proper expression for "balanced"? [edit: according to David Speyer the term in this context is "regular tournament"]

Answer by Stefan Witzel for Is this the CAT(0) metric on an affine building?

2011-08-29T13:16:47Z

You might also want to look at chapters 10 and 11 in the book by Abramenko and Brown. In particular Theorem 11.16.

Answer by Stefan Witzel for Properly Discontinuous Action

2011-06-30T21:15:57Z

Just two small remarks:

The action is properly discontinuous if it is proper and the group is is equipped with the discrete topology (compact then meaning finite, this accounts for some confusion, I guess).
I think in Definition 4 the conclusion should be $g = 1$. Then it means that the action is properly discontinuous and free (which for example Bredon calls properly discontinuous).

Answer by Stefan Witzel for Fundamental Examples

2010-04-13T18:32:39Z

$\operatorname{SL}_2(\mathbb{Z})$ and its action on the hyperbolic plane. It is the "minimal" example of mapping class groups and arithmetic groups. And one can already see a lot of the general behavior.

Comment by Stefan Witzel

2012-11-13T08:16:10Z

If someone is still interested in an explicit homomorphism: there is one in Example 2.5 of these notes by Keith Conrads: math.uconn.edu/~kconrad/blurbs/grouptheory/…

Comment by Stefan Witzel

2012-04-12T06:32:50Z

I guess "classification" is a soft term. For me, a classification is a one-to-one correspondence to a set of data together with a dictionary that allows you to just read off the answers to many interesting questions about the original objects, or at least answer them easily. In non-trivial cases, a classification will never enable you to answer all questions easily, so one has to specify "interesting questions". In this case "what is the number of instances of a given order?" should be one and if it's the only one, then classification in the sense above reduces to enumeration.

Comment by Stefan Witzel

2011-06-30T21:37:59Z

Of course, if a torsion-free group acts properly discontinuously, then it acts freely. So in that case the definitions are again equivalent.