The six graphs I listed make up the complete set of all regular order 8 degree 4 graphs. To enumerate graphs try genreg or nauty. -tom On Sun, Jun 30, 2019 at 2:20 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Tomas Rokicki <rokicki@gmail.com> wrote:
Graph six is K4,4, the same as the graph we have been discussing (both the cube with long diagonals and the octagon with horizontal and 45 degree chords). Both vertex and edge transitive.
Average bits 24 16:1152 19:2304 20:1152 22:4608 23:4608 24:8064 25:3456 26:10368 27:3456 28:1152
I get the same numbers. Note that the number of instances are all divisible by 2 * 4!^2 = 1152, the size of the who-plays-whom-preserving symmetry group of players in K4,4. There are 4! permutations of the players on one side of K4,4, all of whom play everyone except each other, another 4! permutations of the players on the other side of K4,4, all of whom also play everyone except each other, and the final factor of 2 comes from the fact that the two sets of players can be swapped. So it's reduced to 16:1 19:2 20:1 22:4 23:4 24:7 25:3 26:9 27:3 28:1, for a total of 35 rather than 40320 cases. (However, I still find it unexpected that the average is an integer.)
8! / (2 * 4!^2) = 35 is the number of different adjacency matrices. I'll show them all if anyone is interested.
The players are numbered in order of playing ability, i.e. a lower-numbered player always beats a higher-numbered player. The vertices are then, in each of the 40320 permutations, given the same numbers as the players they represent.
The directed matrix, in which A,B is non-zero only if player A played *and beat* player B, is always simply the upper diagonal half of the who-played-whom matrix. I add the identity matrix to it so that instead of having to add all the powers of the directed matrix together to get the score, I just have to look at the highest power. (How high is highest? I stop after the matrix stops changing. For all of K4,4, the square is high enough. The cube always equals the square.)
The matrix which does worst is:
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
The directed matrix then is:
1 0 0 0 1 1 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
Each of the four best players plays each of the four worst players, so there are no instances of transitivity, i.e. a player being beaten by one player and beating another, hence the score is a miserable 16. Not coincidentally, the square of the directed matrix is the same as the directed matrix. As is its cube, ad infinitum. The number of 1 bits (not counting the diagonal) is 16, hence that's the score.
The matrix which does best is:
0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0
(All black squares on the checkerboard.) Its directed version is:
1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1
The odd-numbered players played the even-numbered players. The square of that matrix is:
1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1
The score is 28, the best possible.
Of course the players can't be deliberately assigned to their respective vertices like this unless their ranking is already known, so we have to take the average over all 35 matrices.
The first matrix I found, the Thue-Morse one, scores 26.
So it looks like the pretty symmetric graph we have been discussing is the winner; it averages 24 of the 28 "decisions" and also gives the complete ordering the greatest number of times.
Very likely, but that's presumably only out of the six graphs you tested. It's possible that there's a better graph out there somewhere. I'm still trying to figure out an efficient way to test them all. At least the fact that I'm doing most of the calculations on upper-triangular matrices rather than square matrices speeds things up.
This took me far longer than I thought it would. I guess that means I really needed the mental exercise. A large part of the problem was that I was convinced that if the matrix is on a checkerboard, the number of black squares with 1 bits is unchanged under a row permutation followed by an identical column permutation, given that any color swaps that the row permutation caused would be undone by the column permutation. That is completely wrong. Can anyone see why?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --