Morse-Maxwell Theory for Directed Acyclic Graph

Introduction

Let a graph carry a height function with distinct values, and orient each edge from its higher endpoint to its lower endpoint. A vertex may then reach one or several local minima. The vertices that reach at least two minima form the basin boundary. Repeating this operation, and its analogue for maxima, gives two boundary hierarchies. The Maxwell graph retains the extrema of all their levels and the reachability relations between them. We seek Morse inequalities associated with this construction.

Maxwell’s On Hills and Dales [8] describes regions of depression and elevation and the lines separating them. His counting arguments allow several topographic events to occur at one point. The graph construction follows this viewpoint by using all descending paths; related constructions appear in [12, 13]. The number of extrema at each boundary level alone, however, is insufficient for Morse inequalities. The examples below show that local multiplicities are needed and that the original Maxwell reduction can change homology.

Let $D$ be a finite directed acyclic graph. Reachability gives a partial order $P(D)$: we write $v \leq u$ when a directed path leads from $u$ to $v$. Let $K(D) = \Delta P(D)$ be the simplicial complex whose simplices are the nonempty chains of this order. Fix a field $\mathbb{F}$. For each vertex $v$, its lower order link $L^{-}(v)$ is the order complex of its strict descendants. The local contribution in degree $r$ is

We use $\widetilde{H}_{-1}(\varnothing;\mathbb{F}) = \mathbb{F}$. Thus a sink contributes one generator in degree zero. A vertex whose lower link has three contractible components contributes two generators in degree one. Define the Morse numbers and Betti numbers by

Reversing all arrows gives the ascending inequalities. To preserve these local groups under reduction, we retain the extrema of both boundary hierarchies and every vertex with nonzero lower or upper local homology. We call the resulting graph the homological Maxwell graph. It has the same boundary levels, local groups, and Betti numbers as $D$. In particular, (1) can be computed entirely on the reduced graph.

The homology in (1) is reachability homology [6]. For a DAG, it is also path homology of the transitive closure [11]. It can differ from path homology of $D$ [5] and from singular simplicial homology of the original digraph [3].

Forman’s discrete gradient [4] pairs incident cells of consecutive dimensions, with each cell in at most one pair and no nontrivial closed gradient paths. The unpaired cells are critical; counting gradient paths with signs gives the boundary of the Morse complex. Lin, Wang, and Yau [7] adapt this approach to digraphs, using a Morse function that extends to the transitive closure and a gradient preserving the path chain complex of the original digraph. Their reduction then preserves path homology.

Our construction uses all descending paths determined by the given orientation, without choosing a matching or an auxiliary Morse function. The local homology at a vertex determines its contribution, which may have multiplicity greater than one or occur in several degrees. In smooth Morse theory [9], a nondegenerate critical point of index $r$ contributes just one local generator in degree $r$. The proof of (2) uses the standard homological argument behind Morse inequalities; compare [10, 14]. The additional task here is to preserve the two Maxwell hierarchies and the local groups under reduction. The deletion argument is related to reductions of finite posets [2].

§ 5 explains what changes for path homology. Its Betti numbers do not give Morse inequalities for the unweighted Maxwell level counts $|B_j|$. A three-leaf star gives an obstruction for any homology with the usual $H_0$. Nor can path Betti numbers simply replace $\beta_r$ in (2): the subdivided diamond considered there has $m_1 = 0$ but first path Betti number one. We obtain path-homological Morse inequalities for every finite DAG by assigning each vertex the relative path homology of adding it to its strict descendants. The sums of these local dimensions are the appropriate Morse numbers. For the unchanged Maxwell graph, its reachability homology similarly gives inequalities with multiplicities computed on that graph. These chain constructions do not yet give a general graph reduction preserving both path homology and the Maxwell hierarchies.

Definitions and proofs occupy § 2 and § 3; the latter also gives a Morse complex and computational bounds. § 4 contains the examples, including a six-vertex graph with $\beta_2 = 1$.

Definitions

Directed graphs and their order complexes

Throughout, $D = (V, A)$ is a finite directed acyclic graph (DAG), without loops or parallel arrows. We use $u \leadsto v$ for reachability, allowing a path of length zero. A sink has no outgoing arrow and a source has no incoming arrow. The opposite graph $D^{\mathrm{op}}$ reverses all arrows. A height function is a function $f: V \to\mathbb{R}$ strictly decreasing on arrows. Every DAG admits a height function. Different choices give the same construction, since only reachability is used.

For example, $w < v < u$ determines a triangle in $K(D)$, even if $u \to w$ is not an arrow of $D$. Thus $K(D)$ is not generally the one-dimensional underlying graph. Throughout the paper homology has coefficients in the fixed field $\mathbb{F}$. We use ordinary homology for $K(D)$ and augmented reduced homology for local links. The empty complex has $\widetilde{H}_{-1} = \mathbb{F}$ and no other reduced homology. A complex is acyclic over $\mathbb{F}$ if all its augmented reduced homology groups vanish; in particular it is nonempty.

Basins, hills, and the Maxwell graph

For $U \subseteq V$, let $D[U]$ denote the induced directed subgraph.

Local Morse data

For $v \in P$, let $P_{<v}$ and $P_{>v}$ denote its strict lower and upper sets.

Definition 2.5. The lower and upper order links, local groups, and multiplicities are

A vertex is descending critical if some $\mu_r^-(v)$ is nonzero, and ascending critical if some $\mu_r^+(v)$ is nonzero. Otherwise it is regular in the corresponding direction. Write $C^-(D)$ and $C^+(D)$ for these two critical sets.

The links contain all strict descendants or ancestors. Regularity requires every local group to vanish; a zero alternating sum of their dimensions is insufficient. We call the degree $r$ of a local generator its Morse degree. It need not agree with the boundary level of the vertex.

The descending Morse numbers are $m_r(D)$ from (1). The ascending ones are

The order complexes of $P$ and its opposite have the same simplices, so they have the same Betti numbers.

The homological Maxwell graph

Definition 2.6. The homological essential set and homological Maxwell graph are

The graph retains the labels $B_j$, $H_j$ and the local groups $E_r^\pm(v)$ at its vertices.

Some vertices are retained only because they belong to $W(D)$ and may have zero local groups in both directions. The set $S_{\mathbb{F}}(D)$ can depend on the coefficient field.

Vertices outside $S_{\mathbb{F}}(D)$ contribute zero to $m_r$ and $m_r^+$. Proposition 3.5 shows that the local groups at retained vertices can also be computed in the restricted order $P(D)|_{S_{\mathbb{F}}(D)}$.

Proofs

The Morse inequalities

Choose a linear extension $v_1,\ldots,v_n$ of $P(D)$ in which strict lower elements appear first. Set

At step $i$ we attach all chains whose greatest element is $v_i$.

Proof of Theorem 1.1. Let $a_{i,r}$ be the rank of the connecting map

Here $a_{i,0}=0$ (ordinary $H_{-1}=0$). Set $b_r(K_i)=\dim H_r(K_i)$. Exactness gives

Summing over the vertices, with $A_r=\sum_i a_{i,r}$, gives

Since each $A_r$ is a sum of ranks, the weak inequalities follow. Alternating sums cancel $A_1,\ldots,A_q$, while $A_0=0$, giving

All groups vanish in high degrees, giving eventual equality.

For the polynomial form of the inequalities, write $m_D(t)=\sum_r m_r(D)t^r$ and $P_D(t)=\sum_r\beta_r(D)t^r$.

Preservation under the Maxwell reduction

We first prove that retaining $W(D)$ preserves both boundary hierarchies, and then show that regular vertices can be deleted without changing the local homology groups.

Proof. For a simplicial complex $K$ and vertex $z$,

This follows by taking the cone on the link modulo its base. For an order complex,

Over a field, a join with an acyclic factor is acyclic: the augmented join formula is

The indices include $-1$. With our augmented convention, $A*\varnothing=A$, and the term $j=-1$ gives $\widetilde{H}_k(A*\varnothing)\cong\widetilde{H}_k(A)$. The relative groups in (5) vanish, proving preservation of the homology of the full complex.

The lower link at a remaining vertex $v$ changes only if $z<v$. Inside $L^{-}(v)$, the link of $z$ is

Its first factor is acyclic. The same relative argument proves preservation of the reduced homology of $L^{-}(v)$. Reversing the order proves the upper statement.

Proof. Delete the vertices outside $S$ one at a time. They are initially regular in both directions. At each step, Lemma 3.4 preserves the global homology and all remaining local groups. Thus every vertex still to be deleted is regular in the current restricted order, and induction gives the homology isomorphisms. The boundary levels are preserved by Lemma 3.3, since $W\subseteq S$.

Proof. The vertex set and its Hasse diagram are defined without choices. Proposition 3.5 preserves $W$, both critical sets, and their local groups. Their union in the reduced graph is therefore exactly $S$. Taking its Hasse diagram again changes nothing. Vertices outside $S$ contribute zero to the Morse sums.

An order ideal contains all lower elements of each of its vertices; an order filter contains all upper elements.

Proof. For an ideal, delete $U\setminus S$ with larger vertices first. When $z$ is deleted, all of its original lower elements are still present, so its lower link is the original acyclic $L^{-}(z)$. Apply Lemma 3.4 at each step. For a filter use smaller vertices first and upper links. For $U_1\subseteq U_2$, both composites $K(S\cap U_1)\to K(U_2)$ are the same inclusion. This proves naturality.

In particular, for a height function $f$ decreasing on arrows, the sets $\{f \le t\}$ are ideals and $\{f \ge t\}$ are filters. Hence the reduced and original order complexes have isomorphic sublevel and superlevel persistent homology. The conclusion is a homology isomorphism; acyclic links need not give homotopy equivalences.

A Morse chain complex

The local groups form the chain groups of a Morse complex.

Proof. Group simplices according to their greatest vertex. Their boundary matrix is triangular with respect to the poset labels: a face has the same greatest vertex or a smaller one. The diagonal block at $v$ is the relative complex of $(v * L^-(v), L^-(v))$.

Over a field, choose bases in each diagonal block separating its homology representatives from elementary acyclic pairs. A pair $a,b$ has consecutive degrees, the same vertex label, and a nonzero coefficient $c$ of $b$ in $da$. It can be cancelled in the full complex. Replace $b$ by $c^{-1}da$ and subtract suitable multiples of $a$ from the other generators of its degree to remove their new $b$ coefficient. The equation $d^2=0$ then splits off this two-term acyclic summand. This is a chain homotopy equivalence.

Cancellation preserves the order condition. A new matrix entry from label $w$ to label $u$ can only factor through the cancelled label $v$, so $u \le v \le w$. In particular no other diagonal block changes. Cancel all the acyclic pairs. The surviving graded space at $v$ is $E_*^-(v)$, and the remaining differential strictly lowers its vertex label. Every vertex outside $\mathrm{SF}(D)$ has zero local groups, giving the displayed direct sum.

The basis choices affect the differential but not the numbers $m_r$. Writing $d_r:C_r \to C_{r-1}$ gives

Coefficients may connect vertices separated by several cover arrows. This differential is therefore not generally the incidence matrix of the reduced graph viewed as a one-dimensional complex. Reversing the order gives an ascending Morse complex.

First boundary levels and subdivision

Proof. In the first case the unique sink is a least element of the lower order, so its complex is a cone. In the second case every strict descendant of $v$ lies outside the first basin boundary: otherwise predecessor closure would contradict $v \in\operatorname{Sink}(\Gamma_B(D))$. Each descendant therefore reaches exactly one sink. Partition them by this sink. There are $k$ nonempty parts, each with a least element, and elements of different parts are incomparable. The lower link is a disjoint union of $k$ cones.

The proposition applies within each boundary stage. The groups computed there may differ from the local groups in the original order.

Proof. Transitive arrows do not change reachability. For a single subdivision $u \to x \to v$, the strict lower set of $x$ has greatest element $v$, and its strict upper set has least element $u$. Both order links are cones. Deleting $x$ recovers the original order, and Lemma 3.4 preserves all old local groups.

The vertex $x$ reaches the same sinks as $v$. Inductively, in every descending stage containing $x$, the vertex $v$ is present and their membership at the next step agrees. Thus $x$ is never a stage sink. The dual statement uses $u$ and the ascending stages. All old levels are unchanged, so $x$ belongs to neither $W$ nor $C^{-} \cup C^{+}$. Iterate for a longer subdivision.

Computing the construction

Let $n = |V|$, $m = |A|$, and let $R$ be the number of nonempty chains of $P(D)$.

The boundary hierarchy can be computed by propagating at most two distinct reachable-sink identifiers per vertex in reverse topological order. One identifier means a unique reachable sink; two suffice to detect ambiguity. Repeat on the retained boundary, and reverse arrows for the hill hierarchy. Each stage costs $O(n_j + m_j)$, and there are at most $n$ stages in each direction. The total is $O(n(n + m))$ time with $O(n + m)$ working space when stages are stored by exit labels.

Reachability itself can be computed in $O(n(n + m))$ time by a search from each vertex. Once the order complex is listed, dense boundary-rank computations give a coarse bound of $O(nR^3)$ field operations for all lower and upper local groups, treating them one at a time, with $O(R^2 + n^2)$ storage. The cancellation procedure in Proposition 3.8 takes at most $R/2$ steps, each with $O(R^2)$ matrix updates, hence $O(R^3)$ field operations.

After $S_F(D)$ is known, the Hasse diagram on it can be obtained in $O(|S_F(D)|(n + m))$ time. For each retained $u$, scan its retained descendants with larger elements first. Select an uncovered $v$ as a cover of $u$, then mark $v$ and all its descendants. Every noncover is marked by a preceding cover, and a cover cannot be marked by a different retained element without an intermediate vertex. Sharing the marking set among these searches gives $O(n + m)$ work per $u$.

These bounds describe direct implementations. Since a total order has $R = 2^n - 1$, enumerating the order complex can already require exponential time. Recognizing conical links and using sparse matrices or cancellations can reduce the computation. Over $\mathbb{Q}$, the bounds above count field operations rather than bit operations.

Examples

We compute the descending Morse numbers; reversing arrows gives the ascending ones. In each example the identity $m_D(t) - P_D(t) = (1 + t)Q_D(t)$, with $Q_D(t)$ having nonnegative coefficients, verifies all the Morse inequalities.

A three-leaf star

Let $D$ have arrows $v \to a, v \to b, v \to c$; see Figure 1(a). The sinks $a,b,c$ each contribute $\mu_0 = 1$. The lower link of $v$ is three isolated points, so $\mu_1(v) = 2$. All vertices are retained:

The inequalities read

Equivalently, $m_D(t)-P_D(t)=2+2t=2(1+t)$.

Take $C_0=\mathbb{F}\langle a,b,c\rangle$ and two generators $e_1,e_2$ at $v$ in degree one, with

The boundary has rank two. Adding $v$ joins three components into one, and the multiplicity two counts the two independent mergers.

A directed bipartite graph

Take sources $u,v$, sinks $a,b$, and all four arrows from a source to a sink, as in Figure 1(b). There are no directed paths of length two, so the order complex is the four-cycle itself. Each source has a two-point lower link. Thus

The strong inequalities are $2\ge1$ and $2-2=1-1$. The polynomial difference is $1+t$.

A Morse complex has degree-one generators $e_u,e_v$ with $de_u=de_v=b-a$. Its boundary has rank one, and $e_u-e_v$ generates $H_1$. In the basis $e_v,e_u-e_v$, the first generator joins components and the second represents the cycle.

More generally, orient $K_{p,q}$ from its $p$ sources to its $q$ sinks, where $p,q\ge2$. All vertices are essential and retained. Each source has a lower link consisting of $q$ points, giving

Hence

For $K_{3,4}$ this gives $(m_0,m_1)=(4,9)$ and $\beta=(1,6)$. There are only three vertices in $B_1$, so unweighted level counts would fail even the weak degree-one inequality.

The diamond

Let the arrows be $a\to b$, $a\to c$, $b\to d$, $c\to d$. There is one source and one sink. The first basin and hill boundaries are empty, and $W=\{a,d\}$. Every nonsink has a conical lower link with least element $d$; every nonsource has a conical upper link with greatest element $a$. Thus $S_{\mathrm{F}}(D)=\{a,d\}$ as well.

The full order complex consists of the two triangles $abd$ and $acd$ joined along their common edge $ad$. This edge is present in the order complex because $a$ reaches $d$. The complex is a disc, although the underlying one-dimensional graph is a circle. Only $d$ contributes to the descending Morse numbers:

All Morse inequalities are equalities.

A six-vertex graph with second homology

Arrange six vertices in three pairs $\{a_1,a_2\}$, $\{b_1,b_2\}$, $\{c_1,c_2\}$. Include all four arrows from the $a$-pair to the $b$-pair and all four from the $b$-pair to the $c$-pair; see Figure 3. The descending levels are the $c$-, $b$-, and $a$-pairs, respectively, and every vertex is retained.

Each $c_i$ is a sink. The lower link of each $b_i$ is the two-point set $\{c_1,c_2\}$. The lower link of each $a_i$ is the four-cycle on the $b$- and $c$-pairs. Consequently

A chain contains at most one vertex from each pair, and any such selection is a chain. Therefore

The strong inequalities are

The polynomial calculation is

Choose generators $z_1,z_2$ in degree two, $e_1,e_2$ in degree one, and $c_1,c_2$ in degree zero. One choice of differential is

Both maps have rank one and their composition is zero. Thus $H_0 \cong\mathbb{F}$, $H_1 = 0$, and $H_2 = \mathbb{F}\langle z_1-z_2\rangle$, giving the stated Betti numbers.

A vertex missed by the original hierarchy

Consider the nine-vertex directed tree $T$ with arrows

Its only nonempty levels are

Hence the original Maxwell graph deletes $x$.

The vertex $x$ is comparable with every vertex of $T$, so $K(T)$ is a cone. After removing $x$, every element of $\{a,b,p,c\}$ is above every element of $\{q,d,e,f\}$. The first set has order complex equal to the path $a-p-b$ and an isolated $c$; the second gives the path $e-q-f$ and an isolated $d$. Each is homotopy equivalent to $S^0$. Their join is the order complex of the original Maxwell graph, hence

The original reduction has changed the first Betti number from zero to one.

Both links at $x$ have two contractible components, so $\mu_1^-(x)=\mu_1^+(x)=1$. The modified construction retains $x$. The nonzero descending contributions are

with all others zero. Thus $S_{\mathbb{F}}(T)=V(T)$ and

The inequalities are the same as for the three-leaf star. For example, choose degree-one generators $u_q,u_x$ with $d u_q=f-e$ and $d u_x=d-e$. Their boundary has rank two. The generator at $x$ is absent from the original Maxwell graph.

Digraph	$m_D(t)$	$P_D(t)$	$Q_D(t)$
Three-leaf star	$3+2t$	$1$	$2$
Directed $K_{2,2}$	$2+2t$	$1+t$	$1$
Directed $K_{3,4}$	$4+9t$	$1+6t$	$3$
Diamond	$1$	$1$	$0$
Six-vertex example	$2+2t+2t^2$	$1+t^2$	$1+t$
Nine-vertex tree	$3+2t$	$1$	$2$

Computations verify these values over $\mathbb{F}_2$, $\mathbb{F}_3$, and $\mathbb{F}_5$. They also check the reduction and both Morse complexes on all 1,099 DAGs compatible with a fixed topological ordering through five vertices. The computations provide additional checks of the examples and the reduction.

The original Maxwell graph and path homology

An obstruction to unweighted level counts

Write $c_j(D)=|B_j(D)|$. The following obstruction applies to any homology theory with the usual zeroth Betti number.

Proof. Take the star with arrows $v \to s_i$, $1 \le i \le k$, where $k \ge3$. Its only nonempty descending levels have sizes $c_0=k$ and $c_1=1$. It is connected, so the degree-one strong inequality would give

This contradicts nonnegativity.

The star is its own Maxwell graph. Passing to cohomology over a field leaves its Betti numbers unchanged and does not remove the obstruction.

Homology on the unchanged Maxwell graph

Put $W=W(D)$, $P_W=P(D)|_W$, and define

Define the local multiplicities in the reachability order of $\mathcal{M}(D)$ by

Proof. Apply Theorem 1.1 to $\mathcal{M}(D)$. Lemma 3.3, with $U=W$, gives the same levels and hence $W(\mathcal{M}(D))=W(D)$. Thus $\mathcal{M}(\mathcal{M}(D))=\mathcal{M}(D)$. Changing transitive arrows preserves $P_W$. The topographic argument in Proposition 3.10 shows that subdivision introduces no new essential vertex and leaves the restricted order on the old essential vertices unchanged.

For the nine-vertex tree $T$ of § 4, the Morse and Poincaré polynomials are $3+3t$ and $1+t$; their difference is $2(1+t)$, but $b_1^M(T)=1\ne0=\beta_1(T)$. Functoriality holds for order-preserving maps carrying essential vertices to essential vertices.

The original counts suffice if each $w\in B_j$ has lower link in $P_W$ with the reduced homology of $S^{j-1}$, and all vertices of $W\setminus\bigcup_j B_j$ have acyclic lower links. Then $m_j^M=|B_j|$. This holds in the six-vertex example, but not in the three-leaf star.

Local Morse numbers for path homology

Let $A_r(D)$ be the vector space spanned by allowed elementary paths $[v_0,\ldots,v_r]$, with $v_i \to v_{i+1}$ an arrow for every $i$. Following [5], set

Here $\partial$ is the alternating vertex-deletion boundary and $\partial_0=0$. In general $\Omega_r(D)$ is a space of linear combinations; its basis need not consist of elementary paths.

For a vertex $v$, use the induced digraphs

with their original arrows, without adding transitive arrows. The inclusion $D_{<v}\subseteq D_{\leq v}$ embeds their path chain complexes: an allowed chain with allowed boundary in the smaller graph has the same property in the larger graph. Define relative local groups and their dimensions by

Write $p_r^-(D)=\sum_v\nu_r^-(v)$ and $b_r^{\mathrm{path}}(D)=\dim H_r^{\mathrm{path}}(D)$. The corresponding polynomials are $p_D(t)=\sum_r p_r^-(D)t^r$ and $P_D^{\mathrm{path}}(t)=\sum_r b_r^{\mathrm{path}}(D)t^r$.

Proof. Choose a linear extension with descendants first. For its first $i$ vertices put $D_i=D[\{v_1,\ldots,v_i\}]$. The inclusions identify the quotient chain complexes:

Indeed, every new allowed path starts at $v_i$, and all its remaining vertices are strict descendants. The condition that a boundary be allowed also separates according to the initial vertex: deleting an endpoint always leaves an allowed path, whereas every forbidden face comes from an interior deletion and retains the initial vertex. Consequently forbidden faces cannot cancel between chains with different initial vertices, so each initial-vertex component of an $\Omega$-chain is itself an $\Omega$-chain. It follows that

The subcomplex identities give the chain isomorphism (9).

The exact sequences of this filtration give $p_r^--b_r^{\mathrm{path}}=A_r+A_{r+1}$, where $A_r\geq0$ and $A_0=0$, as in Theorem 1.1. Bounded path lengths give eventual equality. For a transitive DAG, $\Omega_*(D)$ is the simplicial chain complex of $K(D)$, and the local quotient is the cone–base complex of Lemma 3.1.

The local groups are independent of the linear extension. Reversing arrows gives $F_r^+(v)$ and the ascending inequalities.

Grouping paths by their initial vertex makes the differential triangular, with diagonal homology $F^-_\ast(v)$. The cancellation proof of Proposition 3.8, or algebraic Morse reduction [14], therefore produces

Its differential lowers the reachability label. Set

By Lemma 3.3, the Hasse diagram on $S_{\mathrm{path}}$ retains both hierarchies. The chain model carries extra data: its differential depends on choices and may connect nonadjacent comparable vertices. It need not be the ordinary path complex of this Hasse diagram.

Subdivision and admissible deletions

The diamond provides a simple obstruction to preserving path homology by the original Maxwell reduction. Subdivide its arrow $a\to b$ to obtain the graph $J$:

Both original Maxwell graphs are the single arrow $a\to d$. For the diamond, $\Omega_2$ is spanned by $[a,b,d]-[a,c,d]$, whose boundary fills its only undirected cycle. Thus its first path Betti number is zero. In $J$, the three allowed two-paths have distinct forbidden shortcut faces $[a,b]$, $[x,d]$, and $[a,d]$. Hence $\Omega_2(J)=0$. Its five arrows and five vertices form a connected cycle, so

Thus the original Maxwell graph does not determine path homology, which is also not subdivision-invariant. Since $J$ has a unique sink, all nonsink lower order links are cones, so $m_1(J)=0$. This also proves the failure of substituting path Betti numbers in (2) noted in the introduction.

In $J$, only $d$ contributes in degree zero and only $a$ contributes in degree one:

Removing $a$ leaves a directed tree, so its relative group records the cycle; all other nonsink local groups vanish. Reversing arrows gives $S_{\mathrm{path}}=\{a,d\}$. The chain model has one generator in each of degrees zero and one and zero differential. The arrow $a\to d$ itself has no degree-one path homology.

A useful deletion is possible when $z$ has exactly one incoming arrow $u\to z$, one outgoing arrow $z\to w$, and $u\to w$ is already present. The retraction $r:D\to D-z$ sending $z$ to $w$ and fixing other vertices satisfies $\operatorname{id}_D\simeq i\circ r$ via $z\to w$, where $i$ is inclusion. Thus deletion preserves path homology; see [15 Section 6]. It preserves reachability on the remaining vertices, and $z$ belongs to no boundary level by the argument of Proposition 3.10. Both hierarchies therefore survive. Inserting a missing shortcut first is not allowed.

It remains to characterize when Maxwell levels agree with local homological degrees, and to find a canonical graph reduction preserving both path homology and the two hierarchies.

AI use statement. LLMs were used for proof refinement, literature review, and manuscript revision.

The University of Texas Rio Grande Valley, Brownsville, Texas, USA

[email protected]