Studies in Applied Mathematics · 1973 · 11 citations · 1 references
Social SciencesCommunicationMathematicsCommunication TheoryDigital CommunicationInformation TheoryCommunication ComplexityCommunication NetworksCommunication SystemsProbabilistic CombinatoricsCommunication Complexity Upper BoundsErdős - Ginzburg - Ziv TheoremMulti-party Communication Complexity
We are given the question: how many phone calls are needed for n people to pool all their information in a succession of k ‐person party line phone calls? The question was proposed by Erdös for the special case K = 2. We prove here the result that [ n − 2/ K − 1] + [ n − 1 / k ] + 1 calls are required if 1 ≤ n ≤ k 2 , while 2[ n − 2/ k − 1] are required for n > k 2 .
1
Brenda S. Baker, Robert E. Shostak · Discrete Mathematics · 1972 · 129 citations