Mixed Telephone Problems

Abstract

We consider a generalization of the well-known gossip problem: Let the information of each point of a set $X$ be conveyed to each point of a set $Y$ by $k$-party conference calls. These calls are organized step-wisely, such that each point takes part in at most one call per step. During a call all the $k$ participants exchange all the information they already know. We investigate the mutual dependence of the number $L$ of calls and the number $T$ of steps of such an information exchange. At first a general lower bound for $L.k^T$ is proved. For the case that $X$ and $Y$ equal the set of all participants, we give lower bounds for $L$ or $T$, if $T$ resp. $L$ is as small as possible. Using these results the existence of information exchanges with minimum $L$ and $T$ is investigated. For $k=2$ we prove that for even $n$, there is one of this kind if $n\le 8$.