I, the lurker, sent only to Keith as I thought my suggestion too trivial to bother the list with. Keith, good catch on the ambiguity of “minimum score”. I agree, the former seems more meaningful. I think each player plays 4 others, not 3, so the graph is 4-valent, not trivalent. In Dan’s graph (cube with edges and great diagonals), with black and white labeling, my case says black wins all 16 games, so odds would be 1 in 2^16. Equally “bad” is white winning all 16 games. So odds of a “bad” outcome are 1 in 2^15. Such an outcome (no ranking among 4 blacks, and none among 4 whites) is “bad” because it is unknown who the first, second, and third place trophies go to. A006820 says there are 6 8-node, 4-valent graphs. One is Dan’s. Another is a cube with its 12 edges and the two face diagonals on each of two opposite faces. Another is 12 edges and one face diagonal on 4 faces avoiding two opposite faces. Dan’s is nice in that it contains no 3-cycles. I agree, there might be some graphs that suck. That is, the graph is all in one piece, but no outcome of the games allows a complete ranking of all the players. In Dan’s case of 8 players and 16 games, it is merely my intuition that there are no such graphs. (I also assume no redundant games, in which the players are the same.) In the real world, there could be a further scheduling criteria about “exhaustion”, if an otherwise worse player can beat a better player if the better player has played more games. Even further, the games each has played perhaps should be weighted by the (estimated) strength of the opponent. — Mike
On Jun 16, 2019, at 11:54 PM, Keith F. Lynch <kfl@KeithLynch.net> wrote:
A lurker wrote:
Excellent approach to Dan=E2=80=99s question.
Thanks. I have no idea why you didn't CC the list. I'm returning this thread to the list but hiding your name since you apparently don't want your post to be seen on the list. And, as always, and unlike most people on the list, I'm quoting as little as necessary to establish context.
One suggestion =E2=80=94 = besides computing the average score, it might be interesting to also = note the minimum score.
I might as well, since it's almost no extra effort. I'm not sure whether you mean the worst case for a given graph, given all possible vertex labelings, or the worst graph averaged over all vertex labelings for that graph. I'm assuming the former.
I could call yours (best worst-case over orderings) the Rawlsian metric, and mine (best average over orderings) the Randian metric.
For instance, in Dan=E2=80=99s cube with great = diagonals, color alternate corners along edges black and white. All = games are then between a black and a white. If, say, whites always lose = to blacks, the only ranking is that the 4 blacks are better than the 4 = whites, with no ordering in either group.
True, but I'm not sure that's a bad thing. The player at 000 plays the players at 001, 010, 100, and 111, all of which are indeed of opposite parity (color) to 000, but so what?
That sounds like an unhelpful = result, even if very unlikely.
Odds of that are 1/35, if I haven't screwed up. But even if it happens, is it really that bad? There are 3 independent paths of length 2 to each of the other three, same-parity, players. To get from 000 to 011 for instance, you can go through 001, 010, or 111. If each edge is equally and independently likely to point in either direction, then chances that at least one of the three paths works is 7/8. Looked at another way, of the players at 000, 011, and a specified one of the three points that link them, chances are 1/3 that that specified point is between them in playing ability, determining 000 and 011's playing ability order. Since there are three such points, the chance of failure is (2/3)^3, 8/27, about 0.3. By symmetry, the same argument applies to every other two non-adjacent vertices. Very likely, Dan's arrangement is optimal. It's certainly very compact and symmetrical.
I now suspect that by "sessions," Dan meant that all eight players always play simultaneously, pairwise on four boards. Thus the whole tournament only takes as long as four consecutive games, even though sixteen games are played. This would also force each player to play exactly three other players, i.e. the graph is trivalent, rather than some players playing more games than others. According to A002851, there are only two (!) unlabeled order-eight trivalent graphs. That would certainly speed up my program. Trying all 40320 labelings on both of them would be effectively instantaneous, even with raising an 8 by 8 matrix to the 7th power for each ot them. If only I could be sure that one or both of them would be optimal, rather than a graph representing some players playing more games than other. It seems likely, but I can't be certain.
Dan found one of the two unlabeled order-eight trivalent graphs. What's the other one?
I think that if the graph is =E2=80=9Cin one piece=E2=80=9D, the maximum = score will always be a complete ordering of the players, thus 28, so = it=E2=80=99s not worth keeping track of the max.
I wasn't planning on keeping track, but I'm not convinced that every connected graph has a maximum score of 28. Very likely some connected graphs just suck. If it's always possible to find a path of length 7 that doesn't loop, then you could get 28 by ordering the players in order of ability along that path. But I'm not convinced that there's always such a path. (Here I'm not just counting trivalent graphs.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun