IBM - Personal communication

This web page contains the abstract of my paper:

"Further Gossip Problems" with D.J. Kleitman, Discrete Mathematics, 30(1980), p.151-156.

Abstract: n people have distinct bits of information. They can communicate via k-party conference calls. How many such calls are needed to inform everyone of everyone else's information? Let f(n,k) be this minimum number. Then we give a simple proof that f(n,k)=rounded up [(n-k)/(k-1)] + rounded up[n/k] for 1<=k**2, f(n,k)= 2* rounded up [(n-k)/(k-1)] for n>k**2.

In the 2-party case we consider the case in which certain of the calls may permit information flow in only one direction. We show that any 2*n-4 scheme that conveys everyone's information to all must contain a 4-cycle, each of whose calls is "two way", along with some other results. The method follows that of Bumby who first proved the 4-cycle conjecture.

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]