Take the 2-minute tour ×

In 2005, prof. Emil Skoldberg developed a theory, similar to Forman's Discrete Morse Theory, but suited for arbitrary based chain complexes, in his Morse Theory from an algebraic viewpoint. I'm going through the paper and am having some difficulties. I'd be most grateful for an answer to my question 2 below.

Question 1: On p. 116, in the definition of a Morse matching, there is written:

We call a partial matching $M$ on the digraph $G_K$ a Morse matching if for each edge $\alpha\to\beta\in M$ the corresponding component $d_{\beta,\alpha}$ is an isomorphism, and furthermore, there is a well-founded partial order $\preceq$ on each $I_n$ such that $\alpha\succ\gamma$ whenever there is a path $\alpha^{(n)}\to\beta\to\gamma^{(n)}$ in $G^M_K$.

Is $\preceq$ defined by "exists a path $\alpha^{(n)}\to\beta\to\gamma^{(n)}$ in $G^M_K$", or is that just a necessary condition on $\preceq$? More precisely, the word "whenever" in the above quote, is that meant as $\Leftarrow$ or $\Leftrightarrow$?

Edit: Which definition is the right one (are all of them ok?): for $\alpha,\beta\in I_n$, we let:

  1. $\alpha\succeq\beta$ iff there exists a directed path in $G_K^M$ from $\alpha$ to $\beta$;
  2. $\alpha\succeq\beta$ iff there exists a directed path in $G_K^M$ from $\alpha$ to $\beta$ with vertices in $I_{n+1}\cup I_n$;
  3. $\alpha\succeq\beta$ iff there exists a directed path in $G_K^M$ from $\alpha$ to $\beta$ with vertices in $I_n\cup I_{n-1}$;

Question 2: In the proof of Theorem 2 on p. 121. How do Lemmas 3 and 4 imply that for $x\in K_\alpha$ with $\alpha \in M_n^0$ there holds the equality $$\rho\pi(x)=x?$$ We have $\rho\pi(x)=\rho(x)-\rho\phi d(x)-\rho d\phi(x)$. Since $x \in C_n$ and $\rho$ is a projection, we have $\rho(x)=x$. By Lemma 3, we have $d\phi(x)= 0$. By Lemma 4, we have $\phi d(x) = \sum_{\beta\preceq\alpha}y_\beta=:(\ast)$ for some $y_\beta \in K_\beta$, but why is $(\ast)=0$ when $\alpha$ is critical?

Question 3: In Corollary 3, in the first sum, $\sigma$ ranges through $M^0_{n-1}$, right?

Question 4: If I understand correctly, the proof of Theorem 2 shows that if $\pi(K)$ has the induced boundary operator $d|_{\pi(K)}$ and $C$ has the operator $\tilde{d} := \rho(d-d\phi d) = \rho d \pi$, then the maps $\pi: C\longrightarrow \pi(C)=\pi(K)$ and $p: \pi(K)=\pi(C)\longrightarrow C$ are inverse to each other. Furthermore, $\pi\tilde{d} = \pi\rho(d-d\phi d) = d-d\phi d = d(\mathrm{id}-\phi d-d\phi) = d\phi$, so $\pi$ is a chain map. However, $\tilde{d}\rho = \rho(d-d\phi d)\rho = \rho d\rho-\rho d\phi d\rho \overset{???}{=} \rho d$.

Question 5: In general, there does not hold $\tilde{d}|_{\pi(K)}=d|_{\pi(K)}$, right?

Question 6: In the proof of Corollary 3, by Lemma 5 we have $\tilde{d}(x)$ $=$ $\rho(d-d\phi d)(x)$ $=$ $\rho(\sum_{\alpha\to\beta}d_{\beta\alpha}(x)-d\phi\sum_{\alpha\to\beta}d_{\beta\alpha}(x))$ $=$ $\rho\sum_{\alpha\to\beta}(d_{\beta\alpha}(x)-d\phi d_{\beta\alpha}(x))$ $=$ $\rho\sum_{\alpha\to\beta}(d_{\beta\alpha}(x)-d\sum_{\alpha'\in I_n,\gamma\in\Gamma_{\alpha',\beta}} m(\gamma)d_{\beta\alpha}(x))$. How do I continue to get $\rho\sum_{\sigma\in I_{n-1},\gamma\in\Gamma_{\sigma,\alpha}} m(\gamma)(x)$?

P.S. I might later add additional questions regarding p.116-122.

share|improve this question
Also on math.stackexchange math.stackexchange.com/q/278461 –  Martin Jan 15 '13 at 7:47
It's considered rude to ask a question on both places simultaneously, since it means two people could end up doing the same work at both places. –  arsmath Jan 16 '13 at 12:10
@arsmath: I first asked on math.stackexchange, with no intention of asking here, but then there were no responses, and furthermore, there were votes to close the question down, so I became pessimistic about getting an answer there, and I asked here. Besides, each question has a link to the other, so I don't see where the problem is. –  Leon Lampret Jan 16 '13 at 22:18
Such an algebraic discrete Morse theory was invented in the eighties by Ken Brown to prove the Squire-Annick-Grove theorem. –  Benjamin Steinberg Feb 7 '13 at 1:23
See The geometry of rewriting systems: A proof of the Anick-Groves-Squier theorem. Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), 137–163, Math. Sci. Res. Inst. Publ., 23, Springer, New York, 1992. His collapsing scheme is exactly equivalent to the acyclic matching formulation of Forman's approach and he develops an algebraic version to prove a monoid with a finite complete rewriting system is FP_infinity. He does it just for monoid algebras I believe but D Cohen later generalized it. –  Benjamin Steinberg Feb 7 '13 at 1:27
add comment

2 Answers

up vote 4 down vote accepted

It's always nice to see people working on discrete Morse theory.

Answer 1

It is an "if and only if". Meaning: the partial order $\prec$ is defined by $\alpha \prec \gamma$ if and only if $\gamma$ precedes $\alpha$ in a path of the matching. The idea goes back to Forman's "Morse theory for cell complexes" where it is not explicitly stated as a partial order. I think the origins of the partial order are in Chari's reformulation of discrete Morse functions as acyclic matchings, see page 7 of "On discrete Morse functions and combinatorial decompositions".

Regarding your edited version of this question: the degrees of the vertices in the path don't really matter. If $\alpha, \beta$ are both in $I_n$ then $\alpha \succeq \beta$ if there is an alternating path from $\alpha$ to $\beta$ of either the type $(n,n-1,\ldots,n)$ or the type $(n,n+1,\ldots,n)$: in either case, you have $\alpha \succeq \beta$. In the first case, you will have $\alpha, \beta \in M^- \cup M^0$ and in the second case you will have $\alpha, \beta \in M^+ \cup M^0$. In general, this partial order might relate $\alpha$ and $\beta$ lying across different $I_n$'s too.

Answer 2

As you noted, $\phi(dx_\alpha) = \sum_{\beta \prec \alpha}y_\beta$ and your question asks why this quantity should be trivial. In fact, it is not trivial in general, but its image under $\rho$ is trivial (which is all you need): by definition the image of $\phi$ is never critical, so $\rho\circ\phi$ is trivial.

Answer 3

Yes, $\sigma$ ranges over all critical cells of dimension $(n-1)$. This is a common problem with notation: I suspect that the author intended to specify the multiplicity $m(\gamma:\sigma\to\alpha)$ when writing $m(\gamma)$ where $\gamma$ is a path of the matching. In this case, one should define $m(\gamma) = 0$ whenever the source cell $\sigma$ is non-critical, which allows you to sum over arbitrary cells.

Answer 4

There is a typo at the end of your calculation: one has $\pi\tilde{d} = d\pi$ instead of $d\phi$. If you already accept that $\rho$ and $\pi$ are inverses, then there is really no trouble: $$\tilde{d}\rho = (\rho d \pi) \rho = \rho d(\pi \rho) = \rho d $$ Maybe you mean to ask some other question here: even the proof that $\pi$ is a chain map (which you worked out in your question) follows easily by a similar argument if you accept that $\rho$ is its inverse.

Answer 5

You are right, this is not true in general: the image of $\tilde{d}$ must be critical (that is, in the span of $M^0$) whereas there is no such requirement on the image of $d$ restricted to $\pi(K)$.

Answer 6

The result follows from recursive application of Lemma 5. Instead the calculation that you have performed so far, look at $(d - d\phi d)x$ as $(1 - d \phi) (dx)$ and write $dx$ out as a linear combination of $(n-1)$-dimensional cells. By Lemma 3, only the cells from $M^-$ will contribute. Now apply Lemma 5 to each piece of this combination...

share|improve this answer
Thank you very much, this helped me a lot. I'm aware that there is an analogous theory by Jollenbeck and Welker, though the fact that the results are stated in lesser generality has put me off from reading it (though I will, in the near future). Why does Jollenbeck&Welker, Minimal Resolutions via Algebraic Discrete Morse Theory, assume that all modules are free of rank $1$? Why does Kozlov, Combinatorial Algebraic Topology §11.3, assume that $R$ is commutative and modules are free of finite rank? Judging by the results from Skoldberg's article, those are all unnecessary assumptions. –  Leon Lampret Jan 16 '13 at 22:30
Leon, regarding the restrictions of Kozlov and J-W: if you are interested in actual computation of homology (they are) then you need at least a pid so that you can put the matrices in smith normal form. Skoldberg also has chain complexes with a fixed basis of cells (because after all you have to impose the acyclic matching on these cells). More importantly, commutativity of the coefficient ring enables you to write the multiplicity of a path (and hence the morse boundary operator) independent of the cell ordering. I will answer your new questions soon after looking at the notation in skolberg –  Vidit Nanda Jan 28 '13 at 15:27
@Vel Nias: It wasn't until now that I managed to go through the article and your answer. Thank you, much obliged! –  Leon Lampret Mar 19 '13 at 2:37
@Leon: no worries, glad to help. I wasn't kidding in my answer, it is really cool to see people (especially grad students) seriously studying algebraic or discrete Morse theory! –  Vidit Nanda Mar 19 '13 at 3:45
add comment

It may be useful to note in relation to the work of Forman that his notion of discrete vector field on a complex is equivalent to the notion of marked cone complex in David W. Jones' 1984 PhD thesis on Poly T-complexes available from here, also published as "A general theory of polyhedral sets and the corresponding $T$-complexes" Dissertationes Math. (Rozprawy Mat.) 266 (1988) 110.

So it would be interesting if this is related also to Skoldberg's work.

share|improve this answer
add comment

Your Answer


