Spread of information within a wide variety of systems can be represented as evolving processes on digraphs. Starting from a random subset of initially active vertices, the measures we introduce assess the probability, speed, or number of steps it takes to spread information to the entire digraph, thus achieving digraph synchrony. Some of these measures may be viewed as generalizations of digraph connectivity or as generalizations of the diameter of a digraph to higher-order diameters. The paper places considerable emphasis on the regular case of Cayley digraphs associated to finite groups. It is demonstrated that, with appropriate assumptions on the growth of the generating sets, all the higher-order diameters of random Cayley digraphs are almost surely at most 2, as the digraph order goes to infinity. Certain results on the velocity of spread of information in digraphs are also presented.
The directed graphs (digraphs) we work with in this paper do not have loops or multiple edges; see [4] for basic definitions. A graph is a digraph with the property that if \((i,j)\) is an edge then \((j,i)\) is also an edge. Digraphs and graphs have been widely adopted as models of networks in which individual entities, such as animals in a population, neurons in a brain, or generators in a power grid, interact with a subset of the other network elements via specific communication pathways; see [17,20,14]. In some studies of such networks, nodes are endowed with states, which can change in time based on the states of their neighbors. The set of states and the dynamical system describing the state update process can take many forms, customized to the application of interest; [8,9]. Many such applications involve the spread either of some condition, such as a disease, or some abstract entity, such as information or opinions. Depending on the application and the associated communication pathways, edges may be undirected, exemplified by the interpersonal contacts leading to disease transmission, or directed, such as with viewing of social media postings.
In many settings, communication pathways may be imperfect, probabilistic, or weak, such that transmission requires multiple sources. Bootstrap percolation represents one framework that arises in this context, in which nodes switch from inactive to active if and only if at least \(k\) of their neighbors are active for some threshold \(k>0\). Significant progress has been made in understanding bootstrap percolation on various graph classes in the limit as the graph order \(n \to \infty\); see [3,10,11]. These asymptotic results emphasize phase transitions; for example, as the connection probability in an Erdős-Rényi random graph increases from 0, the probability that all nodes in the network will activate from an initially active seed under bootstrap percolation transitions abruptly from 0 to 1, in a mathematically precise sense.
The diameter of a digraph is a well-studied feature that is of mathematical interest and of importance for applications in which a digraph models a network; directed edges represent unidirectional communication pathways within the network, and the diameter relates to how efficiently information can spread through the network. The diameter has not typically been considered in the context of bootstrap percolation, however, because thresholds are usually taken as \(k>1\). In this work we introduce generalizations, which we call higher-order diameters, along with velocity of spread and probability of spread, motivated by bootstrap percolation on digraphs with \(k>1\). We will derive various results related to higher-order diameters that are motivated by issues encountered in neuroscience; see [12]. Specifically, in many brain regions, activity is initiated locally in a neuron or a neuron pool, and its impact on behavior or perception depends on the speed with which this local event can spread by inducing activity in other neurons and the extent of the spread; see [2,13,19,23]. Much of neuronal communication occurs through directed pathways involving chemical signaling events at junctions called synapses, with each neuron typically sending signals to tens, hundreds or thousands of target neurons. Therefore, to avoid run-away activity, which could lead to problems ranging from faulty stimulus detection to seizure states of excessive brain activation, neurons typically require multiple inputs within a small time window in order to activate. These features lead to the question of how well the local activation of a small subset of neurons can induce a spread of activity throughout a neuronal population in which communication occurs over directed links, each with a source and target vertex, and only succeeds when a vertex is the target of multiple, already-active sources. Although we will shortly provide more details about what we may mean by “how well” in this setting, for now we note that in many cases it may be advantageous for activation to spread quickly; for example, neurons typically will only transiently maintain states of elevated activation, and effective signaling may require activation of a population before the first-active neurons drop out of the activated state [8,9,12,13,23].
These questions about spread of activity in a neural population are naturally framed in the context of digraph theory if we consider a digraph \({G}=(V,E)\) with \(|V|=n\), where each vertex in \(V\) represents a neuron, each vertex \(j\) has a state \(\sigma_j\in \{0 ,1\}\), \(E\) consists of a set of directed edges \((i,j)\) each from a source vertex \(i\) to a target vertex \(j\), and a state \(\sigma_j\) transitions from 0 to 1 if and only if, for \(I_j=\{i\in \{1,\ldots ,n\}:(i,j)\in E\;\mbox{\rm and}\;\sigma_ i=1\}\), \(|I_j|\geq t\) for some fixed threshold \(t\). We refer to neurons or vertices with \(\sigma_j=0\) or 1 as inactive or active, respectively, and we call the natural number \(t\) the activation threshold. On this digraph, we can start what is known as a bootstrap percolation process by defining a discrete time variable \(k\in\mathbb{Z}^{+}\), setting \(\sigma_i(0)=1\) for all \(i\in S\subset V\) with \(|S|=s\), setting \(\sigma_i(0)=0\) for all \(i\in V\setminus S\), and using the above transition rule to generate a trajectory \(\{\vec{\sigma }(k)=(\sigma_1(k),\ldots ,\sigma_n(k)): k\in \{0,1,2,\ldots \}\}\). Whether \(\sigma_j(k)\to 1\) as \(k\to\infty\) for all \(j\), and how large \(k\) must be before \(\vec{\sigma}(k) = \mathbbm{1}\) depends on parameters \(s\) and \(t\) of the above process.
Intuitively, for fixed \(s\) and \(t\), there may be multiple, qualitatively different, scenarios by which activity can spread quickly through a brain region from a small subset \(S\) of initially active neurons. Here we focus on the case in which the network \({G}\) features local components, which can be activated quickly, and global links between the local components, which serve the purpose of efficiently integrating the local components in such a way that the entire region becomes active as quickly as possible (or at a controlled or prescribed pace). It is thus of interest to determine those neuronal configurations, viewed as abstract networks, that are best suited to form local components with effective global links between them. Our initial focus here is on the local components, and we start by making some simplifying assumptions. The basic working hypothesis is that a neuron is activated by receiving input from at least \(t\) already active neurons connected to it.
Initially we make the assumption that the underlying digraph \({G}\) that connects the neurons is regular; see [4,15]. We can formulate the spreading of neuronal activity, in terms of a sequence of steps, which we now describe in detail.
\(Step\) 0: Start with a set \(S=S_0\) of active vertices of the digraph \(G\) and an activation threshold \(t.\) Imagine that you hold the active vertices in your left hand, and the other vertices of \(G\) in your right hand. Color any edge emanating from \(S\) red.
\(Step\) 1: Activate vertex \(v\), held in your right hand, if \(v\) has \(t\) or more red arrows pointing to it. Move all activated vertices to your left hand. Call the set of vertices you now hold in your left hand \(S_1.\) Color all edges emanating from \(S_1\) red.
The general step is as follows. We are in posession of \(S_{i-1}\) with all edges emanating from it colored red.
\(Step\) \(i:\) Activate vertex \(v,\) held in your right hand, if it has \(t\) or more red arrows pointing to it. Move all activated vertices to your left hand. Call the set of vertices you now hold in your left hand \(S_i.\) Color all edges emanating from \(S_i\) red.
Evidently \(S=S_0\subseteq S_1\subseteq\cdots\subseteq S_i\subseteq \cdots .\) As we keep increasing \(i\), the following will (obviously) always occur: the set of vertices in your right hand becomes stationary; that is, \(\exists m\) such that the set of vertices in your right hand remains the same for all Steps \(i,\) with \(i\geq m\) . If your right hand becomes empty for some \(i\), then we say that the digraph is in synchrony. (You are now holding the whole digraph in your left hand; hence, all vertices of the digraph became active.) If the digraph is in a stationary state and your right hand is not empty we say that the digraph cannot be brought to synchrony when starting from subset \(S.\)
We say that vertex \(x\) of digraph \(G\) is activated from subset \(S\) if, starting from the vertices of \(S\) as the active vertices, \(x\) is activated after a finite number of steps. For a given starting subset \(S\) with \(s\) vertices we denote by \(d(S,t)\) the smallest number of steps that brings the digraph to synchrony. When a digraph cannot be brought to synchrony from a set \(S\), for activation threshold \(t\), we write \(d(S,t)=\infty\). A maxmin argument of this quantity is very natural to consider. Define therefore \(d_{st}=max_{S:|S|=s}d(S,t).\) As is easy to see from the definition, \(d_{11}\) is just the diameter of the digraph. We call a digraph connected if \(d_{11}\) is finite. [Use of the verbiage strongly connected is never used in this paper.] This is equivalent to saying that there exists a path (of directed edges) starting at vertex \(i\) and ending at vertex \(j\), for all vertices \(i,j\) of the digraph; \(i\neq j\). In particular, this is applicable to graphs as well. We wish to highlight a property, immediately apparent from definitions, that all graphs have but typically digraphs do not: A graph \(G\) is connected if and only if there exists a vertex in \(G\) from which \(G\) can be synchronized.
We call \(d_{st}(G)\) the higher-order diameters of digraph \(G\) and they are the main subject of study in this paper. For brevity we sometimes call higher-order diameters simply higher diameters and, henceforth, we refer to the activation threshold simply as the threshold. Any subset of digraph \(G\) with \(s\) vertices is called an \(s-\)subset.
Fix a threshold \(t\) and a value of \(s\). Besides \(d_{st}\), other measures of spread on digraphs can prove useful. As a first intuitive example, the ratio \(p_{st}(G)=\)(number of \(s-\)subsets \(S\) that bring \(G\) to synchrony)/(number of all \(s-\)subsets) signifies the probability of bringing digraph \(G\) to synchrony from a randomly chosen \(s-\)subset. Generally we are interested in identifying digraphs with large \(p_{st}\). It might also be observed that there are many instances when a digraph has a large \(p_{st}\) but the number of steps required to attain synchrony are generally quite large, which may be inadequate for successful circuit function.
We could tune this up by defining another measure \(v_{st}(G)\), which we call the velocity to synchrony, as follows: \[v_{st}(G)={n\choose s}^{-1}\sum\limits_{S:|S|=s}d(S,t)^{-1}.\]
Observe that when \(S\) does not induce synchrony, \(d(S,t)=\infty\), and we simply add a zero to the sum. Intuitively, the velocity \(v_{st}\) yields the average speed to the synchrony of \(G\) across all \(s-\)subsets. High values of \(v_{st}\) are typically desirable, since synchrony is then speedily achieved.
While bootstrap percolation deals with the spread of activity on a digraph with a threshold \(t\), in the way that we have defined it, the previous literature in this area has focused on critical transitions, or abrupt changes in the probability of synchrony as the connection probability within a graph or digraph is increased [19,23,13,8]. More general analysis of the nature of the activation process, and how it depends on the detailed properties of the underlying digraph, including local component structure, represents an alternative perspective; for example, we have not encountered the concept of velocity to synchrony used in the digraph (or network) optimization literature so far.
In Section 2 we briefly record some basic properties of the measures that we introduced to assess how information (or activity) spreads in a digraph. The diameter of Cayley graphs has received much attention in the the literature, and hence consideration of Cayley digraphs represents a natural starting point for our investigation of higher-order diameters. Sections 3 and 4 initiate such a study, with Section 3 presenting results related to finite groups and the cyclic groups in particular, while Section 4 presents asymptotic behavior of the higher-order diameters. In Section 5 we turn our attention to velocity to synchrony and present sets of digraphs that exhibit some optimal behavior with regard to this measure of spread.
The following result follows easily from the definitions in the previous section.
Proposition 2.1. Matrices \((p_{st}),\) \((v_{st})\), and \((d_{st}^{-1})\) are lower triangular. In each of these three matrices the entries in each row are decreasing. Entries in each column of \((d_{st}^{-1})\) are increasing.
Proof. There are two monotonic properties that are used, which follow immediately from the definitions. The first is to observe that for \(A\subseteq B\) we have \(d(A,t)\geq d(B,t)\), for any fixed threshold \(t\); the second is the equally obvious \(d(S,t)\leq d(S,t+1)\), for any \(s-\)subset \(S\). We verify the assertion for \((v_{s,t})\), the other statements being just as easy to verify. Indeed, \({n\choose s}v_{st}=\sum\limits_{S:|S|=s}d(S,t)^{-1}\geq \sum\limits_{S:|S|=s}d(S,t+1)^{-1}={n\choose s}v_{s,t+1}.\)
The word increasing in Proposition 2.1 does not mean the increase is strict; likewise for decreasing.
Typically we write \(p_{st}(K)\) for the measure \(p_{st}\) of digraph \(K,\) and likewise for the other measures. If \(G\) is a digraph and \(e\) is an edge whose endpoints are among the vertices of \(G,\) we write \(K=G\cup e\) for the digraph obtained from \(G\) by tossing in the extra edge \(e.\) It is again easy to see from the definitions, by considering the measure of spread in the original digraph without edge \(e\) and then adding the spread through edge \(e\), that the measures we introduced are also monotone in any new pathways (that is, additional edges) added to a digraph; we state this below.
Proposition 2.2. The measures of spread have the following monotone properties: \(p_{st}(G\cup e)\geq p_{st}(G),\) \(d_{st}(G\cup e)\leq d_{st}(G),\) and \(v_{st}(G\cup e)\geq v_{st}(G).\)
Let us start with a digraph \(G\) with \(n\) vertices, a threshold \(t\) and a subset \(S\) of \(|S|=s\) active vertices. We want to examine what happens when the digraph reaches a stationary state. By construction, stationarity implies that there is a vertex partition \(A\) and \(I:=G\backslash A\), where \(A(\supseteq S)\) is the set of active vertices activated from \(S\); we assume also that \(I\neq\emptyset,\) so synchrony has not occurred. Stationarity means that no vertex in \(I\) can be activated in one step from set \(A\), and a fortiori cannot be activated from the incipient set \(S.\) For any vertex \(x\in G\) and any subset \(U\) of \(G\), let \(id_Ux\) denote the \(in-degree\) of \(x\) with respect to \(U\), defined as the number of edges that originate in \(U\) and point to \(x\); analogously, \(od_Ux\) denotes the \(out-degree\) of \(x\) with respect to \(U\) and is defined as the number of edges that originate at vertex \(x\) and point to vertices in \(U.\) With this notation, stationarity is equivalent to \(\exists (A,I)\) a partition of vertices of \(G\) such that \(id_Ax<t\), \(\forall x\in I.\)
Recall that digraph \(G\) is called regular of degree h if each vertex of \(G\) has \(h\) edges emanating from it, and \(h\) edges pointing to it. Specializing our observations just made to a regular digraph \(G\) of degree \(h\) in this case stationarity can be stated as follows: \(\exists (A,I)\) a partition of vertices of \(G\) such that \(id_Ix>h-t\), \(\forall x\in I.\) These observations help us establish the following result, where we take \(h, s, t\) to be natural numbers.
Theorem 2.3. (a) Let \(t\) be the activation threshold and \(s\geq t.\) Digraph \(G\) cannot be synchronized starting from subset \(S\), with \(|S|=s\), if and only if \(\exists\) subset \(A\) of vertices activated from \(S\), \(S\subseteq A\neq G,\) such that \(id_Ax<t\), \(\forall x\in G\backslash A\).
(b) Let \(t\) be the activation threshold, \(h\geq t\) and \(s\geq t.\) Regular digraph \(G\) of degree \(h\) cannot be synchronized starting from subset \(S\), with \(|S|=s\), if and only if \(\exists\) subset \(A\) of vertices activated from \(S\), \(S\subseteq A\neq G,\) such that \(id_{G\backslash A}x>h-t\), \(\forall x\in G\backslash A\).
Proof. Regarding part (a), we start with set \(S\) of active vertices, and after \(m\) steps we reach \(S_m\) such that \(S\subseteq S_m=S_i\), for all \(i\geq m\). Define \(A\) to be \(S_m\). Stationarity is equivalent to \(A\) being a proper subset of vertices of \(G\), and the maximality of \(A\) (by inclusion) forces \(id_Ax<t\) for all vertices \(x\) of \(G\) that are not in \(A\). Part (b) follows from part (a) by observing that regularity of \(G\) entails \(id_Ax+id_{G\backslash A}x=h\). Condition \(id_Ax<t\) becomes now equivalent to \(id_{G\backslash A}x=h-id_Ax>h-t\), for all \(x\) not in \(A\).
We next turn our attention to Cayley digraphs associated with finite groups; see [15]. Our motivation for this arises first from the intuition that, by virtue of their construction, we expect Cayley digraphs to support the rapid spread of activation and hence to provide insights into structures that may serve this role in applications; second, from the fact that diameters \(d_{11}\) of Cayley graphs have been extensively studied, providing an opportunity to connect with existing literature; and third, from the fact that the structure of Cayley digraphs is convenient for performing certain calculations related to the spread of activity from an initially active set.
Let \(\Gamma\) be a finite group and \(H\) a generating subset of \(\Gamma\) that does not contain the identity element 1 of \(\Gamma\). Produce a Cayley digraph \(G = Cay(\Gamma ,H)\) of \(\Gamma\) and \(H\) by defining vertices of \(G\) to be elements of \(\Gamma\) and placing an edge \((x,y)\) from vertex \(x\) to vertex \(y\) if \(y=hx\) for some \(h\in H.\) The operations that take place are in the group \(\Gamma\). Often the set of generators \(H\) is understood from the context, in which case we abbreviate by simply writing \(G\) for \(Cay(\Gamma ,H)\). Since 1 is not in \(H\) there are no loops in a Cayley digraph, and the group cancellation law prohibits creation of multiple edges. It is also easy to see that in a Cayley digraph each vertex has \(|H|\) edges pointing to it (i.e., in-degree \(|H|\)) and \(|H|\) edges emanating from it (i.e., out-degree \(|H|\)) and hence is regular of degree \(|H|\).
The vast majority of work related to diameters involves graphs, rather than digraphs. In particular, significant contributions were made in the asymptotic understanding of the diameters of the finite simple groups, and in particular the groups of Lie type and the alternating groups; see [22]. Useful contributions on the diameters \(d_{11}\) of Cayley graphs, from our perspective, are found in [6,18,16], the closest to the applications we aim for being the examples of large Cayley graphs of small diameters, examples of which appear in [7]. Our main interest, however, is to initiate the study of the higher-order diameters \(d_{st}\). To our knowledge no results about \(d_{st}\) are available in the literature, for \(s,t>1\). To this end, for a Cayley digraph \(Cay(\Gamma ,H)\) we need to start from \(s-\)subsets and compute \(d_{st}\) for fixed \(t\)\(.\) Specifically, for a finite group \(\Gamma\) fix a generating subset \(H\subseteq\Gamma\) and produce \(G =Cay(\Gamma ,H)\); whereas the action of \(\Gamma\) on the vertices of \(G\) is transitive (as a right-regular representation), the same is not true of the action of \(\Gamma\) on the \(s-\)subsets of \(G\), for \(s>1.\) We need to study this action first. Let \(S\) be an \(s-\)subset of \(G\). We define \(Sg\) to be the set \(\{xg:x\in S\}\). Group \(\Gamma\) acts, therefore, on the \(s-\)subsets of \(G\) (or of \(\Gamma\)) by right translation.
Lemma 3.1. If \(\Gamma\) acts by right translation on the s-subsets, then the number of resulting orbits is the coefficient of \(y^s\) in the polynomial \(P_{\Gamma}(1+y,1+y^2,\ldots ,1+y^n)\). Here \(P_{\Gamma}\) is the cycle index of \(\Gamma\) in its right-regular permutation representation on the group elements of \(\Gamma\) and \(|\Gamma |=n.\)
Proof. This follows from the well-known orbit-counting formula of Frobenius and the cycle index theory of Redfield and DeBruijn. For details, see [21] or [5, page 225].
The Lemma that follows informs us that, in the case of Cayley digraphs, it suffices to evolve the spreads simply from representatives of the distinct orbits of the \(s-\)subsets.
Lemma 3.2. For any fixed threshold \(t,\) if s-subsets \(X\) and \(Y\) are in the same orbit, then \(d(X,t)=d(Y,t)\).
Proof. Write \(Y=Xg\) for some \(g\in G.\) We activate \(z\) from \(X\) if and only if \(\exists\) \(h_1,\ldots ,h_t\), distinct elements of \(H\), such that \(z=h_ix_i\) for \(x_i\in X\), \(1\leq i\leq t\). Note now that \(z\) is activated from \(X\) if and only if \(zg\) is activated from \(Xg=Y\) via the same \(h_i\) through the images \(x_ig\in Xg=Y.\) This bijective mapping is being repeated and it holds true at every step of the activation process. We conclude that \(d(X,t)=d(Y,t).\)
For any finite group we can compute some specific higher-order diameters of the associated Cayley digraphs.
Proposition 3.3. Let \(\Gamma\) be a finite group, \(H\) a generating set for \(\Gamma\), and \(t\) the activation threshold. In the Cayley digraph \(G=Cay(\Gamma ,H)\), let \(S\) be a set of initially active vertices and \(G\backslash S\) be the set of initially inactive vertices. If \(t=|H|-k\), then \(G\) can be synchronized from \(S\) if and only if \(G\backslash S\) contains no subdigraph \(K\) with \(id_Kx\geq k+1,\) \(\forall x\in K\).
Proof. Let \(I:=G\backslash S.\) Assume that \(I\) contains such a subdigraph \(K\). We show that \(G\) cannot synchronize. Evidently \(id_Ix\geq k+1\) for all vertices \(x\in K.\) Thus at the initial activating step \(id_Sx\leq |H|-(k+1)<|H|-k=t,\) for all \(x\in K.\) Therefore no vertices in \(K\) will activate at the first step. Iteratively, vertices of \(K\) will never activate and \(G\) will fail to synchronize.
We now assume that \(G\) does not synchronize and force the existence of a subdigraph \(K\) in \(I\) having the stated properties. The assumption implies that we reach stationarity with a bipartition into active vertices \(A\) and inactive vertices \(J\) (with \(J\) nonempty). Clearly \(S\subseteq A\) and \(J\subseteq I.\) Define \(K\) to be subdigraph \(J.\) Let \(x\in K.\) Then \(id_Kx\geq k+1,\) else \(x\) would have been activated from \(A,\) since \(t=|H|-k.\) It is now seen that \(K\) is a subdigraph of \(I=G\backslash S\) with the desired properties.
By a cycle in a digraph we always mean a directed cycle. The case of Proposition 3.3 with \(k=0\) is highlighted next, since it allows explicit computation of some higher-order diameters.
Corollary 3.4. Let \(\Gamma\) be a finite group, \(H\) a generating set for \(\Gamma\), and \(t\) the activation threshold. In the Cayley digraph \(G:=Cay(\Gamma , H)\), let \(S\) be a set of initially active vertices and \(G\backslash S\) be the set of initially inactive vertices. If \(t=|H|\), then \(G\) can be synchronized from \(S\) if and only if \(G\backslash S\) is cycle-free.
Proof. Taking \(k=0\) in Proposition 3.3 yields the result, but we shall examine the nature of the subdigraph \(K\) more closely in this case. Specifically, we assume that \(G\) does not synchronize and force the existence of a cycle in \(I.\) The assumption implies that we reach stationarity with a bipartition into active vertices \(A\) and inactive vertices \(J,\) and \(J\) contains an inactive vertex \(g_1.\) Clearly \(S\subseteq A\) and \(J\subseteq I.\) Since \(t=|H|\) and \(g_1\in J\) it follows that there exists \(g_2\in J\) and \(g_2\) points to \(g_1.\) We now start with \(g_2\) and iterate the process. This yields a set of vertices (\(g_1,\) \(g_2,\) \(g_3,\) …) with \(g_{i+1}\) pointing to \(g_i\) and with all \(g_ j\in J.\) Since \(J\) is finite this forces one of the \(g_i\) to be revisited, thus generating a cycle in \(J\subseteq I.\)
We are now in position to compute some higher diameters of Cayley digraphs. Let \(G\) be the Cayley digraph \(Cay(\Gamma ,H)\), with \(|G|=n\) and \(|H|=h.\) Denote by \(m\) the minimum cycle length among all cycles in \(G.\) Scalar \(m\) is called the girth of \(G.\) We demonstrate the following result.
Theorem 3.5. Let \(G=Cay(\Gamma ,H)\) be a Cayley digraph having girth \(m\). If the activation threshold \(t\) is equal to \(h=|H|\), then the diameter \(d_{st}(G)=n-s\) whenever \(s>n-m,\) and is infinite otherwise.
Proof. For \(s>n-m\), the initially inactive set will not contain a cycle so by Corollary 3.4 digraph \(G\) will synchronize for all starting conditions with \(s\) vertices active. Since there are \(n-s\) initially inactive vertices, the worst case activation among the initially active sets of size \(s\) is when the digraph activates in exactly \(n-s\) steps (i.e., the worst case activation is by activating vertices one-at-a-time). In particular, for \(s>n-m\), we have that \(d_{st}(G)\leq n-s\) (we remark that this inequality holds for \(s\) large enough to guarantee that the digraph will eventually fully activate). We show that, in fact, \(d_{st}(G)=n-s\).
Label the vertices in the minimal cycle as \(g_1, g_2, \ldots, g_m\) such that we have edges \((g_1, g_2)\), \((g_2,g_3)\), \(\dots\) \((g_{m-1}, g_m)\), \((g_m, g_1)\). We assert that \(d_{st}(G)=n-s\) if we take our initially active set to be \(\{g_1,g_2,…,g_{s-(n-m)}\}\) and all other vertices inactive (that is, take all vertices not in the minimal cycle to be active, and then take the first \(s-(n-m)\) vertices in the cycle to be active). In this case the set of initially inactive vertices is \(U=\{g_{s-(n-m)+1},…,g_m\}\). Consider the vertex \(g_{s-(n-m)+1}\). We show that this vertex receives an input of \(h\) at the first time step. If we assume for the sake of contradiction that \(g_{s-(n-m)+1}\) receives an input of less than \(h\), then there must be some vertex \(g_k\in U\backslash \{g_{s-(n-m)+1}\}\) that has an edge to \(g_{s- (n-m)+1}\) since all other vertices are active. However, this would form a cycle with nodes \(g_{s-(n-m)+1},g_{s-(n-m)+2},\dots g_{k-1}, g_k\) and edges \((g_{s-(n-m)+1},g_{s-(n-m)+2})\), \((g_{s-(n-m)+2},g_{s-(n-m)+3})\), \(\dots\) \((g_{k-1}, g_k), (g_k, g_{s-(n-m)+1})\) of length \(k-s+(n-m) < k \leq m\) which contradicts \(m\) being the minimal cycle length. Thus, \(g_{s-(n-m)+1}\) receives an input of at least \(h\) and will activate at the first time step. Now consider some vertex \(g_k\in U\backslash \{g_{s-(n-m)+1}\}\). We will show that \(g_k\) does not activate at the first time step. Since \(k>s-(n-m)+1\), vertex \(g_{k-1}\) is initially inactive. Thus, \(g_k\) can have at most an input of \(h-1\) since \(g_{k-1}\) is inactive and \(g_k\) has an in-degree of \(h\). Thus, \(g_k\) will not activate for \(k\in \{s-(n-m)+1,…,m\}\). Iteratively, we conclude that the remainder of the cycle will activate one vertex at a time hence, for \(s>n-m\), we obtain \(d_{st}(G)=n-s\). The result for \(s \leq n-m\) follows from Corollary 3.4.
Example 3.6. Consider \(G=Cay(C_7,H)\) with \(H=\{a,a^2,a^3\}.\) The girth is 3 as is seen in the cycle \((1,a^3,a^6)\) with edges \((1,a^3)\), \((a^3,a^6)\), \((a^6,1)\). Theorem 3.5 yields \(d_{s3}(G)=7-s\) for \(s>4,\) and \(\infty\) otherwise; this can be verified directly.
If we consider \(s=5,\) then \(d_{53}(G)=2;\) this diameter value is obtained from the initially active set \(\{1,a,a^2,a^4,a^5\}.\)
Lastly, we examine Theorem 3.5 in the case \(G=Cay(C_{11},H)\) with \(H=\{a,a^6\}.\) Here the girth is 6, which is seen in the cycle \((1,a^6,a^7,a^8,a^9,a^{10}\)) with edges \((1, a^6)\), \((a^6, a^7)\), \((a^7, a^8)\), \((a^8, a^9)\), \((a^9, a^{10})\), \((a^{10}, 1)\). By Theorem 3.5 we have \(d_{s2}(G)=11-s\) for \(s>5.\) For instance, when \(s=6\) we obtain \(d_{62}(G)=11-6=5\); this value is attained from the initially active set \(\{1,a,a^2,a^3,a^4,a^5\}.\)
In general it is difficult to find explicit formulae for the diameter of sufficiently complex classes of groups, such as finite groups of Lie type or symmetric groups. Asymptotic approximations exist but the proofs are quite intricate and typically deal with graphs, rather than digraphs. Computing higher-order diameters of the associated digraphs does not, in any way, simplify the process. We therefore start by first examining the cyclic groups \(C_p\) for \(p\) prime. As a motivating example, we present an exhaustive computation of all higher-order diameters for the group \(C_7.\) The results are summarized in Table 1.
For \(|H|=6\) we have the complete digraph on 7 vertices, hence for \(s\geq t\), all \(d_{st}\) diameters are 1.
| \(|H| = 1\) | \(|H|=2\) | \(|H|=3\) | \(|H|=4\) | \(|H|=5\) | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(t=1\) | \(t=1\) | \(t=2\) | \(t=1\) | \(t=2\) | \(t=3\) | \(t=1\) | \(t=2\) | \(t=3\) | \(t=4\) | \(t=1\) | \(t=2\) | \(t=3\) | \(t=4\) | \(t=5\) | |
| \(s=1\) | \(6\) | \(3\) | \(2\) | \(2\) | \(2\) | ||||||||||
| \(s=2\) | \(5\) | \(2\) | \(\infty\) | \(2\) | \(3\) | \(2\) | \(2\) | \(1\) | \(2\) | ||||||
| \(s=3\) | \(4\) | \(2\) | \(\infty\) | \(2\) | \(2\) | \(\infty\) | \(1\) | \(2\) | \(\infty\) | \(1\) | \(1\) | \(2\) | |||
| \(s=4\) | \(3\) | \(2\) | \(3\) | \(1\) | \(2\) | \(\infty\) | \(1\) | \(1\) | \(2\) | \(\infty\) | \(1\) | \(1\) | \(1\) | \(\infty\) | |
| \(s=5\) | \(2\) | \(1\) | \(2\) | \(1\) | \(1\) | \(2\) | \(1\) | \(1\) | \(1\) | \(\infty\) | \(1\) | \(1\) | \(1\) | \(1\) | \(\infty\) |
| \(s=6\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
We specify the choices of \(H\) that yield the smallest \(d_{st}\) values in Table 1. In many cases the \(d_{st}\) entry is invariant to the choice of \(H.\) The cases where it is not are as follows. Write \(|H|=h.\) Then \((h,t,s)=(2,1,2)\) has \(H=\{a,a^3\};\) \((h,t,s)=(2,2,4)\) has \(H=\{a,a^2\}\); \((h,t,s)=(2,2,5)\) has either \(H=\{a,a^2\}\) or \(H=\{a,a^3\}.\) Also, \((h,t,s)=(3,2,2)\) has \(H=\{a,a^2,a^4\}\); \((h,t,s)=(3,2,3)\) has either \(H=\{a,a^2,a^3\}\) or \(H=\{a,a^2,a^4\}\); \((h,t,s)=(3,3,5)\) has either \(H=\{a,a^2,a^3\}\) or \(H=\{a,a^2,a^4\}\). Lastly, \((h,t,s)=(4,2,2)\) has \(H=\{a,a^2,a^3,a^5\}\); and \((h,t,s)=(4,3,4)\) has either \(H=\{a,a^2,a^3,a^4\}\) or \(H=\{a,a^2,a^3,a^5\}.\) Lemma 3.2 and a suitable choice of orbit representatives were used in computing all entries in Table 1 and the corresponding generating sets we just listed.
We may apply Theorem 3.5 to obtain higher diameter values for the group \(C_p.\) We need a formula for girth of the Cayley digraphs that arise in this case. Initially we examine the case \(G=Cay(C_p,H)\) where \(H=\{a,a^k\}.\) The minimum cycle length is easily seen to be written as \(m=min_{z,w}\{z+w:z+wk=0\) mod \(p\)\(\}\), where \(z\) and \(w\) are nonnegative integers. We have that \(z+wk=np\) for some \(n\in \mathbb{N}\), so \(z+w=np-w(k-1).\) In this rewriting, \[m=min_{n,w}\{np-w(k-1):np-wk>0\},\] with \(n\in \mathbb{N}\) and \(w\in \mathbb{N}\cup 0.\) For a fixed \(w,\) the value of \(n\) that attains this minimum is given by the minimum value of \(n\) satisfying \(np-wk>0.\) For fixed \(w\), we may thus take \(n=\lceil\frac {wk}p\rceil\), where \(\lceil x\rceil\) denotes the least integer greater than or equal to \(x.\) We thus obtain \[m=min_{w\in \{1,\ldots ,p\}}\{p\lceil\frac {wk}p\rceil -w(k-1)\}.\]
The argument presented above generalizes and allows us to establish the following result.
Proposition 3.7. The girth of \(G=Cay(C_p,H)\) with \(H=\{a,a^{k_1},\ldots ,a^{k_q}\}\) is \[m=min_{\substack{{w_1,\ldots ,w_q\in \{0, 1,\ldots ,p\}} \\ (w_1,…,w_q) \neq (0,…,0)}} \left\{ p\lceil\frac 1p\sum\limits_{ i=1}^qw_ik_i\rceil -\sum\limits_{i=1}^qw_i(k_i-1) \right\}.\]
Higher diameter values of Cayley digraphs of \(C_p\) now explicitly follow from Proposition 3.3, Corollary 3.4, and Theorem 3.5.
Our fist result in this section establishes the fact that Cayley digraphs asymptotically have almost surely higher-order diameters \(d_{s1}\leq 2\).
Theorem 4.1. Let \(\Gamma\) be a finite group of order \(n\), and fix a constant \(c\in(0,1)\). Construct a random subset \(H\subseteq \Gamma\setminus\{1\}\) by including each nonidentity element of \(\Gamma\) independently with probability \(c\). Form the Cayley digraph \(G = \mathrm{Cay}(\Gamma,H)\), with vertex set \(\Gamma\) and an edge \((x,y)\) whenever \(x^{-1}y\in H\). Then, for every fixed \(s\ge 1\), we have \[P\big(d_{s1}(G) > 2\big) \longrightarrow 0 \qquad \text{as } n\to\infty.\]
Proof. We first use the monotonicity property established in Proposition 2.1. Specifically, we have the deterministic inequality \(d_{s1}(G)\leq d_{11}(G)\), for every \(s\geq 1\).
Consequently \(\{d_{s1}(G) > 2\}\subseteq \{d_{11}(G) > 2\}\), and in order to prove the theorem, it suffices to prove \[P\big(d_{11}(G) > 2\big)\longrightarrow 0.\]
Fix two distinct vertices \(x,y\in\Gamma\). We bound the probability that \(y\) is not reachable from \(x\) within two steps.
For each \(z\in \Gamma\setminus\{x,y\}\) define the two group elements \[L(z) := x^{-1}z, \qquad R(z) := z^{-1}y.\]
\(L(z)\) and \(R(z)\) may be interpreted as edges \((x,z)\) and \((z,y)\) in \(G\). Thus \(z\) furnishes a directed \(2\)-path from \(x\) to \(y\) exactly when the event \[C(z):\quad L(z)\in H \ \text{ and }\ R(z)\in H,\] occurs. Denote by \(\overline C(z)\) the complementary event to \(C(z)\). We than have \[P\big(y \text{ not reached from } x \text{ in } \le 2 \text{ steps}\big) \ \le\ P\Big(\bigcap_{z} \overline C(z)\Big).\]
The inequality accounts for the possibility that \((x,y)\) is itself an edge, which only makes reachability easier and \(C(z)\) occurring only easier still; we do not need to track the direct edge separately.
The events \(C(z)\) are not independent as \(z\) ranges over all of \(\Gamma\setminus\{x,y\}\), because different values of \(z\) can involve the same element of \(H\): e.g. \(L(z)\) and \(R(z’)\) may coincide for \(z\neq z’\), and then the events \(C(z)\), \(C(z’)\) both depend on whether that common element lies in \(H\). We handle this by passing to a sufficiently large independent sub-collection, the construction of which is explained in the two Steps that follow.
Step 1. Define a graph \(G_{x,y}\) on the vertex set \(\Gamma\setminus\{x,y\}\) (of order \(n-2\)) by joining \(z\) and \(z’\) (\(z\ne z’\)) whenever \[\{L(z),R(z)\}\ \cap\ \{L(z’),R(z’)\}\ \neq\ \emptyset .\]
Then every vertex of \(G_{x,y}\) has degree at most \(2\).
Proof. Fix \(z\in\Gamma\setminus\{x,y\}\). Since \(z\) and \(z’\) are different elements of \(G_{x,y}\), by the cancellation law in \(\Gamma\), this can only occur if \(L(z)=R(z’)\) or \(R(z)=L(z’)\). In the first case the equation reads \(x^{-1}z={z’}^{-1}y\), which yields to the unique solution \(z’=yz^{-1}x\). The second case analogously yields the unique \(z’=xz^{-1}y\). It follows that \(z\) can have at most two neighbors in \(G_{x,y}\), as asserted.
Step 2. A graph with \(m\) vertices and with maximum degree 2 has a set \(W\) of independent vertices \((\)that is, vertices of which no two are joined\()\) with \(|W|\geq m/3\).
Proof. To see this, pick any vertex of the graph, toss it into \(W\), then delete it and all its neighbors from the graph. Iterate the process in the remaining graph. Each such iteration removes at most 3 vertices. The process runs for at least \(m/3\) iterations, which yields \(|W|\geq m/3\).
By the construction of \(W\), the two-element sets \(\{L(z),R(z)\}\), \(z\in W\), are pairwise disjoint, so the elements \(L(z),R(z)\) for \(z \in W\) are all pairwise distinct nonidentity group elements. Since \(H\) is formed by including each nonidentity element of \(\Gamma\) independently with probability \(c\), the events \(\{C(z)\}_{z\in W}\) are mutually independent, and each has probability \[P(C(z)) \;=\; P(L(z)\in H)\,P(R(z)\in H) \;=\; c^2 \qquad (z \in W).\]
Since \(W \subseteq \Gamma\setminus\{x,y\}\), we may now write \[\begin{aligned} P\big(y \text{ not reached from } x \text{ in } \le 2 \text{ steps}\big) &\le\ P\Big(\bigcap_{z\in\Gamma\setminus\{x,y\}} \overline C(z)\Big)\\ & \le\ P\Big(\bigcap_{z\in W} \overline C(z)\Big)\\ &=\ \prod_{z\in W}\big(1-c^2\big)\\ & =\ (1-c^2)^{|W|}. \end{aligned}\]
Using \(|W|\ge (n-2)/3\) and \(0<1-c^2<1\), \[P\big(y \text{ not reached from } x \text{ in } \le 2 \text{ steps}\big) \ \le\ (1-c^2)^{(n-2)/3}.\]
This bound is uniform over all ordered pairs \((x,y)\) with \(x\ne y\), of which there are \(n(n-1) < n^2\). By the union bound, \[P\big(d_{11}(G) > 2\big) = P\Big(\exists\, x\ne y:\ y \text{ not reached from } x \text{ in }\le 2 \text{ steps}\Big) \ \le\ n^2 (1-c^2)^{(n-2)/3}. \label{eq:3.2}\]
Since \(c \in (0,1)\), we have \(0 < 1-c^2 < 1\), so the right-hand side decays exponentially in \(n\) while \(n^2\) grows only polynomially; hence \[n^2 (1-c^2)^{(n-2)/3} \longrightarrow 0, \qquad \text{as } n\to\infty,\] which gives \(P\big(d_{11}(G) > 2\big) \longrightarrow 0, \; \text{as } n\to\infty.\)
The result below presents the asymptotic behavior of the higher-order diameters \(d_{st}\) within the context of random digraphs.
Theorem 4.2. Consider a class of random digraphs on \(n\) vertices in which each ordered pair \((x,y)\), \(x\ne y\), is independently declared an edge with probability \(p(n)<1\), and fix any \(t\ge 1\). If \(p(n)\gg n^{-a}\) for some fixed \(0<a<\tfrac{1}{2t}\), then almost surely \(d_{st}(G)\le 2\) as \(n\to\infty\), for every fixed \(s\ge t\).
Proof. By Proposition 2.1 we know that \(d_{st}\leq d_{tt}\), for all \(s\geq t\). It suffices, therefore, to prove the theorem just for the case \(s=t\).
Fix a set \(S\) with \(|S|=t\) and a vertex \(v\notin S\). We bound the probability that \(v\) is not activated from \(S\) within two steps. For each vertex \(x\notin S\cup\{v\}\) define the events \[U_x:\ \text{all $t$ edges } (s,x),\ s\in S,\ \text{are present}, \qquad W_x:\ \text{the edge } (x,v)\ \text{is present},\] and set \(I_x=\mathbf 1_{U_x\cap W_x}\) to be the indicator function of the event \(U_x\cap W_x\). If \(I_x=1\) then \(x\) is activated from \(S\) in the first step (it receives all \(t\) available edges from \(S\), meeting the threshold \(t\) exactly), and \(x\) sends an edge to \(v\); thus \(x\) contributes one activating edge into \(v\) at the start of the second step.
The event \(I_x\) depends only on the \(t+1\) edges \(\{(s,x):s\in S\}\cup\{(x,v)\}\). For distinct \(x,x’\notin S\cup\{v\}\) these edge sets are disjoint (they involve different endpoints \(x\ne x’\)), and by the independence of distinct edges in the random digraph model, the variables \((I_x)_{x\notin S\cup\{v\}}\) are mutually independent, each with \[P(I_x=1)=p^{t}\cdot p=p^{t+1}.\]
Let \(N=\sum\limits_{x\notin S\cup\{v\}} I_x\). Since \(N\) is a sum of identical independent Bernoulli variables it has a Binomial distribution. Specifically, \(N\) is distributed as \(\mathrm{Bin}(n-t-1,\,p^{t+1})\). If \(N\ge t\), then at the start of the second step at least \(t\) distinct already-active vertices (namely the \(x\)’s with \(I_x=1\)) each send an edge into \(v\), so \(v\) activates within two steps regardless of any other edges into \(v\). Consequently \[P\big(v\text{ not activated from } S\text{ within 2 steps}\big)\ \le\ P(N< t).\]
We now use Chernoff’s inequality to place a bound on the tail on \(N\). Denote by \(\mu\) the expected value of \(N\). Hence \(\mu=(n-t-1)p(n)^{t+1}\). Since \(p(n)\gg n^{-a}\), for all sufficiently large \(n\) we have \(p(n)\ge n^{-a}\), and therefore \[\mu\ \ge\ (n-t-1)\,n^{-a(t+1)}\ \sim\ n^{1-a(t+1)}.\]
Because \(a<\dfrac{1}{2t}\le\dfrac{1}{t+1}\), we have \(a(t+1)<1\); set \(\varepsilon_0:=1-a(t+1)>0\), so that \(\mu\ge c\,n^{\varepsilon_0}\) for some constant \(c>0\) and all large \(n\); in particular \(\mu\to\infty\).
Since \(t-1\) is a fixed constant while \(\mu\to\infty\), for all sufficiently large \(n\) we have \(\mu/2>t-1\). Applying the multiplicative Chernoff bound for a binomial random variable with mean \(\mu\) \(\Big(\)lower tail, \(\delta=\tfrac12\Big)\): \[P(N\le t-1)\ \le\ P\big(N\le \mu/2\big)\ \le\ \exp(-\mu/8)\ \le\ \exp(-c’n^{\varepsilon_0}),\] for some constant \(c’>0\) and all \(n\) large enough. (The bound \(P(N\le(1-\delta)\mu)\le e^{-\delta^2\mu/2}\) used here is the standard multiplicative Chernoff bound for sums of independent \(\{0,1\}\)-valued random variables; see [1, page 307].)
Combining the two inequalities above, \[P\big(v\text{ not activated from } S\text{ within 2 steps}\big)\ \le\ \exp(-c’n^{\varepsilon_0}).\]
The number of pairs \((S,v)\) with \(|S|=t\) and \(v\notin S\) is \(\binom{n}{t}(n-t)=O(n^{t+1})\), a fixed polynomial in \(n\) since \(t\) is fixed. By the bound above and the union bound, \[\begin{aligned} P\big(d_{tt}(G)>2\big)=&P\Big(\exists\,(S,v):\ v\text{ not activated from } S \text{ within 2 steps}\Big)\\ \le& O(n^{t+1})\exp(-c’n^{\varepsilon_0}). \end{aligned}\]
Since \(\varepsilon_0>0\), the exponential decay dominates the polynomial factor, so the right-hand side tends to \(0\) as \(n\to\infty\), as stated.
Denote by \(g(n,m)\) the set of digraphs with \(n\) vertices and \(m\) edges. For a given threshold \(t\) our aim is to find a description of the digraphs in \(g(n,m)\) that have maximal velocity. We assume that the cardinality of the start-up sets is also \(t\).
Construct digraphs \(G^*\in g(n,m)\) as follows. Fix an integer \(r\) with \(t\le r<n\) and \(t(n-r)<n-1\), and suppose \[r(n-1)+t(n-r)\ \le\ m\ <\ (r+1)(n-1).\]
Pick a set \(R\) of \(r\) vertices and produce edges \((v,w)\) with \(v\in R\) and \(w\) any other vertex, \(w\ne v\). This yields \(r(n-1)\) edges. Observe that the vertices in \(R\) span a complete digraph \(K_r\) containing \(r(r-1)\) edges. The set \(R\) of vertices, and sometimes also the induced digraph \(K_r\) spanned by these vertices, is called the core. There are \(n-r\) vertices not in \(R\); denote them by \(R^c\). Fix a subset \(H\subseteq R\) with \(|H|=t\), which we call the hub, and produce edges \((v,h)\) for every \(v\in R^c\) and every \(h\in H\). This yields a further \(t(n-r)\) edges. We still need \(m-r(n-1)-t(n-r)\ge 0\) additional edges, and we assign these arbitrarily. The digraph \(G^*\in g(n,m)\) is now defined. As is evident from its construction, the digraph \(G^*\) is, in general, not unique up to isomorphism. We enunciate as follows.
Theorem 5.1. Let \(n,m,r,t\) be natural numbers such that \(t\le r<n\), \(t(n-r)<n-1\), and \(r(n-1)+t(n-r)\le m<(r+1)(n-1)\). Then a digraph \(G^*\) as constructed above exists, it satisfies \(d_{tt}(G^*)\le 2\), and it has maximal velocity \(v_{tt}\) over \(g(n,m)\), with \[\binom{n}{t}v_{tt}(G^*)\ =\ \binom{r}{t}\ +\ \left(\binom{n}{t}-\binom{r}{t}\right)/2 .\]
Proof. We first show that \(G^*\) synchronizes from every \(t\)-subset in at most two steps, and compute the number of steps exactly. Let \(T\) be a start-up subset with \(|T|=t\); write \(T_1=T\cap R\) and \(T_2=T\cap R^c\).
If \(T_2=\emptyset\), then \(T=T_1\subseteq R\), and each vertex \(w\notin T\) receives one edge from each of the \(t\) elements of \(T\), since every vertex of \(R\) has out-degree \(n-1\). Thus every inactive vertex receives \(t\) edges from \(T\) and the digraph is activated in one step.
Assume next that \(T_2\ne\emptyset\), and consider any \(h\in H\setminus T_1\). Every element of \(T_1\) points to \(h\), since \(T_1\subseteq R\setminus\{h\}\) and each vertex of \(R\) points to all other vertices; this contributes \(|T_1|=t-|T_2|\) edges into \(h\). Every element of \(T_2\) also points to \(h\), since \(h\in H\) and, by construction, each vertex of \(R^c\) points to all of \(H\); this contributes \(|T_2|\) further edges into \(h\). In total \(h\) receives \(t\) edges from \(T\) and therefore activates at the first step. Since \[|H\setminus T_1|\ =\ t-|H\cap T_1|\ \ge\ t-|T_1|\ =\ |T_2|,\] at least \(|T_2|\) such vertices \(h\) activate, so after one step the set of active vertices contains \(T_1\cup(H\setminus T_1)\), which consists of at least \(|T_1|+|T_2|=t\) vertices of the core \(R\). Each of these has out-degree \(n-1\), so at the second step every remaining inactive vertex receives at least \(t\) edges from the active set and activates. Hence \(d(T,t)\le 2\) for all \(T\), so \(d_{tt}(G^*)\le 2\).
Moreover, if \(T_2\ne\emptyset\) then \(\exists v\in T\setminus R\), and since \(v\) has out-degree strictly less than \(n-1\) there is a vertex \(w\) with \((v,w)\) not an edge; such \(w\) receives at most \(t-1\) edges from \(T\) and cannot be activated at the first step. Consequently \(d(T,t)=1\) exactly when \(T\subseteq R\), and \(d(T,t)=2\) otherwise. Counting, the velocity of \(G^*\) is \[\binom{n}{t}v_{tt}(G^*)=\sum\limits_{T:\,|T|=t}\frac{1}{d(T,t)} =\binom{r}{t}\cdot 1+\left(\binom{n}{t}-\binom{r}{t}\right)\cdot\frac12 .\]
To prove that \(G^*\) has the highest velocity we argue as follows. Let \(G\in g(n,m)\) be arbitrary. Denote by \(Q\) the set of vertices of \(G\) having out-degree \(n-1\); write \(q=|Q|\). Since the out-edges of distinct vertices are distinct, \(q(n-1)\le m<(r+1)(n-1)\), whence \(q\le r\). Observe that a \(t\)-subset \(T\) activates all of \(G\) in one step if and only if \(T\subseteq Q\): if \(T\subseteq Q\) then every vertex outside \(T\) receives one edge from each element of \(T\); while if \(T\not\subseteq Q\) then \(\exists v\in T \setminus Q\) and \(\exists w\ne v\) with \((v,w)\) not an edge of \(G\), so that \(w\) receives at most \(t-1\) edges from \(T\) and does not activate at the first step.
Assume first that \(q<t\). Then no \(t\)-subset is contained in \(Q\), so \(G\) can only be activated in two or more steps from any \(t\)-subset, and therefore \(\binom{n}{t}v_{tt}(G)\le\frac12\binom{n}{t}<\binom{n}{t}v_{tt}(G^*)\), the last inequality holding since \(\binom{r}{t}\ge 1\).
Let now \(q\ge t\), so that \(t\le q\le r\). Exactly \(\binom{q}{t}\) start-up subsets activate \(G\) in one step, and every other subset requires at least two steps. We may now write \[\begin{aligned} \binom{n}{t}v_{tt}(G) \le& \binom{q}{t}\cdot 1+\left(\binom{n}{t}- \binom{q}{t}\right)\cdot\frac12\\ =&\binom{q}{t}+\left(\binom{r}{t}-\binom{q}{t}\right)\frac12+\left( \binom{n}{t}-\binom{r}{t}\right)\frac12\\ \le& \binom{r}{t}+\left(\binom{n}{t}-\binom{r}{t}\right)\frac12 =\binom{n}{t}v_{tt}(G^*), \end{aligned}\] where the last inequality uses \(\binom{q}{t}\le\binom{r}{t}\), valid since \(q\le r\). This concludes the demonstration.
We quickly look at an example that illustrates Theorem 5. Take \(n=10\), \(t=3\), and \(r=8\). Then \(n-r=2\) and \(t(n-r)=6<9=n-1\), and the minimal admissible number of edges is \(m=r(n-1)+t(n-r)=8\cdot 9+3\cdot 2=78\). Let \(R=\{1,2,\dots,8\}\), which yields \(8\cdot 9=72\) edges of \(G^*\), and take the hub \(H=\{1,2,3\}\), which yields the six additional edges \((9,1)\), \((9,2)\), \((9,3)\), \((10,1)\), \((10,2)\), \((10,3)\). We now have a \(G^*\) in our possession. Theorem 5 tells us that this \(G^*\) maximizes \(v_{33}\) over \(g(10,78)\), with maximal velocity \[\binom{10}{3}v_{33}(G^*)=\binom{8}{3}+\left(\binom{10}{3}-\binom{8}{3} \right)\cdot\frac12=56+(120-56)\cdot\frac12=88,\] so that \(v_{33}(G^*)=\frac{88}{120}=\frac{11}{15}\). All \(56\) start-up triples contained in \(R\) synchronize the digraph in one step, and the remaining \(64\) triples synchronize it in exactly two steps.
This work was sponsored under the United States National Science Foundation grant 2424684.