Path abstraction
Steve Huntsman






steve.huntsman@baesystems.com
BAE Systems, 4301 North Fairfax Drive, Arlington, Virginia 22203



             


Given the set of paths through a digraph, the result of uniformly deleting some vertices and identifying others along each path is coherent in such a way as to yield the set of paths through another digraph, called a path abstraction of the original digraph. The construction of path abstractions is detailed and relevant basic results are established; generalizations are also discussed. Connections with random digraphs are also illustrated.



                              

Path abstraction
    Steve Huntsman
    December 30, 2023
=====================




first






§ INTRODUCTION


Each path in a digraph D corresponds to a word over the alphabet V(D). Given a subset U ⊆ V(D), consider the map ∇_U that deletes elements of U from such words. The question naturally arises: does the image of ∇_U correspond to the set of paths in some other digraph? 

In this paper, we address this and related questions. The practical motivation is that we have a complicated structure such as a digraph representing the possible flow of some some quantity through a system, and we wish to abstract away irrelevant details while efficiently preserving paths in the structure. For example, we might consider the flow of data <cit.>, taint <cit.> or provenance <cit.> in computer programs or systems. In general, we cannot assume that the structure has a hierarchical or modular organization, and so clustering or decomposition techniques do not solve the task at hand. Instead, we introduce a natural construction (originally proposed by Mukesh Dalal) that can be used in many circumstances to delete irrelevant vertices and identify related vertices (and though of course clustering and decomposition techniques can have something to say in the determination of these vertices, this issue will not be considered here). Subsequently, we can reason about paths in this construction rather than in its larger antecedent structure.

The paper is organized as follows: in <ref>, we introduce basic notation and definitions; <ref> is a sort of appetizer from the point of view of vertices rather than paths; <ref> introduces the key constructions for digraphs, which are generalized in <ref> to weighted digraphs. Random digraphs are considered in <ref>. So-called temporal networks that are essentially time series of arcs are considered in <ref>. Finally, appendices give alternative proofs of key results for digraphs and briefly indicate the potential relevance of our constructions to renormalization and percolation on random digraphs.




§ BASIC NOTATION AND DEFINITIONS


In this paper we generally follow (or at least adapt in an obvious way) the definitions and notation of <cit.> without further comment. In particular, digraphs are loopless, so digraph morphisms are unambiguously defined in terms of their action on vertices. Also, A indicates a set of arcs; the adjacency matrix corresponding to a colored/labeled digraph, directed multigraph, or weighted digraph D is μ_D. We assume that μ_D takes values in an appropriate commutative semiring, e.g., the Boolean semiring for digraphs. We use + and · to denote both ordinary arithmetic and generic semiring operations, while  denotes either logical disjunction or maximum depending on context; similarly,  denotes either logical conjunction or minimum.
[
Examples of semirings are the Boolean semiring ({0,1}, , ) for digraphs and the real semiring (ℝ, +, ·) for weighted digraphs. Other examples of potential relevance are the tropical semiring (ℝ∪∞, ∧, +) <cit.>, the fuzzy semiring ([0,1], ∨, ∧), the bottleneck semiring (ℝ, ∨ ,∧), the log semiring (ℝ∪∞, +_log, +) with x +_log y := -log(exp(-x)+exp(-y)), the Viterbi semiring ([0,1], ∨, ·), etc. For general background on semirings, see <cit.>. There is no truly standard definition of a semiring, and the same appears to be true of related notions. Rather than invoking necessarily idiosyncratic terminology to remove any ambiguity here, we (perhaps atypically) choose to rely on common sense. For instance, we will require a zero element to indicate the absence of arcs, but this need not be a neutral element for the additive operation. Thus, e.g., we can consider the restriction of the usual tropical semiring to [0,∞). 
]

For a digraph D = (V,A) and vertex coloring or labeling ℓ : V →Λ, write D(ℓ) := (ℓ,A) for the corresponding colored digraph, omitting the dependence on ℓ if the desire exists and context allows. Without loss of generality, we shall assume that V(D) = [n] ≡{1,…,n} for some n ∈ℕ.

As a shorthand, for U ⊆ V(D), we shall write D / U ≡ D / D ⟨ U ⟩ for the vertex contraction of U in D. That is, we set V(D / U) := (V(D) ∖ U) ∪{U} and for x,y ∈ V(D) ∖ U,

    μ_D / U(x,{U})     :=    ∑_u ∈ Uμ_D(x,u), 
    μ_D / U({U},x)     :=    ∑_u ∈ Uμ_D(u,x), 
    μ_D / U(x,y)     :=    μ_D(x,y).

Similarly, for disjoint subsets {U_j}_j ∈ [m] of V(D), D / {U_1,…,U_m} := (… (D / U_1)…) / U_m is well-defined.




§ VERTEX ABSTRACTION


A subset L = {L_j}_j ∈ [m]⊆Λ of colors determines a partial partition π_(ℓ,L) of [n] (i.e., a partition of a subset of [n]) as follows: the blocks π_(ℓ,L)^(j) of π_(ℓ,L) are simply the preimages ℓ^-1(L_j) for j ∈ [m]. Conversely, any partial partition of [n] is nonuniquely determined by some π_(ℓ,L), but we can choose a canonical representative for ℓ that makes the correspondence between colorings and partial partitions bijective.
[
Given ℓ, consider [ℓ] := { f : dom  f = [n] ∧π_(f,f[n]) = π_(ℓ,Λ)}. By construction, [ℓ] is the equivalence class of functions yielding the same partition of [n]. We can construct a canonical representative ℓ' of [ℓ] as follows: let ℓ' : [n] → [|ℓ([n])|] be such that minℓ'^-1(j) < minℓ'^-1(j+1) for j ∈ [|ℓ([n])|-1]. For example, if (using a standard notation for the Cartesian product of functions for brevity) ℓ^× 5(1,2,3,4,5) = (4,2,0,2,0), the corresponding canonical representative ℓ' is defined by ℓ'^× 5(1,2,3,4,5) = (1,2,3,2,3). This canonical representative is essentially the so-called restricted growth string corresponding to π_(ℓ,Λ) <cit.>.
] 
Henceforth we shall assume without loss of generality that ℓ is canonical (and so also surjective) unless otherwise specified.

As usual, let Π_n denote the lattice of partitions of [n]. Following <cit.>, we consider the lattice Π_≤ n of partial partitions ordered by refinement, i.e., for π, π' ∈Π_≤ n, we have π≤π' iff each block of π is contained in a block of π'. 
[
NB. The lattice Π_≤ n has a different partial order than the Dowling lattice Q_n(1) ≅Π_n+1 detailed in <cit.>: by way of comparison, in Q_n, π≤π' iff each block of π' is a union of blocks of π.
]
For economy of notation, we shall write |π| for the number of blocks of π∈Π_≤ n.
Define F_≤ n : Π_≤ n→Π_n+1 as follows: if σ = σ^(1) | … | σ^(|σ|)∈Π_≤ n and [n+1] ∖⋃_j=1^|σ|σ^(j) = {s_k}_k ∈ [r], then F_≤ n(σ) := σ^(1) | … | σ^(|σ|) | {s_1} | … | {s_r}. Similarly, define F_n+1 : Π_n+1→Π_≤ n as follows: if τ = τ^(1) | … | τ^(|τ|)∈Π_n+1 and n+1 ∈τ^(u_+), then F_n+1(τ) :=  τ^(1) | … | τ^(u_+)∖{n+1} | … | τ^(|τ|). An important aspect of the relationship between Π_≤ n and Π_n+1 is captured by the following 


Proposition. The pair (F_≤ n, F_n+1) is a (monotone) Galois connection. 


Define the support supp π of π∈Π_≤ n as the union of its blocks. Because supp π_(ℓ,L) = ℓ^-1(L), the induced colored digraph D ⟨supp π_(ℓ,L)⟩ is well-defined and π_(ℓ,L) = π_(ℓ,L)^(1) | … | π_(ℓ,L)^(|π_(ℓ,L)|) determines a colored digraph via

    D_⟨ℓ,L ⟩ := D ⟨supp π_(ℓ,L)⟩ / {π_(ℓ,L)^(1), …, π_(ℓ,L)^(|π_(ℓ,L)|)}.

The intuition behind (<ref>) is simply that vertices in the jth block π_(ℓ,L)^(j) are identified (note that the order in which these identifications take place is immaterial, and that the resulting coloring will generally not be canonical).


Definition. Call D_⟨ℓ,L ⟩ the vertex abstraction of D with respect to L.


Example. Consider the following colored digraph D: 


	[scale=1.25,->,>=stealth',shorten >=1pt]
		[draw,circle,minimum size=5mm] (v01) at (0,0) 1;
		[draw,circle,minimum size=5mm] (v02) at (1,0) 2;
		[draw,circle,minimum size=5mm] (v03) at (2,0) 1;
		[draw,circle,minimum size=5mm] (v04) at (3,0) 3;
		/→in 
			v01/v02, v02/v03, v03/v04
			() to (→);
	


We have the following table:



	1.5
	
		L     ∅     {1}     {2}     {3}     {1,2}     {1,3}     {2,3}     {1,2,3}
		
 D_⟨ℓ,L ⟩    
			     
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,color=white,circle,minimum size=5mm] (v00) at (0,0.2) ;	
				[draw,circle,minimum size=5mm] (v01) at (0,0) 1;
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v02) at (1,0) 2;
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v03) at (2,0) 3;
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v01) at (0,0) 1;
				[draw,circle,minimum size=5mm] (v02) at (1,0) 2;
				/→in 
					v01/v02, v02/v01
					() to (→);
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v01) at (0,0) 1;
				[draw,circle,minimum size=5mm] (v04) at (1,0) 3;
				/→in 
					v01/v04
					() to (→);
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v02) at (0,0) 2;
				[draw,circle,minimum size=5mm] (v04) at (1,0) 3;
			    
			[scale=1.25,->,>=stealth',shorten >=1pt]
				[draw,circle,minimum size=5mm] (v02) at (0,0) 2;
				[draw,circle,minimum size=5mm] (v01) at (1,0) 1;
				[draw,circle,minimum size=5mm] (v03) at (2,0) 3;
				/→in 
					v01/v02, v02/v01, v01/v03
					() to (→);
			
		
  
	
 

It is easy to see that the map π_(ℓ,·) : 2^Λ→Π_≤ n on the subset lattice 2^Λ is monotone, i.e., if L ⊆ L', then π_(ℓ,L)≤π_(ℓ,L'). Furthermore, there is a surjective morphism χ_ℓ,L',L : D_⟨ℓ,L ⟩→ D_⟨ℓ,L' ⟩ of colored digraphs defined by contracting the preimages of each element of L' ∖ L, and χ_ℓ,L”,L'∘χ_ℓ,L',L = χ_ℓ,L”,L. This and some definition-checking yields the following


Lemma. When endowed with the obvious refinement morphisms and the χ_ℓ,·,·, respectively, {π_(ℓ,L)}_L ⊆Λ and {D_⟨ℓ,L ⟩}_L ⊆Λ are both categories. Furthermore, π_(ℓ,·) : 2^Λ→{π_(ℓ,L)}_L ⊆Λ and D : {π_(ℓ,L)}_L ⊆Λ→{D_⟨ℓ,L ⟩}_L ⊆Λ are both functors that yield equivalences of categories. 


In particular, the lattice structure of 2^Λ is duplicated in {π_(ℓ,L)}_L ⊆Λ and (since we are considering colored digraphs) {D_⟨ℓ,L ⟩}_L ⊆Λ. Another noteworthy consequence of this lemma is that the pullback and pushout squares for set inclusions have analogues for partial partitions and vertex abstractions. For example,


Proposition. Let L_1, L_2 ⊆ L. The pullback of χ_ℓ,L,L_1 and χ_ℓ,L,L_2 is given by χ_ℓ,L_1,L_1 ∩ L_2 and χ_ℓ,L_2,L_1 ∩ L_2. 




§ DETOURS, BYPASSES, AND PATH ABSTRACTIONS


For v ∈ V(D), define

    V(D)_v^-     :=    { x ∈ V(D) ∖{v} : μ_D(x,v)  0 ∧μ_D(v,x) = 0 }; 
    
    V(D)_v^±    :=    { x ∈ V(D) ∖{v} : μ_D(x,v)  0 ∧μ_D(v,x)  0 }; 
    
    V(D)_v^+     :=    { x ∈ V(D) ∖{v} : μ_D(x,v) = 0 ∧μ_D(v,x)  0 }; 
    
    V(D)_v^0     :=    { x ∈ V(D) ∖{v} : μ_D(x,v) = 0 ∧μ_D(v,x) = 0 },

noting that {{v}, V(D)_v^-, V(D)_v^±, V(D)_v^+, V(D)_v^0 } forms a partition of V(D). In particular, P(D)_v := V(D)_v^- ∪ V(D)_v^± is the set of predecessors of v, S(D)_v := V(D)_v^±∪ V(D)_v^+ is the set of successors of v, and P(D)_v ∩ S(D)_v = V(D)_v^±. (See figure <ref>.)



Define the detour at v by D ↑ v by V(D ↑ v) := V(D) and

    μ_D ↑ v(x,y) := 
    
    0     if  (x,y) ∈ [P(D)_v ×{v}] ∪ [{v}× S(D)_v]; 
    
    1     if  (x,y) ∈ [P(D)_v × S(D)_v] ∖Δ(V(D)); 
    μ_D(x,y)     otherwise.

(Here as usual Δ denotes the diagonal functor.) That is, the detour at v is formed by deleting all arcs involving v and inserting arcs from every predecessor of v to every distinct successor of v. Finally, define the bypass at v by D ⇈ v := (D ↑ v) - v. (See figure <ref>.) By construction we have the following


Proposition. If u, v, and w are distinct elements of V(D) and there is a path in D from u to w, then there are also paths in both D ↑ v and D ⇈ v from u to w. 


Lemma. If D ⇈ v is strongly connected and P(D)_v, S(D)_v ∅, then D is strongly connected. 


Proof. Let x,y ∈ [n] ∖{v} and let γ(x,y) be a path in D ⇈ v from x to y. If γ(x,y) does not contain an arc of the form (u,w) for some u ∈ P(D)_v and w ∈ S(D)_v, then it lifts to a path from x to y in D, so assume otherwise. Now γ(x,y) is a concatenation of paths of the form γ(x,u) γ(u,w) γ(w,y), which corresponds to a path concatenation of the form γ(x,u) γ(u,v) γ(v,w) γ(w,y) in D. 


It is easy to see that D ↑ v and D ⇈ v both contain a complete digraph with vertex set V(D)_v^±: thus if this set has more than a single element, the detour and bypass are necessarily cyclic, and their transitive reductions may not be unique. Similarly, there are cases where D ↑ v has multiple Hamilton cycles (which are also transitive reductions). Therefore in general there is no unique minimal digraph with the path preservation property of the preceding proposition. On the other hand, we have the following


Proposition. If D is acyclic (so that in particular V(D)_v^±≡∅), then so are D ↑ v and D ⇈ v. Furthermore, in this event the transitive reductions of D ↑ v and D ⇈ v are the unique minimal digraphs on the respective vertex sets V(D) and V(D) ∖{v} such that if u, v, and w are distinct elements of V(D) and there is a path in D from u to w, then there are also paths in both D ↑ v and D ⇈ v from u to w. 


There are cases where D ↑ v and D ⇈ v are their own transitive reductions: e.g., consider a digraph D with only the three arcs (u,v), (v,w), and (u,w): the only arc in D ↑ v is (u,w). With this in mind, there is a sense in which the detour and bypass can be considered optimal (though typically not minimal) constructions with respect to path preservation in generic digraphs.


Lemma. (D ↑ v) ↑ w = (D ↑ w) ↑ v.


Proof. See <ref> for a naive case analysis. We will prove a more general result in <ref> in a much more elegant and concise manner. 


Theorem. For U = {u_j}_j ∈ [m]⊆ V(D) the obvious generalizations of detour D ↑ U := ( … (D ↑ u_1) …↑ u_m-1) ↑ u_m and bypass D ⇈ U := (D ↑ U) - U are well-defined. 


Surprisingly, the only reference we could find that even suggests the detour/bypass constructions is <cit.>, which seems to take the preceding theorem for granted.

Note that the construction of D ↑ U is not so simple as removing all arcs involving a vertex in U, then inserting arcs from every external predecessor of a vertex in U to every distinct external successor of a vertex in U. For example, consider D given by the path of length 3, i.e. D =
	[scale=.5,->,>=stealth',shorten >=1pt]
		 (v1) at (1,0);
		 (v2) at (2,0);
		 (v3) at (3,0);
		 (v4) at (4,0);
		 (v1) [out=30,in=150,looseness=1] to (v2);
		 (v2) [out=30,in=150,looseness=1] to (v3);
		 (v3) [out=30,in=150,looseness=1] to (v4);
and U the set whose members are the source and target vertices of D. Then D ⇈ U = 
	[scale=.5,->,>=stealth',shorten >=1pt]
		 (v2) at (2,0);
		 (v3) at (3,0);
		 (v2) [out=30,in=150,looseness=1] to (v3);
while the naive procedure mentioned just above yields [scale=.5,->,>=stealth',shorten >=1pt]
		 (v2) at (2,0);
		 (v3) at (3,0);
		 (v2) [out=30,in=150,looseness=1] to (v3);
		 (v3) [out=-150,in=-30,looseness=1] to (v2);. Another example is shown in figure <ref>.




Corollary. If U ⊆ V(D) and D is acyclic, then so are D ↑ U and D ⇈ U. Furthermore, in this event the transitive reductions of D ↑ U and D ⇈ U are the unique minimal digraphs on the respective vertex sets V(D) and V(D) ∖ U such that if v,w ∈ V(D) ∖ U are distinct and there is a path in D from v to w, then there are also paths in both D ↑ U and D ⇈ U from v to w. 


Recall that for a directed pseudograph or quiver Q, the free category F(Q) is the category with objects given by vertices of Q and morphisms given by paths in Q, with composition given by path concatenation.


Proposition. For U ⊆ V(D), there is a functor F(D) → F(D ↑ U) defined on objects as the identity map and on morphisms as the map which deletes elements of U from paths. 
[
As suggested in <ref>, one might consider using this proposition as the foundation of the ⇈ operator: i.e., given a language ℒ over [n] whose elements correspond to paths in some digraph D, define ℒ⇈ U to be the language over [n] ∖ U obtained by deleting all symbols in U from elements of ℒ. However, it is not obvious from this essentially automata-theoretical persepective that the elements of ℒ⇈ U themselves correspond to paths in some (here) notional digraph D ⇈ U. It seems that a path coherence result of the type needed to establish such a fact would be tantamount to the preceding theorem.
]


Example. The digraphs D and D ⇈{5,7} depicted in figure <ref> are DAGs. A quick calculation shows that each has 7 paths from a source to a target: the correspondence between them is shown in the table below.


	
		path in D     corresponding path in D ⇈{5,7}
		
 3 → 5 → 2     3 → 2 

		3 → 5 → 1 → 7 → 2     3 → 1 → 2 

		3 → 5 → 1 → 4 → 7 → 2     3 → 1 → 4 → 2 

		3 → 8     3 → 8 

		3 → 5 → 6 → 8     3 → 6 → 8 

		3 → 5 → 1 → 7 → 8     3 → 1 → 8 

		3 → 5 → 1 → 4 → 7 → 8     3 → 1 → 4 → 8 

		 
	
 


Example. Consider the digraph D in figure <ref>. There are four interesting cycles: 1 → 3 → 1 ≡ 131 (omitting arrows for concision), 1231, 1341, and 12341. These are respectively mapped under ⇈ 3 to 1 (not a cycle!), 121, 141, and 1241. Subsequently contracting vertices 2 and 4 à la (<ref>) maps the remaining cycles in turn to the single cycle 121. This extends to a mapping on all paths, e.g. the path 1231341234 maps under ⇈ 3 to 1214124 and subsequently under the contraction of vertices 2 and 4 to 121212. 




From the proposition we see that for L ⊆ L' there is a surjective morphism ϕ_ℓ,L,L' : F(D ↑ℓ^-1(L)) → F(D ↑ℓ^-1(L')) defined by sending vertices of D to themselves and deleting elements of L' ∖ L from paths. Therefore we get the following 


Lemma. When endowed with the morphisms ϕ_ℓ,·,·, {F(D ↑ℓ^-1(L))}_L ⊆Λ is a category and the map F_D,ℓ : L ↦ F(D ↑ℓ^-1(L)) is a functor yielding an equivalence of categories. 


We close this section by showing that detour/bypass and contraction operations on disjoint vertex sets commute.


Lemma. If u, v, w ∈ V(D) are distinct, then (D ↑ u) / {v,w} = (D/{v,w}) ↑ u.


Proof. See <ref> for a naive case analysis. We will prove a more general result in <ref> in a much more elegant and concise manner. 



Theorem. The detour and bypass operations commute with disjoint graph contractions: if U, V_1, …, V_m ⊆ V(D) are disjoint, then (D ↑ U) / {V_1,…,V_m} = (D / {V_1,…,V_m}) ↑ U, and similarly for bypasses. 


Thus we can freely make the following


Definition. The path abstraction of D with respect to π∈Π_≤ |V(D)| is 

    D ⇈π := (D ⇈ (V(D) ∖supp π)) / {π^(1),…,π^(|π|)} = (D / {π^(1),…,π^(|π|)}) ⇈ (V(D) ∖supp π).

We shall write D ⇈ (ℓ,L) := D ⇈π_(ℓ,L).


Unfortunately, for L ⊆ L' there is not a simple relationship between D ⇈ (ℓ, L) and D ⇈ (ℓ, L'). To see this, let L ⊂Λ, let ℓ_0 ∈Λ∖ L, and let L' := L ∪{ℓ_0}. If π_(ℓ,L) = π_(ℓ,L)^(1) | … | π_(ℓ,L)^(|π_(ℓ,L)|) and π_(ℓ,L') = π_(ℓ,L')^(1) | … | π_(ℓ,L')^(|π_(ℓ,L')|) = π_(ℓ,L)^(1) | … | π_(ℓ,L)^(|π_(ℓ,L)|) | π_(ℓ,L')^(|π_(ℓ,L)|+1), defining π_(ℓ,L')^(0) := V(D) ∖⋃_j ∈ [|π_(ℓ,L)|+1]π_(ℓ,L')^(j) yields a partition {π_(ℓ,L')^(j)}_j = 0^|π_(ℓ,L)|+1 of V(D), and it is readily seen that D ⇈ (ℓ, L) = ((D ⇈π_(ℓ,L)^(0)) / {π_(ℓ,L)^(1),…,π_(ℓ,L)^(|π_(ℓ,L)|)}) ⇈π_(ℓ,L')^(|π_(ℓ,L)|+1) while D ⇈ (ℓ,L') = ((D ⇈π_(ℓ,L)^(0)) / {π_(ℓ,L)^(1),…,π_(ℓ,L)^(|π_(ℓ,L)|)}) ∖π_(ℓ,L')^(|π_(ℓ,L)|+1). That is, the essential distinction between D ⇈ (ℓ,L) and D ⇈ (ℓ,L') is that the former has a bypass while the latter has a contraction. These two operations are typically not readily comparable, and so we defer the quest for a structure theory of path abstractions. 




§ WEIGHTED DIGRAPHS


Generalizing the constructions of <ref> to weighted digraphs introduces some subtleties. However, it also leads to simpler proofs.

As a preliminary step, consider the case of directed multigraphs. For a directed multigraph D, there is a unique minimal subdivision D^⊘ of D that is a digraph. Thus for v ∈ V(D), D^⊘↑ v is well-defined. For x,y ∈ V(D), write ν_D(x,y) for the number of walks in D from x to y, so that ν_D(x,y) < ∞ iff x and y are not in the same strong component of D (of course, this is automatically the case if D is acyclic [which also implies that D^⊘ and D^⊘↑ v are acyclic]). For x,y ∈ V(D), it is clear that ν_D(x,y) = ν_D^⊘(x,y), and moreover that any reasonable definition of D ↑ v should satisfy ν_D^⊘↑ v(x,y) = ν_D ↑ v(x,y). Meanwhile, note that (<ref>) is equivalent to

    μ_D ↑ v(x,y) = 
    
    0     if  (x,y) ∈ [V(D) ×{v}] ∪ [{v}× V(D)] ∪Δ(V(D)); 
    μ_D(x,y) ∨ (μ_D(x,v) ∧μ_D(v,y))     otherwise.


These considerations indicate that for directed multigraphs, we should simply replace ∨ with + and ∧ with · à la

    μ_D ↑ v(x,y) :=
    
    0     if  (x,y) ∈ [V(D) ×{v}] ∪ [{v}× V(D)] ∪Δ(V(D)); 
    μ_D(x,y) + μ_D(x,v) ·μ_D(v,y)     otherwise.

To generalize further from directed multigraphs to weighted digraphs, the addition and multipication operations above can be taken to be those of a commutative semiring that the weights are presumed to inhabit, and μ_D can be taken to indicate the weights (or for the further generalization of a weighted directed multigraph, the appropriate sum of weights). However, while the RHS of (<ref>) is always well-defined, in many circumstances it leads to behavior that is more troublesome than for the special case of unweighted digraphs. 

For convenience, we shall write, e.g., μ_xy := μ_D(x,y) in the rest of this section.


Theorem. (D ↑ v) ↑ w  (D ↑ w) ↑ v iff μ_vwμ_wv 0 and there exists (x,y) ∈ V(D)^2 ∖ ([V(D) ×{v,w}] ∪ [{v,w}× V(D)] ∪Δ(V(D))) such that μ_xvμ_vyμ_xwμ_wy. 


Proof. We have that

    μ_(D ↑ v) ↑ w(x,y) :=
    
    0     if  (x,y) ∈ [V(D) ×{v,w}] ∪ [{v,w}× V(D)] ∪Δ(V(D)); 
    μ_D ↑ v(x,y) + μ_D ↑ v(x,w) ·μ_D ↑ v(w,y)     otherwise.

Applying (<ref>) twice shows that the nonzero entries of μ_(D ↑ v) ↑ w(x,y) are of the form

    μ_xy + μ_xvμ_vy + μ_xwμ_wy + μ_xvμ_vwμ_wy + μ_xwμ_wvμ_vy + μ_xvμ_vwμ_wvμ_vy.

The expression above is not symmetric under the exchange of v and w owing purely to the last term (note that in the special case of digraphs addressed in <ref>, the concomitant Boolean semiring operations recover this lost symmetry as required since the last term is nonzero only if the second term is also). The conditions under which there exist x,y such that x  y and μ_xvμ_vwμ_wvμ_vyμ_xwμ_wvμ_vwμ_wy are stated in the theorem. 


Example. Consider the multigraph D shown in figure <ref>. With v = 1 and w = 4, the terms μ_xvμ_vwμ_wvμ_vy and μ_xwμ_wvμ_vwμ_wy respectively correspond to the matrices

    [ 0; 0; 2; 1 ]·[ 1 ]·[ 1 ]·[ 0 1 0 1 ]
    =
    [ 0 0 0 0; 0 0 0 0; 0 2 0 2; 0 1 0 1 ]  and  [ 1; 0; 0; 0 ]·[ 1 ]·[ 1 ]·[ 1 0 0 0 ]
    =
    [ 1 0 0 0; 0 0 0 0; 0 0 0 0; 0 0 0 0 ].

These have entries in V(D)^2 ∖ ([V(D) ×{v,w}] ∪ [{v,w}× V(D)] ∪Δ(V(D))) = {(2,3),(3,2)} that differ. 




Corollary. If D is acyclic and U ⊆ V(D), then D ↑ U is well-defined and acyclic. 


There may be situations of practical interest in which D is not acyclic, which necessarily complicates any criterion for establishing the existence of a well-defined detour/bypass. We proceed below to establish the most obvious criterion in this vein.


Lemma. If D has no 2-cycles at all and no 3-cycles intersecting v, then D ↑ v has no 2-cycles.


Proof. Suppose that μ_D ↑ v(x,y) ·μ_D ↑ v(y,x)  0. By hypothesis, μ_xyμ_yx = 0, so without loss of generality assume that μ_xy = 0. Now 

    μ_D ↑ v(x,y) ·μ_D ↑ v(y,x) = μ_xvμ_vy (μ_yx + μ_yvμ_vx)  0.

In particular, μ_xv 0 μ_vy. 

If μ_yx = 0, then we must have that μ_xvμ_vx 0 μ_vyμ_yv, contradicting the assumption that D has no 2-cycles. If on the other hand μ_yx 0, then either μ_yvμ_vx = 0 or μ_yvμ_vx 0. In the first case, μ_xvμ_vyμ_yx 0, contradicting the assumption that D has no 3-cycles intersecting v. In the second case, we again contradict the assumption that D has no 2-cycles. Thus it must be that μ_D ↑ v(x,y) ·μ_D ↑ v(y,x) = 0, i.e., D ↑ v has no 2-cycles. 


While it is tempting to spend the effort to recast the preceding lemma as the base case of an induction, the complexity of finding short cycles in digraphs suggests that any theorem actually resulting from such an exercise would be less useful in practice than simply checking online whether or not successive detours commute. For this reason we elect to move on to the following more useful result:


Theorem. If u, v, w ∈ V(D) are distinct, then (D ↑ u) / {v,w} = (D/{v,w}) ↑ u.


Proof. Write X := V(D) ∖{u,v,w}, so that μ_D takes the form

    μ_D     u     v     w     X 
    	u     0    μ_uv   μ_uw   μ_uX
    	v    μ_vu    0    μ_vw   μ_vX
    	w    μ_wu   μ_wv    0    μ_wX
    	X    μ_Xu   μ_Xv   μ_Xw   μ_XX.

For a generic square matrix M and n-tuple z, let d(M)_j := M_jj and d(z)_jk := z_j δ_jk, i.e., d is the obvious notion of a diagonal map in both cases. Define M^ := M - d(d(M)). We then have that μ_D ↑ u and μ_D / {v,w} are respectively

    μ_D ↑ u    u     v     w     X 
    	u     0     0     0     0 
    	v     0     0    μ_vw + μ_vuμ_uw   μ_vX + μ_vuμ_uX
    	w     0    μ_wv + μ_wuμ_uv    0    μ_wX + μ_wuμ_uX
    	X     0    μ_Xv + μ_Xuμ_uv   μ_Xw + μ_Xuμ_uw   μ_XX + (μ_Xuμ_uX)^;


    μ_D / {v,w}    u     vw     X 
    	u     0    μ_uv + μ_uw   μ_uX
    	vw    μ_vu + μ_wu    0    μ_vX + μ_wX
    	X    μ_Xu   μ_Xv + μ_Xw   μ_XX.


Consequently, μ_(D ↑ u) ∖{v,w} and μ_(D / {v,w}) ↑ u are respectively

    μ_(D ↑ u) ∖{v,w}    u     vw     X 
    	u     0     0     0 
    	vw     0     0    μ_vX + μ_vuμ_uX + μ_wX + μ_wuμ_uX
    	X     0    μ_Xv + μ_Xuμ_uv + μ_Xw + μ_Xuμ_uw   μ_XX + (μ_Xuμ_uX)^;


    μ_(D / {v,w}) ↑ u    u     vw     X 
    	u     0     0     0 
    	vw     0     0    μ_vX + μ_wX + (μ_vu + μ_wu) μ_uX
    	X     0    μ_Xv + μ_Xw + μ_Xu (μ_uv + μ_uw)    μ_XX + (μ_Xuμ_uX)^.

These are obviously equal. 


Corollary. If D is acyclic, then its path abstraction is well-defined. 




§ RANDOM DIGRAPHS


For 0 ≤ p ≤ 1, let D_n,p denote the random digraph <cit.> with V(D_n,p) = [n] and independent probabilities ℙ(μ_D_n,p(x,y) = 1 | x  y) ≡ p. 

Let u ∈ [n]. According to (<ref>), there are two ways for the event μ_D_n,p⇈ u(x,y) = 1 to occur for x  y: either (x,y) ∈ P(D_n,p)_u × S(D_n,p)_u, or (x,y) ∉ P(D_n,p)_u × S(D_n,p)_u but μ_D_n,p(x,y) = 1. These two subevents are disjoint, with the probability of the former equal to p^2 and the probability of the latter equal to (1-p^2)p, so we have that ℙ ( μ_D_n,p⇈ u(x,y) = 1 | x  y  ) = p^2 + (1-p^2)p =: f(p). It follows for that for U ⊆ [n]

    ℙ ( μ_D_n,p⇈ U(x,y) = 1 | x  y  ) = f^∘ |U|(p),

where a |U|-fold composition is indicated on the RHS (see figure <ref>). That is, 

    D_n,p⇈ U = D_n-|U|,f^∘ |U|(p).

This suggests the possibility of a renormalization group strategy for studying D_n,p (and percolation thresholds in particular), but we limit our discussion of this to a terse remark in <ref>.

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

 

A qualitative approximation for f^∘ N(p) is readily obtained by the following tactic described in <cit.>: temporarily writing p(N) := f^∘ N(p), we have that p(N+1)-p(N) = p^2(N) - p^3(N). Treating N as a continuous parameter yields the approximation dp/dN≈ p^2-p^3. Writing F(p) := logp/1-p - 1/p and noting that dF/dp = 1/p^2-p^3 yields that 

    f^∘ N(p) ≈ F^-1(N+F(p)).
 
A sophisticated but interesting restatement of (<ref>) is that F is approximately equivariant with respect to the ℤ-actions on [0,1] and ℝ given respectively by iterating f and adding.
[
The approximate ℤ-equivariance expressed in (<ref>) obviously generalizes to other functions f and F such that F'(p) = (f(p)-p)^-1. However, we are not aware of results corresponding to this fact or its further generalization to higher-order differences.
]












Meanwhile, the event μ_D_n,p/U(x,{U}) = 1 occurs for x {U} iff there is some u ∈ U such that μ_D_n,p(x,u) = 1. Equivalently, the event μ_D_n,p/U(x,{U}) = 0 occurs iff μ_D_n,p(x,u) = 0 for all u ∈ U, and this event clearly has probability (1-p)^|U|. Thus 

    ℙ ( μ_D_n,p/U(x,{U}) = 1 | x {U} ) = 1 - (1-p)^|U|.

More generally, if π∈Π_n, then 

    ℙ ( μ_D_n,p/{π^(1),…,π^(|π|)}({π^(j)},{π^(k)}) = 1 | j  k  ) = 1 - (1-p)^|π^(j)| · |π^(k)|.


We can combine the preceding observations into the following

 

Theorem. If π∈Π_≤ n, then

    ℙ ( μ_D_n,p⇈π({π^(j)},{π^(k)}) = 1 | j  k  ) = 
    1 -  ( 1-f^∘ (n-|supp π|)(p)  )^|π^(j)| · |π^(k)|.

In particular, the expected number of arcs in D_n,p⇈π is the sum over j  k of the RHS of (<ref>) (note that the number of vertices is just |π|). 


	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	



	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	



Example. Let n = 28 and p = 0.05, and suppose that the graph D in figure <ref> is a realization of D_n,p. (Note that D has |A(D)| = ∑_x,yμ_D(x,y) = 40 arcs and hence |A(D)|/n(n-1)≈ 0.0529 ≈ p. Furthermore, 12 vertices have indegree 2 and the rest have indegree 1; similarly, 12 vertices have outdegree 2 and the rest have outdegree 1, so D_n,p is at least superficially appropriate here as a model for D.) The partial partition π corresponding to the path abstraction in figure <ref> has n - |supp π| = 4, f^4(p) ≈ 0.0578, and (|π^(1)|,…,|π^(|π|)|) = (4,3,2,2,1,2,1,2,2,3,2). The expected number of arcs in D_n,p⇈π turns out to be approximately 25.9635, whereas the actual number of arcs in D ⇈π is 27. (Taking instead the value p = 0.0529 yields an expected number of arcs approximately equal to 27.4466.) 


Example. Let n = 1000, p = 0.01, and consider U a uniformly random subset of [n] subject to |U| = 50. Figure <ref> demonstrates (<ref>) using the estimate p̂ = |A(D_n,p)|/n(n-1) for 1000 realizations of D_n,p⇈ U. 


 

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

Example. As an example for which D_n,p is a manifestly inappropriate model, consider the digraph D' with vertices corresponding to airports and arcs corresponding to regularly scheduled passenger flights. We constructed this digraph using data accessed from  on 3 May 2016, yielding n' := |V(D')| = 8107 and |A(D')| = 37187 arcs, corresponding to an empirical arc probability of p' := |A(D)|/n(n-1)≈ 5.6588 · 10^-4. We define ℓ' : V(D') →Λ' to be the map coloring airports by country, so that |Λ'| = 240. The in- and out-degrees are very far from uniform, as illustrated in figure <ref>.
 
Evidently D_n',p' is a very poor model for D'. If π' is the partial partition corresponding to country colors excluding the United States, then |A(D' ⇈π')| = 11036, whereas 𝔼(|A(D_n',p'⇈π')|) ≈ 5125. 


In order to get better approximations in such situations it would be necessary to consider a more general random digraph, e.g. the one introduced in <cit.> (ignoring loops). However, the proof of the preceding theorem exploited the commutativity of contracting and bypassing vertices in an essential way that does not generalize to the random digraph of <cit.>. For this reason, obtaining a suitable generalization of the theorem appears to require substantially more effort. Furthermore, applying the resulting theorem would appear to require the same sort of set-theoretic operations as actually constructing the path abstraction outright, largely negating its utility as a predictive tool.




§ TEMPORAL NETWORKS


Digraphs admit a natural temporal generalization called directed temporal contact networks (DTCNs). <cit.> A DTCN with vertex set V ≡ [n] is a pair (𝒟,δ) where 𝒟 is a finite nonempty set and δ : 𝒟→ (V^2 ∖Δ(V)) ×ℝ is injective. The source, target, and time maps (respectively denoted s, t, and τ) are defined so that the following diagram commutes:


	[->,>=stealth',shorten >=1pt]
		(v01) at (0,0) 𝒟;
		(v02) at (0,-4) V^2;
		(v03) at (2,-2) (V^2 ∖Δ(V)) ×ℝ;
		(v04) at (4,0) ℝ;
		(v05) at (4,-4) V^2 ×ℝ;
		
		[->] (v01) edge node [left] s × t (v02);
		[->] (v01) edge node [above] δ (v03);
		[->] (v01) edge node [above] τ (v04);
		[right hook->] (v03) edge node [above] i (v05);
		[->] (v05) edge node [below] (π_1 ∘π_1) × (π_2 ∘π_1) (v02);
		[->] (v05) edge node [right] π_2 (v04);
	


That is, each contact c ∈𝒟 corresponds to a unique triple (s(c),t(c),τ(c)), and when convenient we identify contacts and their corresponding triples. We may economically indicate the DTCN (𝒟,δ) merely as 𝒟 or δ; context should suffice to remove any potential for ambiguity here. There is an obvious notion of a temporally coherent path which we do not bother to write out formally. 

A naive attempt to generalize the constructions of <ref> to DTCNs might define 𝒟↑ v ≡𝒟⇈ v as

    {c ∈𝒟: s(c)  v  t(c)}∪{ (j,k,τ_vk) : (j,v,τ_jv), (v,k,τ_vk) ∈𝒟τ_jv≤τ_vk j  k }.

However, such a definition yields undesirable behavior, as we show in the following 


Example. Consider the DTCN 𝒟 := {(1,4,τ_1), (5,4,τ_2), (2,5,τ_3), (4,3,τ_4)} with τ_1 < τ_2 < τ_3 < τ_4. Using the naive definition (<ref>) for 𝒟↑ v leads to (𝒟↑ 4) ↑ 5 = {(1,3,τ_4),(2,3,τ_4)} (𝒟↑ 5) ↑ 4 = {(1,3,τ_4)}. As figure <ref> illustrates, only the latter corresponds to the desirable result for 𝒟↑{4,5}. 




An approach that manifestly yields the desired construction deals with the temporal digraph of 𝒟 (see figure <ref> for an example), defined as the digraph T(𝒟) with vertex and arc sets

    V(T(𝒟))     :=    {(v, -∞) : v ∈ V}∪{(v,τ(c)) : (v,c) ∈ V ×𝒟 (s(c) = v  t(c) = v) }∪{(v, ∞) : v ∈ V}
    
    A(T(𝒟))     :=    {((s(c),τ(c)),(t(c),τ(c))) : c ∈𝒟}∪{ ((v,τ_j-1^@v),(v,τ_j^@v)) : v ∈ V, j ∈ [|𝒟@v|-1] }
 
where the temporal fiber at v is

    𝒟@v := {-∞}∪{τ(c) : c ∈𝒟 s(c) = v }∪{τ(c) : c ∈𝒟 t(c) = v }∪{∞}≡{τ_j^@v}_j = 0^|𝒟@v|-1.

Note that |V(T(𝒟))| = ∑_v |𝒟@v| ≤ 2|V| + 2|𝒟| and |A(T(𝒟))| = |V(T(𝒟))| - |V| + |𝒟| ≤ |V| + 3 |𝒟|, so that the temporal digraph of a DTCN can be formed with only linear overhead. 

Call the two sets in the union on the RHS of (<ref>) the spatial and temporal arcs of T(𝒟), respectively. Now for U ⊆ V, consider

    T(𝒟) ⇈⋃_u ∈ U ( {u}×𝒟@u  ).

Each of the non-temporal arcs in this digraph is of the form ((v,τ_j^@v),(v',τ_j'^@v')) for v  v' and corresponds to a triple (v,v',τ_j^@vτ_j'^@v'). The set of all such triples defines 𝒟↑ U ≡𝒟⇈ U. That is,

    𝒟↑ U ≡𝒟⇈ U := { (v,v',τ_j^@vτ_j'^@v') : v  v'  ((v,τ_j^@v),(v',τ_j'^@v')) ∈ A  ( T(𝒟) ⇈⋃_u ∈ U ( {u}×𝒟@u  )  ) }.



Proposition. If τ is a constant map, then 𝒟↑ U can be identified with D ↑ U, where here D indicates the obvious digraph corresponding to 𝒟. 


	
	
	
	
	
	
	
	

Example. Again, consider the DTCN 𝒟 := {(1,4,τ_1), (5,4,τ_2), (2,5,τ_3), (4,3,τ_4)} with τ_1 < τ_2 < τ_3 < τ_4. Using (<ref>) yields 𝒟↑{4,5} = {(1,3,τ_4)}, as desired. However, it is still the case that (𝒟↑{4}) ↑{5} = {(1,3,τ_4),(2,3,τ_4)} (𝒟↑{5}) ↑{4} = {(1,3,τ_4)}, just as before. 


The preceding examples show that although (<ref>) is certainly a reasonable definition for 𝒟↑ U, any reasonable definition of detours/bypasses for DTCNs will lead to noncommutativity that is not present for digraphs. However, there is still a well-defined notion of path abstraction for DTCNs (which necessarily will not commute with successive detours/bypasses) due to the following


Lemma. Detours/bypasses commute with vertex contractions for DTCNs.


Sketch of proof. Let U ∩{v,w} = ∅ and U ∪{v,w}⊆ V. The vertex contraction 𝒟 / {v,w} is defined in the obvious way: triples of the form (v,x,τ_vx) and (x,v,τ_xv) for x ∉{v,w} are replaced with ({v,w},x,τ_vx) and (x,{v,w},τ_xv), respectively, and similarly for triples involving w. Thus (𝒟 / {v,w})@{v,w} = (𝒟@v) ∪ (𝒟@w), so additional vertices and temporal arcs are generated in the formation of T(𝒟 / {v,w}). However, in the formation of T(𝒟), replacing both of the  temporal fibers 𝒟@v and 𝒟@w with (𝒟 / {v,w})@{v,w} has no material effect on the subsequent formation of 𝒟↑ U. The lemma now reduces to the already established version for digraphs by contracting vertices with the same time coordinate in each copy of (𝒟 / {v,w})@{v,w}. 


The surprising noncommutativity of detours/bypasses for DTCNs is not the only difference from the situation for digraphs.


Example. There are at least two random DTCNs that are obvious analogues of D_n,p (cf. <ref>): 


  * 𝒟_n,p^(u), with sources and targets corresponding to D_n,p and times uniformly random in [0,1];

  * 𝒟_n,p^(P), with contacts between x  y Poisson distributed over [0,1] with rate p. That is, the probability of a contact between x  y in an interval of infinitesmal duration d τ is given by p · d τ.

It is easy to see that both of these have an expected number of contacts equal to p · n (n-1). Furthermore, for the regime of interest p ≪ 1, these two random DTCNs can be expected to behave quite similarly, akin to the Erdős-Rényi and Gilbert random graphs.

Rather than attempting to develop analytical results, we proceed directly to numerics. The basic observation from figure <ref> is that the number of contacts in 𝒟_n,p^(·)↑ U is much less than the number of arcs in D_n,p↑ U, because there are fewer temporally coherent paths between two vertices in 𝒟_n,p^(·) than there are ordinary paths between the same two vertices in D_n,p. In particular, given {x_j}_j = 0^ℓ, the probability that the path x_0 →…→ x_ℓ exists in D_n,p is p^ℓ, whereas the probability that a temporally coherent version of the same path exists in 𝒟_n,p^(·) is p^ℓ/ℓ!


 

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	



The author is grateful to Mukesh Dalal for proposing the idea of the paper, and to Yingbo Song for patiently allowing it to unfold. This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) and the Air Force Research Laboratory (AFRL). Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA or AFRL.






§ CASE ANALYSIS PROOF OF (D ↑ V) ↑ W = (D ↑ W) ↑ V FOR DIGRAPHS


There are five cases: 1) w = v; 2) w ∈ V(D)_v^-; 3) w ∈ V(D)_v^±; 4) w ∈ V(D)_v^+, and 5) w ∈ V(D)_v^0. Case 1) is trivial, but it is still worth observing that V(D ↑ v)_v^0 = V(D) ∖{v}, whereupon we formally obtain the intuitively obvious fact that (D ↑ v) ↑ v = D ↑ v. Note that case 2) is equivalent to v ∈ V(D)_w^+, so that cases 2) and 4) are equivalent by symmetry; we will address the latter.

Before proceeding with the remaining cases 3), 4), and 5), let us first define 

    Z(D)_v := [V(D) ×{v}] ∪ [{v}× V(D)]

and

    U(D)_v := P(D)_v × S(D)_v.

By construction, we have that μ_D ↑ v(Z_v) ≡ 0 and μ_D ↑ v(U_v ∖Δ(V(D))) ≡ 1. Now

    Z(D ↑ v)_w ∪ Z(D)_v = [V(D) ×{v,w}] ∪ [{v,w}× V(D)] = Z(D ↑ w)_v ∪ Z(D)_w

so it suffices to show that

    U(D ↑ v)_w ∪ [U(D)_v ∖ Z(D ↑ v)_w] = U(D ↑ w)_v ∪ [U(D)_w ∖ Z(D ↑ w)_v]

or equivalently (writing  as usual for symmetric difference)

    [U(D ↑ v)_w ∪ U(D)_v]   [U(D ↑ w)_v ∪ U(D)_w] ⊆ [V(D) ×{v,w}] ∪ [{v,w}× V(D)].


Case 3: w ∈ V(D)_v^±. In this case (see figure <ref> for a cartoon and note that) we have the following identities:

    P(D ↑ v)_w     =     P(D)_v ∪ [P(D)_w ∖{v}]; 
    
    S(D ↑ v)_w     =     S(D)_v ∪ [S(D)_w ∖{v}]; 
    
    P(D ↑ w)_v     =     [P(D)_v ∖{w}] ∪ P(D)_w; 
    
    S(D ↑ w)_v     =     [S(D)_v ∖{w}] ∪ S(D)_w.

From these it follows that 

    U(D ↑ v)_w ∪ U(D)_v    ≡    [P(D ↑ v)_w × S(D ↑ v)_w] ∪ [P(D)_v × S(D)_v] 
        =     [P(D)_v × S(D)_v] ∪ [P(D)_v × (S(D)_w ∖{v})] 
           ∪ [(P(D)_w ∖{v}) × S(D)_v] ∪ [(P(D)_w ∖{v}) × (S(D)_w ∖{v})]

and by symmetry

    U(D ↑ w)_v ∪ U(D)_w     =     [P(D)_w × S(D)_w] ∪ [P(D)_w × (S(D)_v ∖{w})] 
           ∪ [(P(D)_v ∖{w}) × S(D)_w] ∪ [(P(D)_v ∖{w}) × (S(D)_v ∖{w})]

so upon inspection (<ref>) is satisfied and case 3) is done.



Case 4: w ∈ V(D)_v^+. In this case (see figure <ref> for a cartoon and note that) we have the following identities:

    P(D ↑ v)_w     =     P(D)_v ∪ [P(D)_w ∖{v}]; 
    
    S(D ↑ v)_w     =     S(D)_w; 
    
    P(D ↑ w)_v     =     P(D)_v; 
    
    S(D ↑ w)_v     =     [S(D)_v ∖{w}] ∪ S(D)_w.

From these it follows that 

    U(D ↑ v)_w ∪ U(D)_v    ≡    [P(D ↑ v)_w × S(D ↑ v)_w] ∪ [P(D)_v × S(D)_v] 
        =     [P(D)_v × S(D)_w] ∪ [(P(D)_w ∖{v}) × S(D)_w] ∪ [P(D)_v × S(D)_v]

and 

    U(D ↑ w)_v ∪ U(D)_w    ≡    [P(D ↑ w)_v × S(D ↑ w)_v] ∪ [P(D)_w × S(D)_w] 
        =     [P(D)_v × (S(D)_v ∖{w})] ∪ [P(D)_v × S(D)_w] ∪ [P(D)_w × S(D)_w]

so upon inspection (<ref>) is satisfied and case 4) is done.



Case 5: w ∈ V(D)_v^0.  In this case we have the following identities:

    P(D ↑ v)_w     =     P(D)_w; 
    
    S(D ↑ v)_w     =     S(D)_w; 
    
    P(D ↑ w)_v     =     P(D)_v; 
    
    S(D ↑ w)_v     =     S(D)_v.

From these (<ref>) follows trivially, so case 5) is done. 




§ CASE ANALYSIS PROOF OF (D ↑ U) / {V,W} = (D / {V,W}) ↑ U FOR DIGRAPHS


The result is trivial unless v and w belong to different sets of the form V(D)_u^∙. It also suffices to show the result for a modified contraction operation (denoted  below) that yields identical copies of contracted vertices (note that this is essentially the same technical simplifcation as dealing with detours instead of bypasses). By symmetry, we need only consider the six cases where (v,w) is an element of one of the following products: V(D)_u^- × V(D)_u^±, V(D)_u^- × V(D)_u^+, V(D)_u^- × V(D)_u^0, V(D)_u^±× V(D)_u^+, V(D)_u^±× V(D)_u^0, and V(D)_u^+ × V(D)_u^0.

Consider for instance the first of these cases, where v ∈ V(D)_u^- and w ∈ V(D)_u^±. Writing vw and vw' for the identical copies of contracted vertices, V_u;v,w^∙ as a temporary shorthand for V(D)_u^∙∖{v,w}, and e.g., D {v,w} for the modified contraction, we have the following adjacency matrices (with irrelevant entries omitted):

    μ_D     u     v     w     V_u;v,w^-     V_u;v,w^±    V_u;v,w^+     V_u;v,w^0 
    	u     0     0     1     0     1     1     0 
    	v     1     0    ·   μ_v;-   ·   ·   μ_v;0
    	w     1    ·    0    μ_w;-   ·   ·   μ_w;0
    	V_u;v,w^-     1    ·   ·   ·   ·   ·   ·
    	V_u;v,w^±    1    ·   ·   ·   ·   ·   ·
    	V_u;v,w^+     0    μ_+;v   μ_+;w   ·   ·   ·   ·
    	V_u;v,w^0     0    μ_0;v   μ_0;w   ·   ·   ·   ·


    μ_D ↑ u    u     v     w     V_u;v,w^-     V_u;v,w^±    V_u;v,w^+     V_u;v,w^0 
    	u     0     0     0     0     0     0     0 
    	v     0     0     1    μ_v;-    1     1    μ_v;0
    	w     0    ·    0    μ_w;-    1     1    μ_w;0
    	V_u;v,w^-     0    ·    1    ·    1     1    ·
    	V_u;v,w^±    0    ·    1    ·    1-I     1    ·
    	V_u;v,w^+     0    μ_+;v   μ_+;w   ·   ·   ·   ·
    	V_u;v,w^0     0    μ_0;v   μ_0;w   ·   ·   ·   ·


    μ_D {v,w}    u     vw     vw'     V_u;v,w^-     V_u;v,w^±    V_u;v,w^+     V_u;v,w^0 
    	u     0     1     1     0     1     1     0 
    	vw     1     0     0    μ_v;-μ_w;-   ·   ·   μ_v;0μ_w;0
    	vw'     1     0     0    μ_v;-μ_w;-   ·   ·   μ_v;0μ_w;0
    	V_u;v,w^-     1    ·   ·   ·   ·   ·   ·
    	V_u;v,w^±    1    ·   ·   ·   ·   ·   ·
    	V_u;v,w^+     0    μ_+;vμ_+;w   μ_+;vμ_+;w   ·   ·   ·   ·
    	V_u;v,w^0     0    μ_0;vμ_0;w   μ_0;vμ_0;w   ·   ·   ·   ·

whereupon both (D ↑ u) / {v,w} and (D/{v,w}) ↑ u can be seen to have the adjacency matrix

    u     vw     vw'     V_u;v,w^-     V_u;v,w^±    V_u;v,w^+     V_u;v,w^0 
    	u     0     0     0     0     0     0     0 
    	vw     0     0     0    μ_v;-μ_w;-    1     1    μ_v;0μ_w;0
    	vw'     0     0     0    μ_v;-μ_w;-    1     1    μ_v;0μ_w;0
    	V_u;v,w^-     0     1     1    ·    1     1    ·
    	V_u;v,w^±    0     1     1    ·    1-I     1    ·
    	V_u;v,w^+     0    μ_+;vμ_+;w   μ_+;vμ_+;w   ·   ·   ·   ·
    	V_u;v,w^0     0    μ_0;vμ_0;w   μ_0;vμ_0;w   ·   ·   ·   ·

and this case is done. The other cases are entirely similar (in fact, the first, second, fourth and fifth cases are nearly identical). 




§ REMARK ON RENORMALIZATION


We recall two theorems described in <cit.> regarding D_n,p:


Theorem. If c >1 is constant, then with high probability D_n,c/n contains a unique strong component of size ≈ (1-x/c)^2 n, where x < 1 solves xe^-x = ce^-c. Furthermore, all other strong components are of logarithmic size. 


Theorem. lim_n ℙ(D_n,p is strongly connected) = exp(-2e^-lim_n (pn-log n)). 


These theorems suggest studying the behavior of (n-N) f^∘ N(c/n) and (n-N) f^∘ N(c+log n/n) for c constant and 0 ≤ N < n. Numerics indicate that for c > 1 the first of these is greater than unity except for N ≈ n, and the second is always greater than unity: see figures <ref> and <ref>.

 

 


    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


15

BangJensenGutinBang-Jensen, J., and Gutin, G. Digraphs: Theory, Algorithms and Applications. 2nd ed. Springer (2009). 

BloznelisGotzeJaworskiBloznelis, M., Götze, F., and Jaworski, J. “Birth of a strongly connected giant in an imhomogenous random digraph.” J. Appl. Prob. 49, 601 (2012).

CheneyAcarPereraCheney, J., Acar, U. A., and Perera, R. “Toward a theory of self-explaining computation.” In Tannen, V. et al., eds. In Search of Elegance in the Theory and Practice of Computation. Springer (2013).

CountIblis Count Iblis (http://math.stackexchange.com/users/155436/count-iblis), “Good closed form approximation for iterates of x^2+(1-x^2)x”, URL (version: 2016-07-26): http://math.stackexchange.com/q/1872168

DowlingDowling, T. A. “A class of geometric lattices based on finite groups.” J. Combinatorial Th. (B) 14, 61 (1973).

FriezeKaronskiFrieze, A. and Karoński, M. Introduction to Random Graphs. Cambridge (2016).

GlazekGlazek, K. A Guide to the Literature on Semirings and their Applications in Mathematics and Information Sciences. Springer (2002).

HanlonHershShareshianHanlon, P., Hersh, P., and Shareshian, J. “A GL_n(q) analogue of the partition lattice.” Preprint (2009).

KnuthKnuth, D. E. The Art of Computer Programming, vol. 4, fasicle 3. Addison Wesley (2005).

MacLaneMac Lane, S. Categories for the Working Mathematician. 2nd ed. Springer (1978).

MasudaLambiotteMasuda, N. and Lambiotte, R. A Guide to Temporal Networks. World Scientific (2016).

NaumovichClarkeCobleighNaumovich, G., Clarke, L. A., and Cobleigh, J. M.“Using partial order techniques to improve performance of data flow analysis based verification.” PASTE (1999).

NielsonNielsonHankinNielson, F., Nielson, H. R., and Hankin, C. Principles of Program Analysis. Springer (2010).

SchwartzAvgerinosBrumleySchwartz, E. J., Avgerinos, T., and Brumley, D. “All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask).” IEEE Symposium on Security and Privacy (2010).

SpeyerSturmfelsSpeyer, D. and Sturmfels, B. “Tropical mathematics.” Math. Mag. 82, 163 (2009).




