Gossip distance distribution with n gossipers.

Start with the situation of n gossipers that each have a different item of information. On each telephone call all information known to both parties is exchanged. The table below lists the total number of possible knowledge distributions (depending on the chosen sequence of calls) and the number of such distributions that can be reached with a given number of calls (but not with fewer calls).

n # d0 d1 d2 d3 d4 d5 d6 d7 0 1 2 3 4 5 6 7 8 9 1 1 2 11 189 9152 1092473 293656554 166244338221 188620758836916 1 1 1 1 1 1 1 1 1 1 1 3 6 10 15 21 28 36 6 27 75 165 315 546 882 1 76 430 1475 3920 8876 17976 79 1725 10605 41405 125475 322119 4180 59145 369180 1556660 5168520 2731 229816 2686411 16771566 74298756 477990 14916566 152871488 946796256 295321 56809557 1133866839 10505720001 16520 115163279 6418872796 98819769832 1420 86889419 24974052664 758218193454 15789900 55125490756 4483999465212 981540 55648019764 18656374653114 5040 20243146392 47738387914410 2455893090 64985976999745 73604160 40481993669796 57120 10391782344006 986710556160 26910450000 52496640

Gossip distance distribution with n gossipers, up to equivalence.

As above, but consider knowledge distributions equivalent when they only differ by a relabeling of the gossipers.

n # d0 d1 d2 d3 d4 d5 d6 d7 0 1 2 3 4 5 6 7 8 9 1 1 2 4 16 111 1940 68300 4651805 573472861 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 1 5 6 7 7 7 7 7 19 24 25 26 26 46 103 119 124 125 36 395 656 734 751 850 3437 4865 5220 518 13155 32225 40288 34 26959 179804 319699 5 19958 702813 2331047 3716 1550358 13709859 263 1546271 57152917 1 561917 145899848 70430 197131807 2223 122169250 4 31565063 3059452 87285 213

For n ≥ 4 the most efficient way to exchange all information requires 2n−4 steps. For n=0,1,2,3 the number of steps needed is 0,0,1,3, respectively. (This was proved by Tijdeman (1971), Baker & Shostak (1972), Hajnal, Milner & Szemerédi (1972), and Bumby & Spencer.)

A series of telephone calls where in each step one of the two participants learns something new can last at most (n choose 2) steps. (Jan Draisma has a beautiful proof.)

For example, for n=5, a worst case conversation is: A-B A-C A-B A-D A-B A-C A-E A-B A-C A-D.

Up to equivalence, the unique knowledge distribution for n=7 that requires 13 steps is for the seven gossipers A,B,C,D,E,F,G to know ABCEF, ABCDEF, ACDEFG, ABCDEG, ABCDEFG, ABCDEFG, ABCDEFG.

Reach this after a conversation of length 13: A-C A-B C-E C-D B-D C-G D-G E-F A-E B-E C-F E-F E-G.
After a conversation of length 14: A-C A-E A-B C-E C-D B-D C-G D-G E-F A-E B-E C-F E-F E-G.

The part with n < 9 of the above tables was computed in Berndsen (2012).

## Reference

Jochem Berndsen, Three problems in combinatorics, Master's thesis, Eindhoven Univ. of Technology, 2012. PDF