Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

April 12, 2023

Eulerian Magnitude Homology

Posted by Tom Leinster

Guest post by Giuliamaria Menara

Magnitude homology has been discussed extensively on this blog and definitely needs no introduction.

A lot of questions about magnitude homology have been answered and a number of possible application have been explored up to this point, but magnitude homology was never exploited for the structure analysis of a graph.

Being able to use magnitude homology to look for graph substructures seems a reasonable consequence of the definition of boundary map k,\partial_{k,\ell}. Indeed, a tuple (x 0,,x k)MC k,(x_0,\dots,x_k) \in MC_{k,\ell} is such that k,(x 0,,x k)=0\partial_{k,\ell}(x_0,\dots,x_k)=0 if for every vertex x i{x 1,,x k1}x_i \in \{x_1,\dots,x_{k-1} \} it holds that len(x i1,x i^,x i+1)<len(x i1,x i,x i+1)len(x_{i-1},\hat{x_i},x_{i+1}) \lt len (x_{i-1},x_i,x_{i+1}). In other words, if every vertex of the tuple is contained in a small enough substructure, which suggests the presence of a meaningful relationship between the rank of magnitude homology groups of a graph and the subgraph counting problem.

A major problem in exploring this relationship comes from the fact that the definition of MC k,(G)MC_{k,\ell}(G) only asks for consecutive vertices to be different. That is, if x 0x_0 and x 1x_1 are two adjacent vertices in GG an acceptable tuple in MC 5,4(G)MC_{5,4}(G) is (x 0,x 1,x 0,x 1,x 0)(x_0,x_1,x_0,x_1,x_0).

Tuples of this kind inducing a path that just revisits again and again the same edge (an more in general, tuples inducing non-eulerian trails) do not provide any insight about the meaning of magnitude homology. With this motivation, we introduce a slightly different definition of magnitude chain, considering the subgroup of MC k,l(G)MC_{k,l}(G) where a vertex (and therefore an edge) is never required to be revisited.

Definition (Eulerian magnitude chain)   Let GG be a graph. We define the eulerian (k,)(k,\ell)-magnitude chain EMC k,(G)EMC_{k,\ell}(G) to be the free abelian group generated by tuples (x 0,,x k)(x_0,\dots,x_k) of vertices of GG such that x ix jx_i \neq x_j for all distinct 0i,jk0\leq i,j \leq k and len(x 0,,x k)=len(x_0,\dots,x_k)=\ell.

Taking as differential the one induced by MC *,(G)MC_{\ast,\ell}(G) we can construct the eulerian magnitude chain complex EMC *,(G)EMC_{\ast,\ell}(G):

EMC k+1,(G) k+1,EMC k,(G) k,EMC k1,(G) \cdots \to EMC_{k+1,\ell}(G) \xrightarrow{\partial_{k+1,\ell}} EMC_{k,\ell}(G) \xrightarrow{\partial_{k,\ell}} EMC_{k-1,\ell}(G) \to \cdots

and subsequently define the eulerian (k,)(k,\ell)-magnitude homology group

EMH k,(G)=H k(EMC *,(G))=ker( k,)im( k+1,). EMH_{k,\ell}(G) = H_k(EMC_{\ast,\ell}(G)) = \frac{\ker(\partial_{k,\ell})}{\mathrm{im}(\partial_{k+1,\ell})}.

Example   Consider the following graph GG:

We want to compare MH 2,2(G)MH_{2,2}(G) and EMH 2,2(G)EMH_{2,2}(G).

The magnitude chain MC 2,2(G)MC_{2,2}(G) is generated by

(0,1,0),(0,1,2),(0,1,3), (1,0,1),(1,2,1),(1,2,3),(1,3,1),(1,3,2), (2,1,0),(2,1,2),(2,1,3),(2,3,1),(2,3,2), (3,1,0),(3,1,2),(3,1,3),(3,2,1),(3,2,3), \begin{aligned} &(0,1,0), (0,1,2), (0,1,3), \\ &(1,0,1), (1,2,1), (1,2,3), (1,3,1), (1,3,2),\\ &(2,1,0), (2,1,2), (2,1,3), (2,3,1), (2,3,2),\\ &(3,1,0), (3,1,2), (3,1,3), (3,2,1), (3,2,3), \end{aligned}

while MC 1,2(G)MC_{1,2}(G) is generated by

(0,2),(2,0),(0,3),(3,0). (0,2), (2,0), (0,3), (3,0).

We see that MH 2,2(G)=ker( 2,2)MH_{2,2}(G)=\ker(\partial_{2,2}) is generated by all elements in MC 2,2(G)MC_{2,2}(G) apart from

(0,1,2),(2,1,0),(0,1,3),(3,1,0) (0,1,2), (2,1,0), (0,1,3), (3,1,0)

and thus has rank 14.

On the other hand, the eulerian chain EMC 2,2(G)EMC_{2,2}(G) is generated by

(0,1,2),(0,1,3),(1,2,3),(1,3,2),(2,1,0),(2,1,3),(2,3,1),(3,1,0),(3,1,2),(3,2,1), (0,1,2), (0,1,3), (1,2,3), (1,3,2), (2,1,0), (2,1,3), (2,3,1), (3,1,0), (3,1,2), (3,2,1),

while EMC 1,2(G)=MC 1,2EMC_{1,2}(G)=MC_{1,2} is generated by

(0,2),(2,0),(0,3),(3,0). (0,2), (2,0), (0,3), (3,0).

We have now that EMH 2,2(G)=ker( 2,2)EMH_{2,2}(G)=\ker(\partial_{2,2}) is generated by all elements in MC 2,2(G)MC_{2,2}(G) apart from

(0,1,2),(2,1,0),(0,1,3),(3,1,0), (0,1,2), (2,1,0), (0,1,3), (3,1,0),

and thus has rank 6, as the number of permutations of the triangle [1,2,3].

Remark   We point out that all definitions and properties regarding magnitude homology proved in

Richard Hepworth and Simon Willerton, Categorifying the magnitude of a graph, Homology, Homotopy and Applications 19(2) (2017), 31–60

and

Tom Leinster and Michael Shulman, Magnitude homology of enriched categories and metric spaces, Algebraic & Geometric Topology 21 (2021), no. 5, 2175–2221

continue to be valid for eulerian magnitude homology. In particular, with this new definition, EMH 0,0(G)EMH_{0,0}(G) and EMH 1,1(G)EMH_{1,1}(G) are still counting the number of vertices and edges in a graph respectively, since the generators of the groups MC 0,0(G)MC_{0,0}(G) and MC 1,1(G)MC_{1,1}(G) already satisfy the condition of not revisiting vertices.

 

Now, in order to account for the elements in MC k,(G)MC_{k,\ell}(G) containing the repetition of at least a vertex we define the discriminant magnitude chain as the quotient between the standard magnitude chain and the eulerian one.

Definition (Discriminant magnitude chain)   Let GG be a graph. We define the discriminant (k,)(k,\ell)-magnitude chain DMC k,(G)DMC_{k,\ell}(G) as

DMC k,(G)=MC k,(G)EMC k,(G) DMC_{k,\ell}(G) = \frac{MC_{k,\ell}(G)}{EMC_{k,\ell}(G)}

Denoting by [] E[\cdot]_E the equivalence classes in DMC k,(G)DMC_{k,\ell}(G), we define the differential map ˜ k,\tilde{\partial}_{k,\ell} as

˜ k,([x 0,,x k] N)=[ k,(x 0,,x k)] E.\tilde{\partial}_{k,\ell}([x_0,\dots,x_k]_N) = [\partial_{k,\ell}(x_0,\dots,x_k)]_E.

Splitting result

(Section removed following the conversation below.)

Applications

Subgraph counting

The example above suggests the presence of the relation we were looking for between the subgraph counting problem and the ranks of magnitude homology groups.

Lemma  Let ZZ be the number of basis elements x¯EMC 2,2\overline{x} \in EMC_{2,2} such that 2,2(x¯)=0\partial_{2,2}(\overline{x})=0. The number of triangles occurring in GG is Z6\frac{Z}{6}.

Proof  Consider a 33-tuple x¯=(x 0,x 1,x 2)\overline{x}=(x_0,x_1,x_2) of length 2. Since x¯\overline{x} has length 2, {x 0,x 1}\{x_0,x_1\} and {x 1,x 2}\{x_1,x_2\} are edges of GG. Also, 2,2(x¯)=0\partial_{2,2}(\overline{x})=0 if and only if the shortest path between x 0x_0 and x 2x_2 has length smaller than 22, that is, if removing the required vertex x 1x_1 we obtain a 2-tuple of length 1. This implies that there exists and edge {x 0,x 2}\{x_0,x_2\} and thus a triangle with vertices x 0,x 1,x 2x_0,x_1,x_2.

It is immediate to see that the above holds for all permutations of x¯\overline{x}, which implies that the number of triangles occurring in GG is given by the number of basis elements in the kernel of 2,2\partial_{2,2} divided by the cardinality of the automorphisms group of the triangle D 3D_3.

Proceeding in a similar way, it also possible to show that the number of kk-cliques in GG is upper bounded by Zk!\left\lfloor\frac{Z}{k!}\right\rfloor, where ZZ is the number of basis elements x¯EMC k,k\overline{x} \in EMC_{k,k} such that k,k(x¯)=0\partial_{k,k}(\overline{x})=0.

A vanishing threshold for the first diagonal of EMH of Erdős–Rényi random graphs

Let G=G=(n,p)=G(n,n α)G=G=(n,p)=G(n,n^{-\alpha}) be an Erdős–Rényi graph.

In order to produce a vanishing threshold for EMH k,k(G)EMH_{k,k}(G) we identify what kind of subgraph HH is induced by a cycle in EMH k,k(G)EMH_{k,k}(G) and give an estimate for the occurrences of HH in GG.

Take [x 0,,x k]EMH k,k(G)[x_0,\dots,x_k] \in EMH_{k,k}(G). Then for every i=1,,k1i=1,\dots,k-1 the edge (x i1,x i+1)(x_{i-1},x_{i+1}) exists and the induced subgraph HH is as shown:



























  


  


  


  







  



  





  



  





  





  












Now, the number of edges contained in such graph is k+(k1)k+(k-1) (black edges plus blue edges). Hence, calling a Ha_H the number of automorphisms of HH, the number of copies of HH expected in GG is

N H =(nk+1)a Hp 2k1 n k+1a H(k+1)!n α(12k) =a H(k+1)!n α(12k)+(k+1)n{0, if α>k+12k1 , if 0<α<k+12k1. \begin{aligned} N_H &= \binom{n}{k+1} a_H p^{2k-1} \\ &\sim n^{k+1} \frac{a_H}{(k+1)!} n^{\alpha(1-2k)} \\ &= \frac{a_H}{(k+1)!} n^{\alpha(1-2k)+(k+1)} \xrightarrow{n\to \infty} \begin{cases} 0, \ \text{ if } \ \alpha \gt \frac{k+1}{2k-1} \\ \infty, \ \text{ if }\ 0 \lt \alpha \lt \frac{k+1}{2k-1}. \end{cases} \end{aligned}

The computation above implies the following.

Lemma  Let GG be an Erdős–Rényi graph on nn vertices and set p=n αp=n^{-\alpha}. The first diagonal of the eulerian magnitude homology EMH k,k(G)EMH_{k,k}(G) vanishes for α>k+12k1\alpha \gt \frac{k+1}{2k-1}.

Posted at April 12, 2023 9:34 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3462

19 Comments & 0 Trackbacks

Re: Eulerian Magnitude Homology

Thanks for this post, Giulia!

Sorry about the various formatting glitches when I posted this earlier today. Hopefully they’re all fixed now, but I trust people will let me know if I missed any.

Let me see if I can start to get to grips with this.

When we look at the magnitude homology of a graph, we usually take the kk-chains to be generated by (k+1)(k+1)-tuples of vertices (x 0,,x k)(x_0, \ldots, x_k) where

x 0x 1x k. x_0 \neq x_1 \neq \cdots \neq x_k.

In other words, x ix_i is never equal to x i+1x_{i + 1} — but it could, for instance, be equal to x i+2x_{i + 2}.

You go further, and look at the (k+1)(k + 1)-tuples where all the x 0,,x kx_0, \ldots, x_k are distinct. No backtracking allowed! And these are the Eulerian magnitude chains.

Of course, there are far fewer Eulerian chains than ordinary ones, because the nondegeneracy condition is more stringent. So that should make computations easier.

You then measure the difference between the ordinary and Eulerian magnitude chains, or more exactly the quotient of the former by the latter. And that’s your discriminant magnitude chain group: DMC=MC/EMCDMC = MC/EMC.

The cool thing is, at the homological level, this quotient splits:

MH=EMHDMH. MH = EMH \oplus DMH.

It’s clear from the definitions that DMHDMH is going to be a quotient of MHMH, but the fact that it’s a direct summand is less obvious.

The upshot is that we can split magnitude homology into two parts: essentially, those generated by the chains (x 0,,x k)(x_0, \ldots, x_k) containing no repeats, and those containing some repeats. This is nice!

That’s just about the splitting result so far, without touching the stuff on Erdős–Rényi graphs…

Posted by: Tom Leinster on April 12, 2023 10:18 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

I haven’t understood the splitting result. Is it possible to elaborate?

From the lemma it seems that there is a short exact sequence

0EMH k,(G)ι *MH k,(G)π *DMH k,(G)0. 0 \to EMH_{k,\ell}(G) \xrightarrow{\iota_\ast} MH_{k,\ell}(G) \xrightarrow{\pi_\ast} DMH_{k,\ell}(G) \to 0.

“It follows that” there is a splitting

MH k,(G)EMH k,(G)DMH k,(G). MH_{k,\ell}(G)\cong EMH_{k,\ell}(G) \oplus DMH_{k,\ell}(G).

How does this follow? Is this a canonical splitting?

Unless I’ve confused myself, a classic example of a short exact sequence that doesn’t split is the following.

0×2 /20. 0 \to \mathbb{Z} \xrightarrow{\times 2} \mathbb{Z} \xrightarrow{&nbsp;} \mathbb{Z}/2\mathbb{Z} \to 0.

Posted by: Simon Willerton on April 13, 2023 10:45 AM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

If I thought about all of this correctly, the point is that we can consider a cycle in EMH k,(G)EMH_{k,\ell}(G) as a cycle in MH k,MH_{k,\ell}. Then this gives us a homology class [(x 0,,x k)] EEMH k,(G)[(x_0,\dots,x_k)]_E \in EMH_{k,\ell}(G) and also [(x 0,,x k)]MH k,(G)[(x_0,\dots,x_k)] \in MH_{k,\ell}(G). In these terms, the homomorphism induced by the inclusion is [(x 0,,x k)] Ei *[(x 0,,x k)][(x_0,\dots,x_k)]_E \overset{i_{*}}{\rightarrow} [(x_0,\dots,x_k)], and because of the specific (very rigid) construction it cannot happen that a cycle (x 0,,x k)(x_0,\dots,x_k) which is non-trivial in EMHEMH becomes trivial in MHMH.

Then we define the splitting sequence 0EMH k,(G)i *MH k,(G)coker(i)00 \to EMH_{k,\ell}(G) \overset{i_{*}}{\rightarrow} MH_{k,\ell}(G) \to coker(i) \to 0 and verify that coker(i)DMH k,(G)coker(i) \cong DMH_{k,\ell}(G).

Posted by: Giuliamaria Menara on April 13, 2023 3:22 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Hi Giuliamaria, we might have crossed wires here. I’m willing to believe the lemma (but I haven’t checked it), so you have the short exact sequence. However, I don’t see how you then get the splitting. These are two different things. In general, it does not follow from a short exact sequence of abelian groups

0ABC0 0 \to A \to B \to C \to 0

that there is a splitting

BAC; B \cong A \oplus C;

you would typically need some more structure, for instance having a morphism CBC \to B, in order to deduce the existence of a splitting.

Do you have a morphism DMH k,(G)MH k,(G)DMH_{k,\ell}(G) \to MH_{k,\ell}(G)?

Another situation in which a short exact sequence leads to a splitting is when you are talking about vector spaces rather than abelian groups. You didn’t define precisely what you meant by the homology groups: if you were working with, say, rational coefficients then the sequence would split, though it wouldn’t necessarily split canonically.

Posted by: Simon Willerton on April 13, 2023 5:00 PM | Permalink | Reply to this

Hello Simon. As a matter of fact, at an initial stage I was working with \mathbb{Q} coefficients (to kill torsion) and I first came to the splitting result in the context of vector spaces (and you are right, I should have specified this).

Although, even in the case of abelian groups the result does hold. Indeed, from the construction of EMH k,EMH_{k,\ell} you get that the kernel of i i_{\star} is trivial. Then i i_{\star} is injective, so it admits a left inverse, and by the splitting lemma this is enough for the sequence to split.

Posted by: Giuliamaria Menara on April 14, 2023 9:52 AM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Then i *i_\ast is injective, so it admits a left inverse

I don’t follow this step. The map i *i_\ast is an injective homomorphism of abelian groups, but that by itself doesn’t imply it admits a left inverse. (E.g. multiplication by 22 is an injective homomorphism of abelian groups \mathbb{Z} \to \mathbb{Z}, but has no left inverse.) What’s going on?

Posted by: Tom Leinster on April 14, 2023 3:50 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

I was really sloppy in giving this argument. I am going to construct a morphism j *:MH k,EMH k,j_{*}: MH_{k,\ell} \to EMH_{k,\ell} such that its composition with i i_{\star} is the identity on EMH k,EMH_{k,\ell}.

First, notice that since the basis of EMC k,EMC_{k,\ell} is a subset of the basis of MC k,MC_{k,\ell} and because the boundary map of the eulerian magnitude chain is defined as just a restriction of the boundary map on the magnitude chain MC *,MC_{*,\ell}, the an element [x¯] EEMH k,[\bar{x}]_E \in EMH_{k,\ell} can be mapped by i i_{\star} to the element [x¯]MH k,[\bar{x}] \in MH_{k,\ell} with the same representative and it never happens that a non-trivial cycle in EMHEMH becomes trivial in MHMH.

Then, consider the morphism (πϕ):ker( k,(MC k,))EMH k,(\pi \circ \phi) : \ker(\partial_{k,\ell}(MC_{k,\ell})) \to EMH_{k,\ell}. The first map ϕ:ker( k,(MC k,))ker( k,(EMC k,))\phi : \ker(\partial_{k,\ell}(MC_{k,\ell})) \to \ker(\partial_{k,\ell}(EMC_{k,\ell})) sends a basis element x¯\bar{x} of ker( k,(MC k,))\ker(\partial_{k,\ell}(MC_{k,\ell})) to itself if x¯ker( k,(EMC k,))\bar{x} \in \ker(\partial_{k,\ell}(EMC_{k,\ell})) (i.e. if all vertices in x¯\bar{x} are different) and to the identity otherwise. The second map is the quotient π:ker( k,(EMC k,))ker( k,(EMC k,))im( k+1,(EMC k+1,))=EMH k,\pi: \ker(\partial_{k,\ell}(EMC_{k,\ell})) \to \frac{\ker(\partial_{k,\ell}(EMC_{k,\ell}))}{im(\partial_{k+1,\ell}(EMC_{k+1,\ell}))} = EMH_{k,\ell}.

Now, since im( k+1,(MC k+1,))ker(πϕ)im(\partial_{k+1,\ell}(MC_{k+1,\ell})) \subseteq \ker(\pi \circ \phi) then the morphism (πϕ)(\pi \circ \phi) factors through ker( k,(MC k,))im( k+1,(MC k+1,))=MH k,\frac{\ker(\partial_{k,\ell}(MC_{k,\ell}))}{im(\partial_{k+1,\ell}(MC_{k+1,\ell}))} = MH_{k,\ell}, providing us with a morphism j *:MH k,EMH k,j_{*}: MH_{k,\ell} \to EMH_{k,\ell}.

With this construction, j *i j_{*} \circ i_{\star} is the identity on EMH k,EMH_{k,\ell}.

Posted by: Giuliamaria Menara on April 17, 2023 12:05 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Thanks for expanding. I have another question!

You said

First, notice that since the basis of EMC k,\mathrm{EMC}_{k,\ell} is a subset of the basis of MC k,\mathrm{MC}_{k,\ell} and because the boundary map of the eulerian magnitude chain is defined as just a restriction of the boundary map on the magnitude chain [… then] it never happens that a non-trivial cycle in EMH becomes trivial in MH.

I don’t see how that follows. You’re saying that it is never the case that the boundary of a non-Eulerian chain is Eulerian. That may be true but it doesn’t seem to follow from the first half of the sentence.

Consider the chain complex C\mathrm{C} generated in degree one by aa and in degree two by bb, with d(b)=a\mathrm{d}(b) = a and d(a)=0\mathrm{d}(a) = 0. Take EC\mathrm{EC} to be the sub-chain complex generated by aa with d(a)=0\mathrm{d}(a) = 0. This seems to satisfy the first half of your sentence. But it doesn’t seem to satisfy the conclusion of the sentence as [a][a] is non-trivial in the homology of EC\mathrm{EC} but trivial when mapped into the homology of C\mathrm{C}.

Posted by: Simon Willerton on April 17, 2023 1:52 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Given the splitting result, we should be now able to define the Eulerian magnitude and discriminant magnitude of a graph as the graded Euler characteristics of EMH(G)EMH(G) and DMH(G)DMH(G) respectively, with the usual magnitude being the sum of Eulerian magnitude and discriminant magnitude, right?

I wonder if there is a more direct, decategorified way of defining those. Not that I see any immediate motivation for doing so, I’m just trying to clarify what’s going on here for myself.

Posted by: Mark Meckes on April 14, 2023 3:20 PM | Permalink | Reply to this

Just a comment on the formatting:

Posted by: Jacques Distler on April 13, 2023 5:26 AM | Permalink | PGP Sig | Reply to this

Re: Just a comment on the formatting:

Aha, thanks, Jacques. Evidently I missed a trick: I could have just included the tikz code that Giuliamaria sent me, rather than using an image file. I’ve made this improvement now. Much appreciated.

Posted by: Tom Leinster on April 13, 2023 11:28 PM | Permalink | Reply to this

Re: Just a comment on the formatting:

Evidently I missed a trick: I could have just included the tikz code that Giuliamaria sent me, rather than using an image file.

Right. And, as you can see, it can also be used in comments.

The only non-obvious thing is that, if you have a \usetikzlibrary{...} command (which would normally be placed in the header of your LaTeX file), you should embed it in the tikz code instead.

Posted by: Jacques Distler on April 14, 2023 3:06 AM | Permalink | PGP Sig | Reply to this

Re: Eulerian Magnitude Homology

Thanks, this looks interesting.

It would be nice to see more computations and maybe I can help with that. This is an invitation for anyone interest in this to lend a hand. The SageMath code for computing graph magnitude homology has not been as obviously available as it might have been (it was buried in the arxiv submission) so I’ve just uploaded a jupyter notebook to GitHub.

I don’t have the time or energy to modify this to compute Eulerian magnitude homology but it shouldn’t be difficult and it should be fun! However, be aware that the code was written quite a while ago and I would probably write it neater now.

Now for some confessions of ignorance on the latest “best practice” for scientific code.

  1. I don’t know if a jupyter notebook is the best format or not but it looks easier to read than straight code.
  2. I don’t know if GitHub is the right place for the code, but it was a quick and easy place to put it.
  3. I don’t know much about GitHub conventions, so I might not have the repository set up sensibly.

Please let me know if you are more knowledgeable in such things and can help me improve the availability of the code.

Posted by: Simon Willerton on April 13, 2023 10:19 AM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

I coded MH up in MATLAB a few years back and am doing it again from scratch on my personal time. I plan to incorporate EMH (which BTW Giulia this is lovely). Stay tuned.

NB. Because for symmetric dissimilarities blurred MH is basically Vietoris-Rips, it’s particularly interesting to consider asymmetric dissimilarities. For example I’ve computed the MH of DAGs that correspond to neural network architectures and it’s considerably richer than path homology, and also more scalable because of the direct sum decomposition on sources and targets. EMH should of course help further with scalability. I imagine there are lots of applications to cyber and connectome data in the directed arena.

Posted by: Steve Huntsman on April 13, 2023 1:13 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Adrian Doña Mateo (currently doing a PhD with me) did unearth the Sage code from your arXiv submission, and got it working, but I think he said he first had to spend a while updating it so that it worked with the current version of Python. Presumably the code you just put on GitHub does have that virtue, even given your other humble disclaimers :-)

Posted by: Tom Leinster on April 13, 2023 11:31 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Ah, yes, I forgot about the changes, thanks for mentioning it.

Last year, Emily Roff (previously doing a PhD with you) pointed out to me, while I was visiting, that she couldn’t get the code to work with the current version of SageMath. This was mainly because of a big switch in SageMath 9 in which they moved to using Python 3. A significant difference between Python 2 and Python 3 is that in one you can type print a and in the other you need to type print(a).

Anyway, I fixed all the print statements and made some very minor changes to the code so Emily could run it directly in SageMath. The version I’ve put on GitHub is just a slightly prettier version in that I broke parts of it into notebook cells.

Posted by: Simon Willerton on April 14, 2023 8:57 AM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

I’m trying to understand the proof of lemma for the splitting result. In the post it says the following.

k+1(x 0,,x k+1)]={[y 0,,y k], if y iy j for all i,j, [0], otherwise.\partial_{k+1}(x_0,\dots,x_{k+1})]= \begin{cases} [y_0,\dots,y_k], \ \text{ if }\ y_i\neq y_j \ \text{ for all }\ i,j,\\ [0], \text{ otherwise.} \end{cases}

The left-hand side seems to have a couple of typos. Are you missing a [[ and an \ell?

As for the right-hand side, I don’t think you’ve said what y iy_i is. Can you say what y iy_i is?

Also, does [] N[]_N mean the same as [] E[]_E?

Posted by: Simon Willerton on April 17, 2023 1:19 PM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Hello Simon, sorry for the late reply. Yes there are a few typos: the missing [[ and \ell, and [] N[]_N instead of [] E[]_E.

Posted by: Giuliamaria Menara on April 21, 2023 8:45 AM | Permalink | Reply to this

Re: Eulerian Magnitude Homology

Also, y iy_i is a vertex and [y 0,...y k][y_0,...y_k] is an element in EMH k,EMH_{k,\ell} - I just didn’t want to use the same vertex notation for elements in DMHDMH and EMHEMH.

Posted by: Giuliamaria Menara on April 21, 2023 10:10 AM | Permalink | Reply to this

Post a New Comment