Re: [math-fun] optimal advance tournament scheduling
Tomas, please remind me of just what the program is computing — thanks. —Dan ----- 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. ... ... 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 ... ... -----
For each graph topology, and each of the 8! orderings of competitor strength, it calculates how many of the (8 choose 2)=28 pairwise judgements can be derived from just the head-to-head results from a tournament represented by the input graph. This gives us a number from 0 to 28 (in this case, from 16 to 28 because there are 16 edges in each graph so we know those will be good). Then it writes a distribution. So in the example you quoted, of the 8! orderings, 1728 gave 18 bits of results, 2352 gave 19 bits of results, etc. up to 840 orderings gave all 28 bits of results (or a full ordering of all competitors). On Wed, Jun 19, 2019 at 12:22 PM Dan Asimov <dasimov@earthlink.net> wrote:
Tomas, please remind me of just what the program is computing — thanks.
—Dan
----- 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. ... ... 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 ... ... -----
_______________________________________________ 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/ --
So, I ran the same code over the five possible (8,3) combinations. Not surprisingly, many fewer decisions were made on average; from 16.81 up to 18.89. The cube graph got 18.30 on average (and it is nicely vertex and edge transitive). The best graph was the cube graph with a twist, a Mobius ladder, also known as the Wagner graph, with 18.89 on average. What happens in the (8,4) case on the K4,4 graph is easily understood. The unfolded DAG corresponds to the odd/even parities of the permutation; if adjacent elements of the permutation always have a different parity, they are on different sides of the bipartite graph, and thus adjacent elements of the permutation are distinguishable so the whole permutation is determined. From this it is easy to see what head-to-head results can be inferred. Take for instance the permutation (3,1,4,5,2,6,8,7); we interpret this to be the order of strength, with 3 strongest and 7 weakest. 3 and 1 are both odd, so both on one side of the bipartite graph, so we can't distinguish them; they both beat the four competitors they played. Then comes 4, which we can absolutely determine to be in 3rd place, because he was beat by 1 and 3 but beat everyone else. Next comes 5 in fourth place. Competitors 2, 6, and 8 are indistinguishable since they have the same results (losing to 3, 1, and 5, but beating 7) so they are all tied for fifth place. And competitor 7 is in 8th place since everyone beat him, and he's the only one that everyone beat. On Wed, Jun 19, 2019 at 12:35 PM Tomas Rokicki <rokicki@gmail.com> wrote:
For each graph topology, and each of the 8! orderings of competitor strength, it calculates how many of the (8 choose 2)=28 pairwise judgements can be derived from just the head-to-head results from a tournament represented by the input graph. This gives us a number from 0 to 28 (in this case, from 16 to 28 because there are 16 edges in each graph so we know those will be good). Then it writes a distribution. So in the example you quoted, of the 8! orderings, 1728 gave 18 bits of results, 2352 gave 19 bits of results, etc. up to 840 orderings gave all 28 bits of results (or a full ordering of all competitors).
On Wed, Jun 19, 2019 at 12:22 PM Dan Asimov <dasimov@earthlink.net> wrote:
Tomas, please remind me of just what the program is computing — thanks.
—Dan
----- 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. ... ... 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 ... ... -----
_______________________________________________ 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/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
participants (2)
-
Dan Asimov -
Tomas Rokicki