Greedy Gossiping

Kada K Williams · 2025

Read Greedy Gossiping by Kada K Williams (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-17804.txt.

Introduction

Kada Williams solves a greedy twist on the classic gossiping problem. In the 1971 puzzle, each of n people knows one secret. A call swaps all secrets both sides hold. It is known that full spread takes 2n minus 4 calls when n is at least four. Williams asks a leaner question: with fewer calls than that, how much total knowledge can be banked at best?

The greedy rule always picks the call that adds the most knowledge now. One might fear it wastes calls early. Her 2025 proof shows greedy is in fact optimal at every call count below the full mark. Only at one call past the classic count can the total reach its ceiling. The result is a clean close to a natural worry.

Catalog record

CREATORKada K Williams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-17804

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Greedy Gossiping Kada K Williams Abstract The renowned Gossiping Problem (1971) asks the following. There are n 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 ≥ 4 n\geq 4 , the answer is 2 ​ n − 4 2n-4 . We initiate and solve the related Greedy Gossiping Problem: given a fixed number m < 2 ​ n − 4 m<2n-4 of calls, at most how much gossip can be known altogether? If every call increases the total knowledge of gossip as much as possible, the sum reaches n 2 n^{2} only when m = 2 ​ n − 3 m=2n-3 . Our main result is that surprisingly, for each m < 2 ​ n − 4 m<2n-4 , this calling strategy is optimal. 1 Introduction In 1971, Boyd asked the following question [ 3 ] . 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? This problem, commonly referred to as the ’Gossiping Problem’, was independently resolved by Tijdeman [ 1 ] , Baker and Shostak [ 2 ] , as well as Hajnal, Milner, and Szemerédi [ 3 ] . Possibly due to the simplicity of and variety of approaches to the Gossiping Problem, Bollobás additionally introduced it as a challenging ’starred question’ for undergraduate students [ 8 ] . In this note, we tackle the related question of what happens when the number of calls is restricted to m calls. The dons call greedily in the sense that if each don counted how much gossip she knows, the sum total N would be largest possible. We characterise the optimal value of N as follows. Theorem 1 . Let 0\leq m\leq 2n-5 . In Gossiping, suppose that after m calls, the number of news known is N altogether. The maximal value of N is achieved by the first m of the following 2n-3 calls: dons 2,3,\dots,n call don 1 , then don 1 calls dons 2,3,4,\dots,n-1 . In our proof, the range 0\leq m\leq n-1 is easy to resolve, n\leq m\leq 2n-6 requires ideas from [ 2 ] , and m=2n-5 is more difficult. For an example of m=2n-4 calls after which N=n^{2} ( n\geq 4 ), we refer the reader to [ 1 ] , [ 2 ] , [ 3 ] . Incidentally, a plethora of research is available involving ideas related to the original ’gossiping dons’ problem. This includes questions about broadcasting [ 5 ] , perpetual gossip [ 7 ] , shuffles [ 9 ] , and counting algorithms [ 10 ] . These variations apply respectively to situations where only one piece of news is to be disseminated across an entire network, where the dons continually update one another, where information is replaced with an amount of a resource, or where information overload is to be prevented. 2 Proof of Theorem 1 2.1 Distinction between 0\leq m\leq n-1 and n-1\leq m\leq 2n-5 Suppose dons v_{1},v_{2},\dots,v_{n} make the calls e_{1},e_{2},\dots,e_{m} in this order. The vertex set \{v_{1},\dots,v_{n}\} defines a temporal graph on this multiset of edges, where we say that e_{t} occurs at time t [ 9 ] . Notice that don v_{1} hears the gossip of v_{2} if and only if there is a path of edges at increasing times, a temporal path , from v_{2} to v_{1} . Let us consider the call sequence \epsilon_{t}=\{v_{1},v_{t+1}\} for 1\leq t\leq n-1 and then \epsilon_{n-1+t}=\{v_{1},v_{t+1}\} for 1\leq t\leq n-1 . In the first n-1 calls, \epsilon_{t} lets v_{t+1} learn the news from v_{1},\dots,v_{t} and v_{1} learn the news from v_{t+1} , 1\leq t\leq n-1 . In the last n-1 calls, v_{1} knows everything, and \epsilon_{n-1+t} lets v_{t+1} learn the news from v_{t+2},\dots,v_{n} . This much is clear by inducting on t . We are claiming that e_{t}=\epsilon_{t} ( 1\leq t\leq m ) is optimal, with total gossip knowledge N=\begin{cases}n+(2+3+\dots+(m+1))\quad\text{if}\quad 1\leq m\leq n-1\\ n^{2}-(1+2+\dots+(m^{\prime}-1))\quad\text{if}\quad m=2n-2-m^{\prime},1\leq m^{\prime}\leq n-1\end{cases} since if m\geq n-1 , after e_{1},e_{2},\dots,e_{n-1} , v_{t+1} would be yet to learn n-t-1 new gossips ( 1\leq t\leq n-1 ) before N=n^{2} . 2.2 The case 0\leq m\leq n-1 Lemma 2 . At most t+1 pieces of news are communicated in call e_{t} ( 1\leq t<n ). Proof. Consider the simple graph on the set of edges \{e_{1},e_{2},\dots,e_{t}\} . The news that could be spoken of in call e_{t} can only be from a vertex in the connected component of e_{t} , which contains at most t+1 vertices, if connected. ∎ Summing over t=1,\dots,m yields the claimed result when 0\leq m\leq n-1 . 2.3 No don hears her own gossip Lemma 3 . Suppose there are n+1 dons whose calls include a subsequence of times t_{0}<t_{1}<\dots<t_{j} when v_{n+1} calls v_{i_{1}} , who calls v_{i_{2}} , and so on, until v_{i_{j}} calls v_{n+1} . Then it is possible to arrange 2 fewer calls among the n dons, excepting v_{n+1} , such that v_{1},\dots,v_{n} communicate at least as much. [ 2 ] Proof. It is always possible to arrange 1 fewer calls: if v_{n+1} calls u_{1},u_{2},\dots,u_{s} in this order, then instead, let u_{r} call u_{r+1} ( 1\leq r<s ) at the time she would call v_{n+1} . This way, transmission via v_{n+1} is replaced by transmission along the temporal path u_{1}u_{2}\dots u_{s} . However, if between the calls of v_{n+1} with u_{p} and u_{q} ( p<q ), there is a temporal path from u_{p} to u_{q} , then the calls of u_{p},\dots,u_{q-1} can be replaced as follows. Whenever p<r<q , let u_{r} call the don currently at the end of the path when she would call v_{n+1} . Therefore, if v_{n+1} hears her own information, the other n dons can communicate to the same effect, while sparing a call for u_{s} and u_{p} . ∎ Thus, we deduce that if there are 2n-m^{\prime} calls among n+1 dons with N>(n+1)^{2}-(1+2+\dots+(m^{\prime}-1)) , and someone hears back her news, then there are 2n-2-m^{\prime} calls among n dons with N>n^{2}-(1+2+\dots+(m^{\prime}-1)) , because that don and her news contributes to N by at most (n+1)+n=(n+1)^{2}-n^{2} . It is known that m^{\prime}=n cannot occur, and if m^{\prime}<n , then we can pass to a smaller counterexample n . Therefore, in a counterexample with minimal n , there is no don who hears her own gossip. 2.4 The case n\leq m\leq 2n-5 Lemma 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} gossips. Further, let c_{i} be the number of calls that neither inform v_{i} nor pass on the gossip of v_{i} , and let d_{i} be the number of calls with v_{i} . Then a_{i}+b_{i}\leq m+2+d_{i}-c_{i}. Proof. Highlight all the calls where v_{i} ’s gossip is news. There are at least a_{i}-1 such calls, of which at least a_{i}-1-d_{i} are not a direct call with v_{i} . Since v_{i} never hears her own gossip,

Read the complete text