The renowned Gossiping Problem (1971) asks the following. There are \(n\) people who each know an item of gossip. In a telephone call, two people share all the gossip they know. How many calls are needed for all of them to be informed of all the gossip? If \(n\ge 4\), the answer is \(2n-4\). We initiate and solve the related Greedy Gossiping Problem: given a fixed number \(m<2n-4\) of calls, at most how much gossip can be known altogether? Our main result is that if every call increases the total knowledge of gossip as much as possible, then this call strategy is optimal.
In 1971, Boyd asked the following question [6]. There are \(n\) people who each know an item of gossip. In a telephone call, two people share all the gossip they know. How many calls are needed for all of them to be informed of all the gossip?
Boyd’s problem, commonly referred to as the ‘Gossiping Problem’, was resolved within a year in different ways by Tijdeman [11], Baker and Shostak [1], as well as Hajnal, Milner, and Szemerédi [6]. Bollobás subsequently introduced it as a challenge problem for undergraduate students [2].
For \(n=4\), it is an easy exercise to show that \(4\) calls are sufficient, and by induction, \(2n-4\) calls are sufficient for \(n\ge 4\). The difficult part of the problem is proving that \(2n-4\) calls are necessary [1, 6, 11].
In this note, we tackle the related question of what happens when the number of calls is restricted to \(m\) calls. For the sake of our word problem, we say the dons live in different countries and international telephone calls are very costly. We name this “Greedy Gossiping’, for the dons shall aim to know as much gossip as possible in total. That is, let each don count how many items of gossip she knows, and let \(N\) be the sum total. The maximal value of \(N\), given \(m\), is the following.
Theorem 1.1. Let \(n\ge 4\) be an integer and \(0\le m\le 2n-5\). Suppose that \(n\) dons each know a unique item of gossip, and in each of \(m\) telephone calls, two of the dons communicate all the items of gossip they know and remember it. After the calls, each don counts how many items of gossip she knows. The sum of these numbers, \(N\), is the score of the call sequence.
The largest possible score is achieved by the first \(m\) of the following \(2n-3\) calls: dons \(2,3,\dots,n\) call don \(1\), and then don \(1\) calls dons \(2,3,4,\dots,n-1\).
In the range \(0\le m\le n-1\), by induction on \(m\), the score is maximised precisely by a greedy strategy, one that increases the score as much as it can with every call. For \(n\le m\le 2n-5\), however, it would seem that we must induct on \(n\), and we do so by reusing ideas from [1] and [9]. Therefore, if \(m=2n-5\), the maximum of \(N\) is \(n^2-3\), so \(2n-4\) calls are necessary in the Gossiping Problem. Since an optimal strategy may not include a 4-cycle, unlike the case of \(m=2n-4\) [9], this can be viewed as a negative stability result.
The original Gossiping Problem prompted a wide array of related questions [7]. The question most similar to Greedy Gossiping is Partial Gossiping, where after \(m\) calls, the least number of items of gossip known by a don is maximised [4].
We also mention three variants of Gossiping. In Broadcasting, information from one don is to reach all the dons, with various constraints [7]. In Perpetual Gossiping, a new piece of information occurs to each don after a given number of calls are made [10]. In Shuffling, each don has a unique object, and a “lazy” call is an option to exchange the object [8].
The Gossiping Problem has further achieved renown in computer science, with a call sequence among \(n\) dons referred to as a temporal graph. We mention a few inspiring combinatorial questions that occurred in this recent algorithmic field of research. As a subsequence of some sort of call sequence, at least how many calls are needed so that every don hears every gossip? What is the maximum of this minimum over every call sequence that forms a complete graph [3]? Like the Travelling Salesman Problem, we could also ask, how many in-person meetings are necessary to pass a mascot from one don along to every don [5]?
For the sake of proving Theorem 1.1, we define the concept of a temporal path.
Definition 2.1. Let the dons \(v_1,v_2,\dots,v_n\) make the calls \(e_1,e_2,\dots,e_m\), where call \(e_t\) takes place at time \(t\). Thus, the calls form a temporal graph. A temporal walk from don \(u\) to don \(w\) is a subsequence of calls, \(\{u_1,u_2\},\{u_2,u_3\},\dots,\{u_{h-1},u_h\}\), where \(u=u_1\) and \(u_h=w\). It is a temporal path if \(u_1,u_2,\ldots,u_h\) are distinct.
Observe that the item of gossip from don \(u\) reaches don \(w\) if and only if a temporal walk (hence, by contracting loops, a temporal path) from \(u\) to \(w\) exists.
The optimal call sequence described in Theorem 1.1 is given by
and then \(e_t:=C_t\) for \(t=1,\dots,m\). With \((C_t)_{t=1}^{2n-3}\), we claim that after \(m\) calls,
By induction on \(m\), this claim follows from how
Consequently, the score \(N\) of \((C_t)_{t=1}^m\) can be characterised as follows:
where the latter describes how for \(1\le i\le n-1\), \(v_{n-i}\) does not know \(i\) pieces of information after the first \(n-1\) calls, and the next \(n-1-l\) calls inform \(v_1,\dots,v_{n-l}\) with every gossip item.
Consider the call sequence \((e_t)_{t=1}^m\), where \(0\le m\le n-1\).
Lemma 2.2. After \(e_1,\ldots,e_{t-1}\), at most \(t+1\) gossip items are shared in call \(e_t\).
Proof. Let us consider the simple graph \(G_t\) whose vertices are dons who call by time \(t\) and whose edge set is \(\{e_1,e_2,\dots,e_t\}\). If an item of gossip is heard in call \(t\), then it reached one of the dons in \(e_t\) along a temporal path. Hence, the sources of the gossip communicated in \(e_t\) are limited to the connected components of the two dons involved. Since a connected graph with at most \(t\) edges contains at most \(t+1\) vertices, no more than \(t+1\) items of gossip can be heard in the call \(e_t\). \(\square\)
By Lemma 2.2, the call \(e_t\) increases the score by at most \(t+1\) for all \(1\le t\le m\), so
For equality to hold in this bound, \(G_t\) must be connected for \(1\le t\le m\). Given that \(G_{t-1}\) is connected, \(e_t\) is a call between a new don and a don who must know every item of gossip from the dons in previous calls, a don who is one of the dons in call \(t-1\). While such a call can be arranged in essentially two ways, either way, the score increases maximally in call \(t\) (\(t=2,\ldots, m\)). Moreover, if we arrange these \(m\) calls in such a greedy way, then up to renaming the dons, the sets of gossip items known to each don are uniquely determined.
Our next step is to prove that \(N=n^2-(1+2+\ldots +(l-1))\) is maximal when there are \(m=2n-2-l\) calls and \(3\le l\le n-1\). We have settled the case \(m=n-1\), and this will be the base of our induction on \(n\), for it is the only case when \(n=4\).
Suppose Theorem 1.1 holds for \(n\) dons with \(n-1\le m\le 2n-5\) calls. Let \(n+1\) dons make \(m=2n-l\) calls, where \(3\le l\le n\). If \(l=n\), it is the case that \(m=n\), so we are done. If \(l<n\), the induction step is made possible by the following observation [1].
Lemma 2.3. Suppose that \(v_{n+1}\) hears her own item of gossip, i.e. there are \(n+1\) dons whose call sequence includes a (nontrivial) temporal walk from \(v_{n+1}\) to \(v_{n+1}\). Under this premise, it is possible to arrange \(2\) fewer calls among \(v_1,\dots,v_n\) without communicating any less information among them.
Proof. As a preliminary, we remark that one fewer calls can always be arranged. Suppose the calls of \(v_{n+1}\) are with dons \(u_1,u_2,\dots,u_d\), in this order. Instead of these calls, for \(1\le i\le d-1\), let \(u_i\) call \(u_{i+1}\) at the time she would call \(v_{n+1}\). This way, if a temporal path with endpoints among \(v_1,\dots,v_n\) includes \(\{u_i,v_{n+1}\}\) and \(\{v_{n+1},u_j\}\), \(i<j\), then these two edges can be replaced with a temporal walk \(u_iu_{i+1}\dots u_{j-1}u_j\) to form a temporal walk not involving \(v_{n+1}\).
Now suppose there is a temporal walk from \(v_{n+1}\) to \(v_{n+1}\). Hence, between some two calls \(\{v_{n+1},u_p\}\) and \(\{v_{n+1},u_q\}\), \(p<q\), there is a (possibly trivial) temporal path \(P\) from \(u_p\) to \(u_q\). Informally, on our preliminary temporal walk \(u_1u_2\dots u_d\), rather than using \(u_pu_{p+1}\dots u_q\), we walk from \(u_p\) to \(u_q\) along \(P\). However, for \(p<i<q\), at the time \(u_i\) would call \(v_{n+1}\), she shall call the don at the endpoint of the path \(P\) up to that time. Given a temporal path with endpoints among \(v_1,\dots,v_n\) including \(\{u_i,v_{n+1}\}\) and \(\{v_{n+1},u_j\}\), \(i<j\), these two edges can be replaced with a subpath of our temporal walk from \(u_1\) to \(u_d\), possibly with a replacement call from \(u_i\) or \(u_j\) to begin or end with. In this way, we reduce the number of calls by \(2\) without changing the information communicated between two of the dons \(v_1,\dots,v_n\). \(\square\)
The upshot of Lemma 2.3 is that if there is a call sequence of \(2n-l\) calls (\(3\le l\le n-1\)) among \(n+1\) dons that scores \(N\), then there is a call sequence of \(2n-2-l\) calls among \(n\) dons that scores at least \(N-(2n+1)\). Indeed, the don \(v_{n+1}\) spreads her item of gossip to at most \(n\) other dons and knows at most \(n+1\) items of gossip in the end. Therefore, by induction,
As we are done in this case, we may suppose that no don hears her own item of gossip. The next observation, also from [1], shows the ramifications of this premise.
Lemma 2.4. Suppose that \(v_i\) does not hear her own gossip. Let \(a_i\) be the number of dons who know the gossip of \(v_i\) and let \(v_i\) know \(b_i\) many items of gossip. Further, let \(c_i\) be the number of calls that neither inform \(v_i\) nor pass on \(v_i\)’s gossip, and let \(d_i\) be the number of calls with \(v_i\). Then
Proof. Highlight all the calls where \(v_i\)’s gossip was known by only one of the dons. There are at least \(a_i-1\) such calls, of which at least \(a_i-1-d_i\) are not a call with \(v_i\), so these calls are in a temporal path from \(v_i\) of more than one call. Since there is no temporal walk from \(v_i\) back to \(v_i\), it follows that these calls cannot be in a temporal path to \(v_i\). Such temporal paths include at least \(b_i-1\) edges, because they connect \(b_i\) vertices, including \(v_i\). Altogether, we have
which rearranges to the claimed inequality. \(\square\)
The score, \(N=\sum\limits_{i=1}^n b_i\), counts the number of pairs \((i,j)\) for which \(v_i\) hears an item of gossip from \(v_j\), and so \(N=\sum\limits_{j=1}^n a_j\). Similarly, by double-counting the number of participants in the \(m\) calls, we obtain \(2m=\sum\limits_{i=1}^n d_i\). Therefore, we can sum both sides of Lemma 2.4 to find
Our aim is to show that this quantity cannot exceed \(2n^2-2(1+2+\dots+(l-1))\). However, by substituting \(m=2n-2-l\), elementary algebra shows
which is non-negative in the range \(4\le l\le n-1\). Arguably, we could now deduce Theorem 1.1 in the range \(m\le 2n-6\), but with a little more work, we can tackle the case \(l=3\), \(m=2n-5\).
Our next idea is that a swap of disjoint consecutive calls does not change who knows which gossip in the end. Such a swap is possible regardless of how many dons participate in each call [9].
Lemma 2.5. If the dons make \(m\ge n-1\) calls, there is a rearrangement of the calls that ultimately communicates the same information where either some don is not involved in the first \(n-2\) calls or \(e_{n-2+i}\) is never disjoint from each of \(e_{n-2},e_{n-1},\dots,e_{n-3+i}\) for \(1\le i\le m-(n-2)\).
Proof. The key idea, due to Hajnal, Milner, and Szemerédi [6], is that if two consecutive calls are disjoint, then by swapping them, the items of gossip known by the participants after the calls does not change. In particular, suppose that \(e_{j+i}\) is disjoint from \(e_j,e_{j+1},\dots,e_{j+i-1}\). Then, by induction on \(i\), there are \(i\) such swaps that rearrange \(e_j,e_{j+1},\dots,e_{j+i}\) to \(e_{j+i},e_j,\dots,e_{j+i-1}\).
Let us keep track of the connected components in the graph \(G\) with vertices \(v_1,\dots,v_n\) and edges given by the first \(n-2\) calls. At least two of these components are trees, because a connected graph that is not a tree has at least as many edges as vertices. If none of the trees is an isolated vertex, then by making swaps between calls in disjoint components, we can let \(e_{n-2}\) be the final call in the smallest of the trees, \(T_1\), and \(e_{n-3}\) be the final call in the second smallest tree \(T_2\).
Now if there is a positive integer \(i\) for which \(e_{n-2+i}\) is disjoint from \(e_{n-2}\), \(\ldots\), \(e_{n-3+i}\), then the calls can be rearranged so that the first \(n-1\) calls are \(\ldots\), \(e_{n-3}\), \(e_{n-2+i}\), \(e_{n-2}\). Thus, \(G\) changes, as \(T_1\) is disconnected into subtrees \(T_1’\) and \(T_1”\), and then some two connected components are joined with an edge. This decreases \(|T_1|+|T_2|\) if two of \(T_1’\), \(T_1”\), and \(T_2\) are among its components. Otherwise, \(e_{n-2+i}\) joins two of \(T_1’\), \(T_1”\), and \(T_2\), so \(|T_1|+|T_2|\) stays the same or decreases.
If \(e_{n-2+i}\) is from \(T_1’\) to \(T_1”\), then with two swaps, we can rearrange the calls \(e_{n-3},e_{n-2+i},e_{n-2}\) to \(e_{n-2+i},e_{n-2},e_{n-3}\). This way, \(G\) will include two components that are subtrees of \(T_2\), and so \(|T_1|+|T_2|\) decreases by at least \(|T_1|\). If \(e_{n-2+i}\) is from \(T_2\) to \(T_1’\), say, then \(T_1”\) will be a smaller tree component in \(G\). Therefore, \(2^{|T_1|+|T_2|}+2^{|T_1|}\) is a monovariant, and at its minimum over all possible rearrangements of the calls, either an isolated vertex occurs or no call \(e_{n-2+i}\) can be swapped with \(e_{n-2},e_{n-1},\dots,e_{n-3+i}\). \(\square\)
In the case where some don \(v_i\) has not called until \(e_{n-2}\), at most \(n-2\) dons learn her gossip, and so \(a_i\le n-2\). In the case where the last \(n-2\) calls are connected as a graph, there is an isolated vertex representing a don \(v_i\) that only learns from the first \(n-3\) calls, whence \(b_i\le n-2\).
Notice that by reversing the calls \(e_1,\dots,e_m\) to \(e_m,\dots,e_1\), all temporal paths are also reversed, and so \(a_i\) and \(b_i\) are interchanged. Hence, without loss of generality, \(a_i\le n-2\) for some \(i\).
Since \(a_i\le n\) for all \(i\), we obtain \(N=\sum\limits_{i=1}^n a_i\le n^2-2\). Our objective is to prove that \(N\le n^2-3\), which we may do by ruling out the case of equality, i.e. \(a_i=n\) for all \(i\) but one with \(a_i=n-2\). For the sake of contradiction, let us assume that is the case.
Lemma 2.6. For each don, let us consider who they called first. Suppose the call \(\{v_1,v_2\}\) came first for \(v_1\), but \(\{v_2,v_3\}\) came first for \(v_2\). Then \(a_1<n\), unless \(v_3\) hears her own item of gossip.
Proof. If \(a_1=n\), there must be a temporal path from \(v_1\) to \(v_3\). The first call in this path is \(\{v_1,v_2\}\) or a later call, and so it occurs after \(\{v_2,v_3\}\). Therefore, by appending \(\{v_2,v_3\}\) and removing or inserting \(\{v_1,v_2\}\), we obtain a temporal walk from \(v_3\) to \(v_3\). \(\square\)
If a call is the first for both callers, we say it is a mutual first call, and similarly for final calls. Notice that if \(\{v_1,v_2\}\) is a mutual first call, then afterwards, whoever knows \(v_1\)’s gossip also knows \(v_2\)’s gossip. Hence, for a unique \(i\) with \(a_i=n-2\), the first call is not mutual.
By Lemma 2.6, whenever \(a_i=n\), the first call of don \(v_i\) has to be mutual. Thus, there are \(\frac{n-1}{2}\) mutual first calls. As for mutual final calls, we would be done if there were three distinct vertices whose final call is not mutual, with \(b_i\le n-1\) thrice. Hence, for parity reasons, \(\frac{n-1}{2}\) final calls are mutual. The mutual first and mutual final calls are different, else there would be two dons disconnected from the others, a contradiction. Thus, there are \(\frac{n-1}{2}\) mutual first calls, \(\frac{n-1}{2}\) mutual final calls, and \(n-4\) miscellaneous calls.
Lemma 2.7. If the miscellaneous calls do not isolate a vertex, then \(c_i\ge 1\) for all \(i\).
Proof. The \(n-4\) miscellaneous calls determine a graph on \(v_1,\dots,v_n\) with at least \(4\) connected components. Any temporal path beginning at \(v_i\) or ending at \(v_i\) could contain miscellaneous edges from the component of \(v_i\), her first caller, or her final caller. Therefore, a miscellaneous edge in a fourth component would not be involved in communicating to \(v_i\) or from \(v_i\). \(\square\)
By Lemma 2.4, \(a_i+b_i\le m+2+d_i-c_i\), which we rewrite in the form
If it were the case that \(c_i\ge 1\) for all \(i\), then summing would yield \(2m+2(n^2-N)\ge 4n\), \(N\le n^2-5\). Otherwise, there is a don \(v_j\) whose vertex is isolated in the graph of miscellaneous calls. The only calls involving \(v_j\) are her first and final calls, and so \(d_j=2\).
Collecting the facts, we find a unique don whose first call is not mutual, say \(v_1\), so that \(a_1=n-2\), as well as a unique don, say \(v_{j’}\), whose final call is not mutual, which implies \(b_{j’}<n\). Since \(v_j\) cannot be \(v_1\), it follows that \(a_j=n\). Using Lemma 2.4, we find \(2+0+(n-b_j)\ge 3\), so \(b_j<n\). However, since the same information is known by mutual final callers, the dons in the final call of \(v_j\) and also \(v_{j’}\) are now three instances of \(b_i\le n-1\). Thus, we deduce that \(N\le n^2-3\).
This completes the proof of Theorem 1.1.
It is known that if \(n\ge 4\), then for \(m=2n-4\) calls, every optimal call sequence involves a 4-cycle [9]. We proved this to be false when \(m<2n-4\). This raises the question of characterising all the possible maximisers for \(m\ge n\).
Problem 3.1. Can there be a 4-cycle in an optimal call sequence if \(m<2n-4\)?
Our proof built on different solutions to the Gossiping Problem. In particular, the key idea for the subcase \(m=2n-5\) is the heart of a more general proof that works if calls are between \(k\) people, where \(k\ge 2\) is fixed [9]. A logical next question for Greedy Gossiping is whether the same phenomenon occurs if the calls form a temporal \(k\)-uniform hypergraph.
Conjecture 3.2. Let \(n\) dons gossip in conference calls of \(k\) people. Let \(m\) be a fixed number of calls, less than the minimal number of calls needed for all the dons to know all the gossip. Then the number of items they know is maximal when every call maximises the amount of new gossip overheard.
We find Conjecture 3.2 plausible because it holds whenever \(m(k-1)\le n-1\). We can deduce this from a straightforward generalisation of Lemma 2.2: at most \(t(k-1)+1\) gossip items occur in the \(t\)-th call. Each such gossip item is thus heard of at most \((k-1)\) times, and so
The author is especially grateful to Imre Leader for doctoral supervision and to Trinity College Cambridge for financial support (Internal Graduate Studentship). At no stage of creating this work was an LLM on a computer put to use.
The author declares no conflicts of interest.
This research received no external funding.
This study is theoretical and does not involve the generation or analysis of datasets.