Okay, I wrote and ran the code for the 8/4 case over the six graphs and this is what I got. I'm a bit surprised we get so much information . . . the graphs are in the order I gave the graph list before. TL;DR: the pretty graph we've been talking about is, indeed, the best one. All these graphs have identical average shortest path lengths. Graph one is randomish; not vertex or edge transitive. Average bits 22.6464 18:1728 19:2352 20:3504 21:7200 22:4152 23:6528 24:5712 25:3576 26:3120 27:1608 28:840 Graph two is two copies of K4 with each node in one connected to one node in the other. Vertex transitive; not edge transitive. Average bits 22.3786 18:1296 19:4128 20:5616 21:3504 22:8256 23:4896 24:3888 25:3120 26:3360 27:1440 28:816 Graph three is the edges of a square antiprism. Average bits 22.4476 18:432 19:2800 20:5424 21:7936 22:5920 23:4928 24:4272 25:3888 26:2592 27:1312 28:816 Graph four is randomish; not vertex or edge transitive (I think). Average bits 22.8815 17:256 18:696 19:2884 20:3640 21:4348 22:6336 23:5732 24:5296 25:4700 26:3560 27:2008 28:864 Graph five is randomish; not vertex or edge transitive (I think). Average bits 23.3071 17:720 18:1568 19:592 20:2656 21:4224 22:3888 23:6496 24:5760 25:6464 26:4208 27:2816 28:928 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 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. Also, since it is edge and vertex transitive, it provides the same amount of information about each competitor. On Wed, Jun 19, 2019 at 11:16 AM Dan Asimov <dasimov@earthlink.net> wrote:
If for example A beats B and B beats C, then we can at least guess that A can beat C.
So, even if A doesn't play C in this case, there seems to be at least some information about A vs. C.
—Dan
Michael Collins wrote: ----- Some quick observations: given two players who are adjacent in the ordering, we cannot tell who is stronger if they do not actually play one another; this means that a tournament schedule without a Hamiltonian path can never give enough information to reconstruct the entire ordering. It also means that an incomplete tournament schedule can never guarantee reconstruction of the full ordering.
... -----
_______________________________________________ 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/ --