Tomas Rokicki <rokicki@gmail.com> wrote:

Nauty comes with a pretty good description of the algorithm it uses to solve the graph isomorphism problem and enumerate the graphs.

Thanks. Can you be more specific? Is it in this 103-page manual: http://users.cecs.anu.edu.au/~bdm/nauty/nug26.pdf and if so, at what page number?

The cube with long diagonals is just K4,4 (a bipartite graph with four nodes on each side and degree four).

I'm not sure what you're saying about permutating that matrix; I can permute it (rows and columns identically) into

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0

I screwed up. I apologize. I'm not a visual thinker. And I was perhaps misled by the fact that all vertices in that graph are isomorphic to each other (if that's the right term). I hadn't fully realized that there's only one bipartite graph with 8 vertices and 16 edges. 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? Indeed, before laying them out on an actual checkerboard, I thought that was the pattern I'd get. But wait, I had convinced myself that the number of 1-bits on black squares was unchanged with graph automorphisms, since moving a bit by N rows and also by N columns keeps it on the same color. (And indeed it was unchanged in your matrix.) So now I'm even more confused. The all-black matrix represents each even-numbered player playing all odd-numbered players and no even-numbered players, and vice versa. And isn't that just K4,4 again? (The (Thue-Morse) labeling I used was based on treating the coordinates of the vertices on the cube as binary numbers, so 0,0,0 became player 0, 0,0,1 became player 1, 0,1,0 became player 2, etc.) Mike Beeler <mikebeeler2@gmail.com> wrote:

I think what you call ?average bits? is what Keith calls ?score?, the number of player pairs whose ordering is found by the tournament results.

Here I think I'm on slightly firmer footing. Right. The "number of bits of information" is somewhat ambiguous, as with asking how many bits are in the first thousand decimal digits of pi. Or asking how many bits are in Borges's Library of Babel, which contains all possible books. If all 8 players play each other, and any result is possible, including ones that violate consistency and transitivity, that conveys 28 bits. With consistency and transitivity, most patterns of 28 bits are impossible. A complete ordering conveys log2(8!) bits, about 15.3 bits. Either way, with just 16 games we can't get more than 16 bits. Since 16 > 15.3 it sounds like it might be possible to get a complete ordering. But apparently not, at least not without deciding on who plays whom before knowing the results of any games. However, if, even before I thought about the problem at all, someone had suggested that 15 games would be enough, I'd know they were wrong, since 15 < 15.3. Saying the result of a tournament conveys 15.3 bits implicitly assumes that the result of a tournament is always a complete ordering. If, as 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. Confusingly, "partial ordering" doesn't seem to mean what I thought it meant. A000670 differs from A001035.