No label defined (Q3972008)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 15364
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 15364

      Statements

      0 references
      0 references
      25 June 1992
      0 references
      generalized Fibonacci numbers
      0 references
      gossip
      0 references
      telephone problem
      0 references
      \(k\)-conference calls problem
      0 references
      \(k\)-telegraph problem
      0 references
      [For the entire collection see Zbl 0698.00017.] In the gossip problem there are \(n\) persons, each knowing a piece of information ( gossip) unknown to others. At each discrete unit of time information is exchanged between pairs of persons when all the information known to one is passed on to the other. If information exchange takes place in both ways (modelled by an undirected graph) we have the telephone problem. If exchange can take place only in one way in unit time (modelled by a directed graph) we have a telegraph problem. If, in unit time, a person can communicate with \(k\) others we have a \(k\)- conference calls problem or a \(k\)-telegraph problem, respectively. One of the objectives is to find the minimum number \(T_ k(n)\) of rounds (time) necessary for a complete exchange of information. The authors settle a conjecture of Entringer and Slater for the \(k\)-telegraph problem: \[ T_ k(n)=\alpha_ k\log_{k+1}(n)+O(1)\text{ with } \alpha_ k\to 1\text{ as } k\to\infty. \] They actually prove that, for \(k\geq 2\), \(T_ k(n)\in\{\lceil\log_{\tau_ k}n\rceil,\lceil\log_{\tau_ k}n\rceil+1\}\) where \(\tau_ k={1\over 2}[k+(k^ 2+4)^{1/2}]\) is the positive root of \(x^ 2-kx-1=0\). The proof technique involves the generation of a message sequence involving the recurrent sequence \(\{F_ k(t)\}\) defined by \(F_ k(0)=0\), \(F_ k(1)=1\) and \(F_ k(t+1)=kF_ k(t)+F_ k(t+1)\) for \(t\geq 1\). This is an obvious generalization of the Fibonacci sequence. At least two sets of people seem to be working on these problems in non- communicating compartments. For example the list of references in the paper under review and the one by \textit{Akos Seress} [Combinatorial mathematics, Proc. 3rd Int. Conf., New York/NY (USA) 1985, Ann. N.Y. Acad. Sci. 555, 375-382 (1989; Zbl 0722.05059)] have empty intersection.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references