For docs on how Nauty works, check out this paper: http://users.cecs.anu.edu.au/~bdm/nauty/pgi.pdf The newer Traces program does it slightly differently and sometimes (oftentimes?) more effectively. Am I correct that it could also be represented by a 1 on every
black square of the checkerboard and a 0 on every red square?
As long as the red squares go from top left to bottom right (the main diagonal), this should work. That essentially says evens go to odds and odds to evens, but odds do not go to odds and evens do not go to evens, so it is a valid labeling of K4,4. The matrix I showed above says values 0..3 go to values 4..7 and vice versa, but 0..3 don't go to 0..3 and 4..7 don't go to 4..7. This automorphism group has size 1152 so there are a lot of labelings.
ordering. But apparently not, at least not without deciding on who plays whom before knowing the results of any games. However, if, even
Probably of a complete ordering is 1152/40320, so while you can't guarantee it, it's not impossible.
seems to be the case, the result may be a partial ordering, we have to count how many of those are possible too. For instance if the result is always either a complete ordering or an ordering with just 1 of the 28 possible games having an unknown result, i.e. with two players "tied" in the sense that we don't know which one is better, it would require log2(8! + 7*7!), about 16.2 bits, to encode. Assuming any amount of ignorance is possible, including having no results at all, A000670 says there are 545835 possibilities for 8 players. That would require 19.1 bits to encode. Given that even the worst graph will return *some* results, the floor is somewhat above total ignorance. So somewhere between 16.2 and 19.1 bits in that sense.
Once you start allowing draws I believe you get into murky water since two players who draw are unlikely to actually be equal, so you start getting into probabilities and chess ranking strategies and the like. It's still interesting, but more complicated. This thread has made me think a bit more about doing some searches for regular graphs with low average path length, and I'm finding that with modern machines I can get a lot more results than I did back in the early 90's. If you do pursue this and want some likely good graphs I'd be happy to share what I have. -tom