

A318154


Number of nonisomorphic directed graphs reachable by n agents using the ANY protocol.


1




OFFSET

1,2


COMMENTS

Suppose that each of n agents initially knows a single secret. Each agent is allowed to call each of the others and each time they call they share all the secrets they know at the time. The agents can only learn new secrets; they can never forget one. Imagine the following discrete random process: We randomly select two agents a and b and let them call each other (i.e., we let a learn b's secrets and vice versa). The random process stops when all the agents know all the available secrets.
Clearly there are several ways to achieve the situation where every agent knows all the available secrets. During each of these ways several secret distributions are produced. Initially everybody knows only their own secret, after the first call there are two agents who know each other's secret (and of course everybody still knows their own secret), etc.
We can nicely represent the above procedure using secrets graphs. A secrets graph is a directed graph where the nodes are the agents and there is an edge between a and b iff a knows the secret of b. Initially the graph contains only self loops; during the procedure edges are added and finally the secrets graph is complete (i.e., when all the agents know all the available secrets).
The random process described above is known as the ANY protocol in the literature (see e.g. the paper Dynamic Gossip in the links section) and the secrets graphs reachable by ANY are also called ordered tuples (see the paper Reachability and Expectation in Gossiping in the links section).
For up to 4 agents it is relatively easy to verify that our sequence is correct. For 5, 6 and 7 agents we developed a program for generating the reachable graphs modulo isomorphism. Details and definitions for our program can be found in the paper "Reachability and Expectation in Gossiping" in the links section.
A similar problem was studied by Douglas West (see links). The problem studied by West is similar to ours with the exception that calls are selected under very strict criteria. This allowed West to obtain a closed formula for the number of reachable nonisomorphic graphs with the fewest calls possible. In our case, since such a restriction is absent, we are unable to find a closed formula. So, we believe that developing a program which generates the reachable nonisomorphic graphs is the best we can do.


LINKS

Table of n, a(n) for n=1..7.
Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, Dynamic Gossip, arXiv:1511.00867 [cs.DM], 20152018.
Hans van Ditmarsch, Jan van Eijck, Pere Pardo, Rahim Ramezanian, François Schwarzentruber, Dynamic gossip Bulletin of the Iranian Mathematical Society (2018): 128.
Hans van Ditmarsch, Ioannis Kokkinis, Anders Stockmarr, Reachability and Expectation in Gossiping, PRIMA 2017: 93109.
Hans van Ditmarsch, Malvin Gattinger, Ioannis Kokkinis, Louwe B. Kuijer, Reachability of Five Gossip Protocols, Reachability Problems, 13th Int'l Conf. (Brussels, Belgium, RP 2019), Lecture Notes in Computer Science (LNCS Vol. 11674), Springer, Cham, 218232.
Ioannis Kokkinis, Implementation for Reachability and Expectation in Gossiping
Ioannis Kokkinis The ANYReachable Tuples for up to 4 Agents
D. B. West, A class of solutions to the gossip problem, part I, Discrete Math. 39(3), 307326.


EXAMPLE

For n=1 only the 1node graph with a self loop is reachable.
For n=2 it is clear that we can reach only 2 graphs: the initial with only self loops and the final complete directed graph with 2 vertices.
An example for the graphs generated for up to 4 agents can be found in the links section.


PROG

In order to generate the above sequence install the program given by the github repository in the links section.


CROSSREFS

Sequence in context: A281964 A297009 A135249 * A110365 A047892 A275911
Adjacent sequences: A318151 A318152 A318153 * A318155 A318156 A318157


KEYWORD

nonn,more


AUTHOR

Ioannis Kokkinis, Aug 19 2018


STATUS

approved



