On torsion in eulerian magnitude homology of Erdos-Renyi random graphs
Giuliamaria Menara

	
	Purification of Gaussian States by Photon Subtraction
    Mattia Walschaers
    September 9, 2024
=====================================================

§ ABSTRACT 
		In this paper we investigate the regimes where an Erdös-Rényi random graph has torsion free eulerian magnitude homology groups.
		To this end, we start be introducing the eulerian Asao-Izumihara complex - a quotient CW-complex whose homology groups are isomorphic to direct summands
		of the graph eulerian magnitude homology group.
		We then proceed by producing a vanishing threshold for a shelling of eulerian Asao-Izumihara complex.
		This will lead to a result establishing the regimes where eulerian magnitude homology of Erdös-Rényi random graphs is torsion free. 
	
	
	

§ INTRODUCTION

	
	Magnitude, introduced by Leinster in <cit.>, is an invariant for metric spaces that quantifies the number of effective points in the space.
	Hepworth and Willerton introduced magnitude homology for graphs as a categorification of magnitude <cit.>, and this concept was later extended to metric spaces and enriched categories by Leinster and Shulman <cit.>.
	In recent years, various methods have been devised to calculate the magnitude homology groups <cit.>.
	
	Eulerian magnitude homology is a variant recently introduced by Giusti and Menara in <cit.> to highlight the connection between magnitude homology of simple graphs equipped with the path metric and their combinatorial structure.
	Here the authors introduce the complex of eulerian magnitude chains, which are supported by trails without repeated vertices.
	Then they describe the strong connections between the (k,k)-eulerian magnitude homology groups and the graph's structure.
	Further, in the context of Erdös-Rényi random graphs they derive a vanishing threshold for the limiting expected rank of the (k,k)-eulerian magnitude homology in terms of the density parameter.
		
	In this paper, we will make some progress towards investigating the presence of torsion in eulerian magnitude homology.
	
	Torsion in standard magnitude homology was first studied by Kaneta and Yoshinaga in <cit.>, where the authors have analyzed the structure and implications of torsion in magnitude homology.
	Torsion in the magnitude homology of graphs was also studied by Sazdanovic and Summers in <cit.> and by Caputi and Collari in <cit.>.
	
	In the present work, as a first step towards exploring whether graphs have torsion in their eulerian magnitude homology groups, we turn our attention to Erdös-Rényi model for random graphs.
	This model is the most extensively studied and utilized model for random graphs, and it represents the maximum entropy distribution for graphs with a given expected edge proportion.
	Random complexes originating from Erdös-Rényi graphs are widely studied in stochastic topology <cit.>, and in studying this “unstructured" example our intent is to create a foundation for understanding the torsion in “structured" graphs.
	
	Adapting the construction introduced by Asao and Izumihara in <cit.> to the context of eulerian magnitude homology, we able to produce for every pair of vertices (a,b) ∈ G two simplicial complexes (a,b) and (a,b) such that the homology of the quotient (a,b) / (a,b) is isomorphic to a direct summand of the eulerian magnitude homology  EMH_∗,ℓ(G) up to degree shift.
	Therefore, producing a shellability result of the complexes (a,b) and (a,b) will in turn determine a torsion-free result for EMH_∗,ℓ(G).
	In Theorem <ref> we achieve such shellability result for (a,b) in terms of the density parameter.
	Further, in Corollary <ref> we link the torsion-free result for eulerian magnitude homology groups stated in Theorem <ref> with the vanishing threshold produced in <cit.>, determining sufficient conditions under which if eulerian magnitude homology is non-vanishing, then it is also torsion-free.
	
		
	

 §.§ Outline

	The paper is organized as follows. 
	We start by recalling in Section <ref> some general background about graphs, eulerian magnitude homology and shellability.
	In Section <ref> we introduce the eulerian Asao-Izumihara complex.
	We then investigate in Section <ref> the probability regimes in which the eulerian Asao-Izumihara complex is shellable, and we conclude by producing a vanishing threshold for torsion in eulerian magnitude homology groups.	
	Finally, in Section <ref> we propose extensions of the current work and identify open questions that could deepen the understanding of the topic.

	
	

§ BACKGROUND

	
	
	We begin by recalling relevant definitions and results.
	We assume readers are familiar with the general theory of simplicial homology (for a thorough exposition see <cit.>).
	Throughout the paper we adopt the notation [m] = {1, …, m} and [m]_0 = {0, …, m} for common indexing sets.
	
	
	
	
	
	
		
	
	
	
		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

 §.§ Graph terminology and notation

	
	
	An undirected graph is a pair G=(V,E) where V is a set of vertices and E is a set of edges (unordered pairs of vertices).
	A walk in such a graph G is an ordered sequence of vertices x_0,x_1,…,x_k∈ V such that for every index i ∈ [k]_0 there is an edge {x_i,x_i+1}∈ E.
	A path is a walk with no repeated vertices.
	For the purposes of introducing eulerian magnitude homology we assume that all graphs are simple, i.e. they have no self-loops and no multiedges <cit.>.
	One can interpret the set of vertices of a graph as an extended metric space (i.e. a metric space with infinity allowed as a distance) by taking the path metric d(u,v) to be equal to the length of a shortest path in G from u to v, if such a path exists, and taking d(u,v) = ∞ if u and v lie in different components of G.
	
	
		
		Let G = (V,E) be a graph, and k a non-negative integer. A k-trail x̅ in G is a (k+1)-tuple (x_0,…,x_k) ∈ V^k+1 of vertices for which x_i ≠ x_i+1 and d(x_i,x_i+1)<∞ for every i ∈ [k-1]_0.
		The length of a k-trail (x_0,…,x_k) in G is defined as the minimum length of a walk that visits x_0,x_1,…,x_k in this order:
		
    (x_0,…,x_k) = d(x_0,x_1)+⋯ + d(x_k-1,x_k).

		We call the vertices x_0, … x_k the landmarks, x_0 the starting point, and x_k the ending point of the k-trail.
	
	
	
	

 §.§ Eulerian magnitude homology

	
	
	The magnitude homology of a graph G, MH_k,ℓ(G), was first introduced by Hepworth and Willerton in <cit.>, and the eulerian magnitude homology of a graph EMH_k,ℓ(G) is a variant of it with a stronger connection to the subgraph structures of G.
	Specifically, while the building blocks of standard magnitude homology are tuples of vertices (x_0,…,x_k) where we ask that consecutive vertices are different, eulerian magnitude homology is defined starting from tuples of vertices (x_0,…,x_k) where we ask that all landmarks are different.
	
	Eulerian magnitude homology was recently introduced by Giusti and Menara in <cit.> and we recall here the construction.
	
	(Eulerian magnitude chain)
		Let G=(V,E) be a graph.
		We define the (k,ℓ)-eulerian magnitude chain EMC_k,ℓ(G) to be the free abelian group generated by trails (x_0,…,x_k) ∈ V^k+1 such that x_i ≠ x_j for every 0≤ i,j ≤ k and (x_0,…,x_k)=ℓ.
	
	
	It is straightforward to demonstrate that the eulerian magnitude chain is trivial when the length of the path is too short to support the necessary landmarks.
	
	
		
		Let G be a graph, and k > ℓ non-negative integers. Then EMC_k,ℓ(G) ≅ 0.
	
	
	
		Suppose EMC_k,ℓ(G)≠ 0.
		Then, there must exist a k-trail (x_0,…,x_k) in G so that (x_0,…,x_k)=d(x_0,x_1)+⋯+d(x_k-1,x_k) = ℓ.
		However, as all vertices in the k-trail must be distinct, d(x_i,x_i+1) ≥ 1 for i ∈ [k-1]_0, so k can be at most ℓ.
	
	
	(Differential)
		
		Denote by (x_0,…,x̂_̂î,…,x_k) the k-tuple obtained by removing the i-th vertex from the (k+1)-tuple (x_0,…,x_k).  We define the differential
		
    ∂_k,ℓ: EMC_k,ℓ(G) → EMC_k-1,ℓ(G)

		to be the signed sum ∂_k,ℓ= ∑_i∈ [k-1](-1)^i∂_k,ℓ^i of chains corresponding to omitting landmarks without shortening the walk or changing its starting or ending points,
		
    ∂_k,ℓ^i(x_0,…,x_k) = 
    			(x_0,…,x̂_̂î,…,x_k) ,     if (x_0,…,x̂_̂î,…,x_k) = ℓ, 
    
    			0,     otherwise.

	
	
	For a non-negative integer ℓ, we obtain the eulerian magnitude chain complex, EMC_*,ℓ(G), given by the following sequence of free abelian groups and differentials.
	
	(Eulerian magnitude chain complex)
		We indicate as EMC_*,ℓ(G) the following sequence of free abelian groups connected by differentials
		
    ⋯→ EMC_k+1,ℓ(G)  EMC_k,ℓ(G)  EMC_k-1,ℓ(G) →⋯

	
	
	The differential map used here is the one induced by standard magnitude, and it is shown in <cit.> that the composition ∂_k,ℓ∘∂_k+1,ℓ vanishes, justifying the name “differential" and allowing the definition the corresponding bigraded homology groups of a graph.
	
	(Eulerian magnitude homology)
		
		The (k,ℓ)-eulerian magnitude homology group of a graph G is defined by
		
    EMH_k,l(G) = H_k(EMC_*,l(G)) = (∂_k,ℓ)/(∂_k+1,ℓ).

	
	
	
	
	
	Notice that by construction we have the following proposition.
	
	
		For ℓ≥ 0, the following direct sum decomposition holds:
		
    EMC_∗, ℓ(G) =⊕_a, b∈ V(G) EMC_∗, ℓ(a, b),

		where EMC_∗, ℓ(a, b) is the subcomplex of EMC_∗, ℓ(G) generated by trails which start at a and end at b.
	
	
	
	

 §.§ Shellable simplicial complexes

	
	
	We recall the definition of shellable simplicial complex.
	
	
		
		If X is a finite simplicial complex, then a shelling of X is an ordering F_1,…,F_t of the facets (maximal faces) of X such that F_k ∩⋃_i=1^k-1F_i is a non-empty union of facets of F_k for k ≥ 2.
		If X has a shelling, we say it is shellable.
	
	
	In other words, we ask that the last simplex F_k meets the previous simplices along some union B_k of top-dimensional simplices of the boundary of F_k, so that X can be built stepwise by introducing the
	facets one at a time and attaching each new facet F_k to the complex previously built in the nicest possible fashion.
	
	Suppose X is a non-pure simplicial complex.
	In this case the first facet of a shelling is always of maximal dimension.
	In fact, if X is shellable there is always a shelling in which the facets appear in order of decreasing dimension.
	
	
		
		Let F_1, F_2, … ,F_t be a shelling of X.
		Let F_i_1, F_i_2, … ,F_i_t be the rearrangement obtained by taking first all
		facets of dimension d =  X in the induced order, then all facets of dimension d-1 in the induced order, and continuing this way in order of decreasing dimension.
		Then this rearrangement is also a shelling.
	

	
		
		Let X be a simplicial complex, and let 0 ≤ r ≤ s ≤ X.
		Define X^(r,s)={σ∈ X  such that σ≤ s  and σ∈ F  for some facet F with  F ≥ r  }.
		If X is shellable, then so is X^(r,s) for all r ≤ s.
	

	Lemma <ref> and Theorem <ref> can be interpreted as providing a kind of “structure theorem”, describing how a general shellable complex X is put together from pure
	shellable complexes.
	First there is the pure shellable complex X^1=X^(d,d) generated by all facets of maximal size.
	Then X^1's (d-1)-skeleton, which is also shellable, is extended by shelling steps in dimension d-1 to obtain X^2=X^(d-1,d).
	Then X^2's (d-2)-skeleton is extended by shelling steps in dimension (d-2) to obtain X^(d-2,d), and so on until all of X=X^(0,d) has been constructed.
	
	A shellable simplicial complex enjoys several strong properties of a combinatorial, topological and algebraic nature.	
	Let it suffice here to mention that it is homotopy equivalent to a wedge sum of spheres, one for each spanning simplex of corresponding dimension <cit.>.
	
	
	

§ EULERIAN ASAO-IZUMIHARA COMPLEX

	
	
	We introduced in this section the eulerian Asao-Izumihara complex.
	
	Recall that the Asao-Izumihara complex is a CW complex which is obtained as the quotient of a simplicial complex K_ℓ (a,b) divided by a subcomplex K'_ℓ (a,b), and was proposed in <cit.> as a geometric approach to compute magnitude homology of general graphs.
	Here we adapt this construction to the context of eulerian magnitude homology, providing a way of replacing the computation of the eulerian magnitude homology EMH_k,ℓ(G) by that of simplicial homology.  
	


	Let us start by recalling the Asao-Izumihara complex.
	Let G=(V,E) be a connected graph and fix k ≥ 1.
	For any a,b ∈ V the set of walks with length ℓ which start with a and end with b is denoted by
	
    W_ℓ(a,b):={x̅=(x_0,…,x_k)  walk in G | x_0=a,x_k=b, (x̅)=ℓ}.


	
	
		Let G be a graph, and a, b ∈ V, ℓ≥ 3.
		
			   K_ℓ(a,b) := {       ∅≠((x_i_1,i_1),…,(x_i_k,i_k)) ⊂V ×{1,…,ℓ-1} 

			   	       | (a, x_i_1,…,x_i_k,b) ≺∃(a, x_1,…, x_ℓ-1, b) ∈W_ℓ(a,b) } 

			   K'_ℓ(a,b) := {       ((x_i_1,i_1),…,(x_i_k,i_k)) ∈K_ℓ(a,b) | (a, x_i_1,…,x_i_k,b) ≤ℓ-1 }.
		
	

	
		Following <cit.>, we will denote ((x_i_1,i_1),…,(x_i_k,i_k)) by (x_i_1,…,x_i_k) when there is no confusion.
		
		It can also be easily seen that K_ℓ(a,b) is a simplicial complex and K'_ℓ(a,b) is a subcomplex.
	

	
		Let ℓ≥ 3 and ∗≥ 0.
		Then, the isomorphism
		
    (C_∗(K_ℓ(a,b),K'_ℓ(a,b)),-∂) ≅
    		(MC_∗ +2,ℓ(a,b),∂)

		of chain complexes holds.
	

	
		Let ℓ≥ 3. 
		
			
  * If k ≥ 3, MH_k,ℓ(a,b) ≅ H_k-2(K_ℓ(a,b),K'_ℓ(a,b)).
			
  * If k = 2, we also have
			
    MH_2, ℓ(a, b) ≅H_0(K_ℓ(a, b), K'_ℓ(a, b))     if  d(a, b) < ℓ, 
    H̃_0(K_ℓ(a, b))    if  d(a, b) = ℓ,

			where H̃_∗ denotes the reduced homology group. 
		
	

	
		Notice while both K_ℓ -1(a,b) and K'_ℓ(a,b) are subcomplexes of K_ℓ(a,b), in general K_ℓ -1(a,b) ⊊ K'_ℓ(a,b).
		Indeed, say v and u are two adjacent vertices, then the tuple (v,u,u) is an element of both K_3(v,u) and K'_3(v,u) because it is a subtuple of (v,u,v,u), but it cannot be in K_2(v,u).
		This type of example with consecutively repeated vertices is the only one that can be constructed to show that K_ℓ-1(a,b) is a proper subset of K'_ℓ(a,b), and in the context of eulerian magnitude homology it cannot arise because the tuples have all different vertices.
		Therefore when introducing the eulerian Asao-Izumihara complex it will possible to only rely on the (eulerian versions of the) complexes K_ℓ(a,b) and K_ℓ -1(a,b).
	
	
	
		
		Let (a, b) be the set of eulerian trails from a to b with length smaller than ℓ. 
		That is, the set of all trails (x_1, …, x_t)∈ V^t+1 such that x_i ≠ x_j for every i, j ∈{1,…,t} and 
		
    (a,x_1, …, x_t,b) ≤ℓ.

	
	
	The set (a, b) is clearly a simplicial complex, and the complex (a, b) is a subcomplex of (a, b), see Figure <ref> for an illustration.
	
	
		Consider the same graph G as in example <ref>.
		Suppose we choose (a,b)=(0,4) and ℓ =4.
		Then we have ET_4(0,4)={(1,2,3),(1,2),(1,3),(2,3),(1),(2),(3) } and ET_3(0,4)={(1,2),(2,3),(1),(2),(3) }.
		
		
	
	
	The following two results can be shown proceeding similarly to the proofs of <cit.>.
	
	
		
		
		Let a, b be vertices of a graph G, and fix an integer  ℓ≥ 3. 
		Then we can construct a pair of simplicial complexes ((a, b),(a, b)) which satisfies
		
    C_∗ -2((a, b), (a, b)) ≅ EMC_∗,ℓ(a, b).

	
	
	
	
		
		Let ℓ≥ 3. Then
		
    EMH_k, ℓ(a, b)≅ H_k-2((a, b), (a, b))

		Moreover, for k = 2, we also have
		
    EMH_2, ℓ(a, b) ≅H_0((a, b), (a, b))     if  d(a, b) < ℓ, 
    H̃_0((a, b))    if  d(a, b) = ℓ,

		where H̃_∗ denotes the reduced homology group.
	
		
	

§ TORSION IN EMH OF ERDŐS-RÉNYI RANDOM GRAPHS

	
	
	In this section we investigate the regimes where the eulerian magnitude homology of Erdős-Rényi random graphs is torision free.
	
	Recall that the Erdős-Rényi (ER) model for random graphs, denoted as G(n,p) and first introduced in <cit.>, is one of the most extensively studied and utilized models for random graphs.
	This model represents the maximum entropy distribution for graphs with a given expected edge proportion, making it a valuable null model across a wide array of scientific and engineering fields. Consequently, the clique complexes of ER graphs have garnered significant interest within the stochastic topology community <cit.>.
	
	
		The Erdős-Rényi (ER) model 
		G(n, p) = (Ω, P) is the probability space where Ω is the discrete space of all graphs on n vertices, and
		P is the probability measure that assigns to each graph G ∈Ω with m edges probability
		
    P(G)=p^m(1-p)^n  2-m.

	
	
	We can sample an ER graph G ∼ G(n, p) on n vertices with parameter p∈ [0,1] by determining whether each of the n  2 potential edges is present via independent draws from a Bernoulli distribution with probability p.
	In order to study the limiting behavior of these models as n →∞, it is often useful to change variables so that p is a function of n.
	Here we will take p=n^-α, α∈ [0,∞), as in <cit.>.
	
	We will first prove in Section <ref> that, under certain assumptions, the complex (a,b) is shellable for every choice for ℓ≥ 3.
	This will imply that H_∗((a,b),(a,b)) is torsion free, and by Corollary <ref> that EMH_∗+2,ℓ(G) is torsion free.
	
	

 §.§ Homotopy type of the eulerian Asao-Izumihara complex

	
	
	Recall from Section <ref> that the eulerian Asao-Izumihara chain complex is the relative complex C_∗((a,b) , (a,b)), where (a,b) is the set of eulerian tuples (x_0…,x_k) such that (a,x_0,…,x_k,b) ≤ℓ, and (a,b) is defined similarly.
	Fix and integer ℓ≥ 3. 
	
	
		
		Let G(n,n^-α) be an ER graph.
		Suppose the facets f_1,…,f_t-1,f_t of (a,b) are ordered in decreasing dimension. 
		
		
		Then as n→∞ ET_≤ℓ(a,b) is shellable asymptotically almost surely when	
		
			
  * 0< α < ∏_i=1^t-1 f_i +  f_i+1/ℓ +2 f_i+1 -2, if f_1  < ℓ -2/2,
			
  * 0<α< ∏_i=1^k-1 f_i +3/ℓ +4∏_i=k^t-1 f_i +  f_i+1/ℓ +2 f_i+1 -2, if f_i ≥ℓ -2/2 for 1 ≤ i ≤ k-1 and f_i < ℓ -2/2 for i ≥ k.
		
		
	 
	
	
		 Consider the facets f_1,…,f_t of (a,b).
		 Suppose they are ordered in decreasing dimension and say f_1=d.
		 There are some cases we need to consider.
		 
		 	
  * If there is a single facet f_1, then (a,b) is homotopic to a sphere S^d-1 with d= f_1 and we are done.
		 	
  * Say there are two different maximal facets, f_1 and f_2 and suppose they have the same dimension d.

		 	If f_1 and f_2 differ in one vertex, then they intersect in a (d-1)-face, and thus {f_1,f_2} is a shelling.
		 	
		 	If f_1 and f_2 differ in two vertices u,v, then we need to distiguish the situations when u and v are adjacent and when they are not.
		 	
		 		
  * If u and v are not adjacent, then we will have f_1=(a,…,u,…,v,…,b) and f_2=(a,…,u',…,v',…,b), and by construction there exists a third facet f_3=(a,…,u',…,v,…,b) such that {f_1,f_3,f_2} is a shelling, see Figure <ref>.
		 		
		 		
		 		
		 		
		 		
  * If  u and v are adjacent, then in order to construct a facet f_3 intersecting f_1 in a (d-1)-face we need either the edge (u,v') or the edge (u',v) to be present (see Figure <ref>), and this happens with probability p=n^-α.
		 	
		 	
		 	
		 	
		 	
		 	Now say f_1 and f_2 differ in m vertices and, indicating the facets f_1 and f_2 only by the vertices they differ in,  write f_1=(u_1,u_2,…,u_m) and f_2=(u_1',u_2',…,u_m').
		 	Define a partition A_i with ⋃_iA_i={u_1,…,u_m} such that two vertices u_α^i, u_β^i belong to the same set A_i if and only if they are adjacent in G, see Figure <ref>.
		 	Call A'_i the corresponding partition for the vertices (u_1',u_2',…,u_m').
		 	Notice that |A_i|=|A'_i| for every i. 
		 	Indeed, suppose by contradiction this is not true.
		 	Then, because f_1 and f_2 have the same dimension, there exists i_1,i_2 such that |A_i_1| > |A_i_1'| and |A_i_2| < |A_i_2'|.
		 	But then it is possible to construct a f_3 visiting vertices from A_i_1 and A_i_2' thus having f_3 >  f_1, f_2, contradicting the fact that f_1 and f_2 are maximal facets.
		 	
		 	Then in this case we need for every set of adjacent vertices A_i and A'_i a number |A_i|-1 of edges (u_α^i, u_β^', i), α≠β, in order to create a shelling.
		 	Indeed, we need to be able to construct a sequence of facets f'_1,…,f'_m by changing one vertex each time so that the intersection between the j-th facet and the preceding (j-1) facets is a (d -1)- dimensional simplex, see Figure <ref>.  
		 	Given the fact that we also require for every set A_i a number |A_i|+1 of edges to connect the vertices in A_i, we obtain that the probability of all the required edges existing is
		 	
    p^ℓ + ∑_i(|A_i|+1) + ∑_i(|A_i|-1) =  p^ℓ +2m.
 
		 	With p=n^-α, α∈ [1/2,∞), we get  
		 	
    ∑_m=2^d-1nd+1+m n^-α (ℓ + 2m)≤
       (d-2) nd+3 n^-α (ℓ + 4)∼
        (d-2) n^d+3/(d+3)! n^-α (ℓ + 4)
    		 			0,  if α > d+3/ℓ +4
    ∞,  if α < d+3/ℓ +4.

		 	
		 	Notice that we assumed α∈ [1/2,∞) and d+3/ℓ +4≥1/2 only when d ≥ℓ -2/2.
		 	 
		 	
		 	With p=n^-α, α∈ [0,1/2), we get  
		 	
    ∑_m=2^d-1nd+1+m n^-α (ℓ + 2m)≤
       (d-2) n2d n^-α (ℓ + 2d -2)∼
        (d-2) n^2d/(2d)! n^-α (ℓ + 2d -2)
    		 			0,  if α > 2d/ℓ + 2d -2
    ∞,  if  0<α < 2d/ℓ + 2d -2.

		 	
		 	Since it holds also in this case that 2d/ℓ + 2d -2≥1/2 if and only if d ≥ℓ -2/2, we can conclude that we can construct a shelling when
		 	
    0< α < d+3/ℓ +4,  if  d≥ℓ -2/2
    
    		 		0<α< 2d/ℓ +2d -2,  if  d< ℓ -2/2.

		 	
		 	
		 	
		
  * Suppose now there are two different facets, f_1 and f_2, and suppose f_2 <  f_1.
		
		
		Let f_2 = d'≤ d-1.
		Following the structure theorem for non-pure shellable complexes provided by Lemma <ref> and Theorem <ref>, in order to produce a shelling we need to extend the (d')-skeleton of f_1 to f_2 by constructing a sequence of (d')-dimensional facets f'_1,…,f'_m by changing one vertex each time so that the intersection between the j-th facet and the preceding (j-1) facets is a (d'-1)-dimensional simplex.

		If the simplices in the (d')-skeleton of f_1 and f_2 differ in m ≤ d'-1 vertices, constructing such sequence is possible if we can find ℓ +2m edges joining the vertices in which f_1 and f_2 differ. 
		This happens with probability p^ℓ +2m and therefore following the computations done in the previous point we get, for p = n^-α and α∈ [1/2, ∞),
		
    ∑_m=2^d'-1nd+1+m n^-α (ℓ + 2m)≤
       (d-3) nd+3 n^-α (ℓ + 4)∼
       (d-3) n^d+3/(d+3)! n^-α (ℓ + 4)
    				0,  if α > d+3/ℓ +4
    ∞,  if 1/2<α < d+3/ℓ +4.

		

		With p=n^-α, α∈ [0,1/2), we get  
		
    ∑_m=2^d'-1nd+1+m n^-α (ℓ + 2m)≤
       (d-3) nd+d' n^-α (ℓ + 2(d'-1))∼
        (d-3) n^d+d'/(d+d')! n^-α (ℓ + 2d' -2)
    				0,  if α > d+d'/ℓ + 2d' -2
    ∞,  if  0<α < d+d'/ℓ + 2d' -2.

		
		
		Again, from the fact that both inequalities d+3/ℓ +4≥1/2 and d+d'/ℓ + 2d' -2≥1/2 are true if and only if d ≥ℓ -2/2, we conclude that we can construct a shelling when
		
    0< α < d+4/ℓ +4,  if  d≥ℓ -2/2
    
    			0<α< d+d'/ℓ + 2d' -2,  if  d< ℓ -2/2.

		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
		
	 	
	 	
  * Suppose there are t facets f_1,…,f_t-1,f_t ordered in decreasing order with f_1=d, then we only need to iterate the observations made in point (3).
	 	
	 	That is, at each step j ∈ [1,...t-1] we have a shelling when
	 	
    0< α <  f_j +3/ℓ +4 ,  if  f_j ≥ℓ -2/2
    
    	 		0<α<  f_j + f_j+1/ℓ + 2 f_j+1 -2,  if  f_j< ℓ -2/2.

	 	
	 	Therefore, suppose d= f_1 < ℓ -2/2.
	 	Then every smaller facet f_k will be such that f_k < ℓ -2/2 and we will have a shelling when 
	 	
    α < ∏_i=1^t-1 f_i +  f_i+1/ℓ +2 f_i+1 -2.

	
	 	
	 	On the other hand, if d= f_1 ≥ℓ -2/2 let f_k be the first facet in the sequence f_1,…,f_t such that f_k < ℓ -2/2.
	 	Then we will have a shelling when 
	 	
    α < ∏_i=1^k-1 f_i +3/ℓ +4∏_i=k^t-1 f_i +  f_i+1/ℓ  +2 f_i+1 -2.


		
	

	
	
		
		Let G(n,n^-α) be an ER graph.
		Suppose the facets g_1,…,g_τ-1,g_τ of (a,b) are ordered in decreasing dimension.
		
		Then as n →∞ (a,b) is shellable asymptotically almost surely when
		
			
  * 0< α < ∏_i=1^τ-1 g_i +  g_i+1/(ℓ -1) +2 g_i+1 -2, if g_1  < (ℓ -1) -2/2,
			
  * 0<α< ∏_i=1^k-1 g_i +3/(ℓ -1) +4∏_i=k^τ-1 g_i +  g_i+1/(ℓ -1) +2 g_i+1 -2, if g_i ≥(ℓ -1) -2/2 for 1 ≤ i ≤ k-1 and g_i < (ℓ -1) -2/2 for i ≥ k.
		

	

	It was shown in both <cit.> and <cit.> that a shellable simplicial complex has the homotopy type of a wedge of spheres. 
	
	Therefore using Theorem <ref> and Corollary <ref> we can show the following.  

	
		
		Let G(n,n^-α) be an ER graph.
		For any pair of vertices (a,b)∈ V^2 consider the eulerian Asao-Izumihara chain complex C_∗ -2(ET_≤ℓ(a,b), ET_≤ℓ-1(a,b)) ≅ EMC_∗,ℓ(a, b).
		Suppose the facets f_1,…,f_t of ET_≤ℓ(a,b) and g_1,…,g_τ of ET_≤ℓ-1(a,b) are ordered in decreasing dimension.
		As n →∞, in the regimes where both (a,b) and (a,b) are shellable, EMH_k,ℓ(a,b) is torsion free for every k.

	
	
	
		In the regimes where both (a,b) and (a,b) are shellable we can assume 
		
    (a,b) ≃⋁_i=1^t S_i^n_iand(a,b) ≃⋁_j=1^τ S_j^n_j.

		
		So, H_k ((a,b), (a,b)) ≅ H_k ( ∨ S^n_i, ∨ S^n_j), and considering the long exact sequence
		
    ⋯→ H_k(∨ S^n_j) → H_k(∨ S^n_i) → H_k ( ∨ S^n_i, ∨ S^n_j) →  H_k-1(∨ S^n_j) →⋯

		we see that 
		
    H_k ((a,b), (a,b)) ≅ H_k ( ∨ S^n_i, ∨ S^n_j) ≅ℤ^m_i,  if  k=n_i, 
    ℤ^m_j,  if  k=n_j, 
    
    			0,  otherwise.

		
		Finally, from the isomorphism theorem <ref> proved in <cit.>, we can conclude that EMH_k,ℓ(a,b) is torsion free for every k.
		
	
	
	Recall that <cit.> provides a vanishing threshold for the limiting expected rank of the (ℓ, ℓ)-eulerian magnitude homology in terms of the density parameter in the contexts of Erdös-Rényi random graphs. 
	
	
		
		Let G = G(n,n^-α) be an Erdös-Rényi random graph. Fix ℓ and let α > ℓ+1/2ℓ-1. 
		As n →∞, [β_ℓ,ℓ(n, n^-α)] → 0 asymptotically almost surely.
	
	
	
		
		Notice that when the smallest facet of (a,b), f_t, is such that f_t  ∼ℓ > ℓ -2/2, then (a,b) is shellable when 
		
    α < ∏_i=1^t-1( f_i +3/ℓ +4) ∼∏_i=1^t-1(ℓ +3/ℓ +4) ∼ 1.
 
		
	
	
	Therefore, putting together Remark <ref> with Theorems <ref> and <ref> we have the following.
	
	
		
		Let G(n,n^-α) be an Erdős-Rényi random graph.
		When the smallest facet f_t of (a,b) and the smallest facet g_τ of (a,b) are such that f_t,  g_τ∼ℓ, if EMH_k,ℓ(G(n,n^-α)) is non-vanishing it is also torsion free.	
	


	

§ FUTURE DIRECTIONS

	
	
	In this paper we investigated the regimes where an Erdös-Rényi random graph G has torsion free eulerian magnitude homology groups.
	
	While the results presented have provided significant insights into the problem, several aspects remain unexplored, offering fertile ground for continued research.
	
	In this section, we propose extensions of the current work and identify open questions that could deepen the understanding of the topic.
	
	

 §.§ The choice of ℓ

	
	The result stated in Corollary <ref> relies on the dimension of the minimal facet f_t of (a,b) and the minimal facet g_τ of (a,b) being “close enough” to the parameter ℓ so that f_i +3/ℓ +4∼ 1 and g_j +3/ℓ +4∼ 1 for every other facet f_i,g_j. 
	
	It is thus natural to ask, how do we choose ℓ so that f_t ∼ℓ?
	
	First, notice that the parameter ℓ cannot be too big with respect to the number of vertices n.
	Specifically, ℓ cannot be of the order n^2.
	Indeed, suppose we pick ℓ = n(n+1)/2.
	The only way we can produce a facet f inducing a path of such length is if we have a path graph on n vertices V={1,…,n}, (a,b)=(1,⌈ n/2 ⌉), and we visit vertex n-i+1 after vertex i, i ∈{1,…,⌊ n/2 ⌋}, i.e. f= (1,n,2,n-1,…,⌈ n/2 ⌉). 
	Then f= n < n(n+1)/2.
	See Figure <ref> for an illustration.  
	
	
	
	We conclude that a quadratic growth rate for ℓ with respect to n is not appropriate.
	
	On the other hand, setting ℓ = n we do not encounter the same problem as before.
	For example, consider the path graph in Figure <ref>.
	Choosing (a,b)=(1,4) and ℓ = n =7 we find two facets f_1=(1,2,3,6,5,4) and f_2=(1,2,3,5,6,4).
	Both have dimension 6 and thus f_i +3/ℓ +4 = 6+3/7+4 = 9/11 > 1/2.
	
	Based on this computation, along with many other examples not displayed here, we make the following conjecture.
	
	
		Indicate the diameter of the graph G by diam(G).
		There exists a linear function φ such that if ℓ≤φ(diam(G)), then f_t ∼ℓ.
	

	

 §.§ Connection with the complex of injective words

	
	A natural development of the work present in this paper (which we are already investigating) concerns a deterministic result about the presence of torsion in eulerian magnitude homology groups of graphs.
	It is the author's belief that this kind of result can be achieved by exploiting the strong connection between the eulerian magnitude chain complex and the complex of injective words.
	


	An injective word over a finite alphabet V is a sequence w = v_1v_2⋯ v_t of distinct elements of V.
	Call Inj(V) the set of injective words on V partially ordered by inclusion, and recall that the order complex of a poset (P,≤), denoted Δ(P), is the simplicial complex on the vertex set P, whose k-simplices are the chains x_0 < ⋯ < x_k of P.
	For example, if P = [n]={1,…,n} with the usual ordering, then Δ(P)=Δ_n-1 is the standard (n-1)-simplex.
	
	
		A complex of injective words is an order complex Δ(W) associated to a subposet W ⊂Inj(V).
	

	Farmer <cit.> proved that if #(V)=n, then Δ(Inj(V)) has the homology of a wedge of D(n) copies of the (n-1)-sphere S^n-1, where D(n) is the number of derangements (i.e. fixed point free permutations) in 𝕊_n.
	The following result was obtained by Björner and Wachs in <cit.> as a strengthening of Farmer's theorem.
	
	
		Δ(Inj([n])) ≃⋁_D(n) S^n-1.
	

	Let now the alphabet V be the vertex set of a graph G=(V,E).
	Let Inj(V) be the set of injective words on the vertex set V and denote by Inj(V,ℓ)={w ∈Inj(V)  such that (w)≤ℓ}, the subset containing w ∈Inj(V) such that length of the walk w in G is less than ℓ.
	Then we have a filtration 
	
    Inj(V,0) ⊂Inj(V,1) ⊂⋯⊂Inj(V,ℓ) ⊂⋯⊂Inj(V).

	
	
	The following equivalence easily follows from the definition of the filtration of Inj(V) and the definition of the eulerian Asao-Izumihara complex (a,b)/(a,b), 
	
    |Inj(V,ℓ)|/|Inj(V,ℓ -1)| = ⋁_(a,b)|(a,b)|/|(a,b)|,

	
	where |·| denotes the geometric realization.
	

	
	Further, the connection between the eulerian magnitude chain complex and the complex of injective words is strengthen by the following observation.  
	
	Hepworth and Roff <cit.> thoroughly analyzed in the context of directed graphs the magnitude-path spectral sequence (MPSS), a spectral sequence whose E^1 page is exactly standard magnitude homology, path homology <cit.> can be identified with a single axis of page E^2, and whose target object is reachability homology <cit.>.
	
	Reproducing the computations proposed in <cit.> using the filtration of the complex of injective words in <ref>, leads to a version of the MPSS where the E^1 page is exactly eulerian magnitude homology.
	Since the homology of the complex of injective words, as the target object, controls the behavior of the spectral sequence, we make the following conjecture.
	
	
		Let G be a graph.
		The eulerian magnitude homology groups of G, EMH_k,ℓ(G), are torsion free for every k,ℓ≥ 0.
	
	
	
	

§ ACKNOWLEDGMENTS

	The author is thankful to Yasuhiko Asao, Luigi Caputi and Chad Giusti for helpful conversations throughout the development of this work.
	
	amsplain
	

