{'fraction_non_alphanumeric': 0.036588622807798454, 'fraction_numerical': 0.0056529867355114395, 'mean_word_length': 3.5963584288052375, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Algebraic discrete Morse theory for the hull resolution

We study how powerful algebraic discrete Morse theory is when applied to hull resolutions. The main result describes all cases when the hull resolution of the edge ideal of the complement of a triangle-free graph can be made minimal using algebraic discrete Morse theory.


Introduction
Finding minimal free resolutions of ideals is an important problem in commutative algebra. Cellular resolutions provide one of the main techniques for obtaining free resolutions of monomial ideals. A particularly nice type of cellular resolution is the hull resolution. The hull resolution preserves all the symmetry of the ideal itself but it is not necessarily minimal. Algebraic discrete Morse theory is a general method for making free resolutions smaller, but often it is not clear how powerful this method is. This paper studies the case when the monomial ideal is the edge ideal of a graph and algebraic discrete Morse theory is applied to the hull resolution.
The main result is the following.
Theorem 1.1. Let G be a triangle-free graph and let I G be the edge ideal of G. The Hull resolution of I G can be made minimal using algebraic discrete Morse theory if and only if G has no induced subgraph isomorphic to two disjoint cycles.
An important example is the complement of a cycle. There are a few cellular resolutions of the edge ideal of the complement of a cycle already in the literature. Bierman [3], Dochterman [6] and Sturgeon [7] give different constructions. As there is some choice in how to apply discrete Morse theory, the exact description of the resolution from the theory in this paper varies. However it is immediate that the cells correspond to components of induced subgraphs of the cycle and each induced proper subgraph gives one cell less than the number of components.
The minimal example where the algebraic discrete Morse theory can not be used to make the hull resolution minimal for complements of triangle-free graphs is the complement of two disjoint cycles. In these cases it is possible to get a cellular resolution with one single cell too many to be minimal.
The outline of the paper is as follows. Section 2 introduces some basic graph theory concepts and notation. In Section 3 edge ideals and the associated edge polytopes that support their hull resolutions are described. In Section 4 the machinery of algebraic discrete Morse theory and cellular resolutions is briefly explained. In Section 5 the hull resolutions for general edge ideals are explored. Section 6 and Section 7 are devoted to the combinatorics of the hull resolutions of the edge ideals of triangle-free graphs. In Section 8 Theorem 1.1 is proved.

Graph theory
Graphs are finite and have no loops or multiple edges unless explicitly said otherwise.
Some basic notions from graph theory are needed. Let G be a graph, the vertex set of G is denoted V (G) and the edge set of G is denoted E(G). The degree of a vertex v ∈ V (G) is the number of edges containing v in E(G). Let V i (G) be the set of vertices in V (G) with degree i. A subgraph of G is a graph G ′ with V (G ′ ) ⊆ V (G) and E(G ′ ) ⊆ E(G). A component of G is a maximal connected subgraph with nonempty vertex set. A set U ⊆ V (G) is independent if there is no edge between any pair of vertices in U . A graph is triangle-free if it has no subgraph isomorphic to a triangle.
There are a few standard ways to construct new graphs that will be important. The complement of a graph G is denoted G and it is the graph with V (G) = V (G) so that two vertices are adjacent in G if and only if they are not adjacent in G.
Given two graphs G 1 and G 2 the graph G 1 ∩ G 2 is defined as the graph with Stars are important special kinds of graphs.
Given a graph G there are some special important subgraphs that will occur.
Two important properties is that N G (v) is a star for vertices v and the neighborhood of v is the same in G and N G (v). In fact this is a simple reformulation of the definition.
Given two different nonempty independent sets U and U ′ it will be important to were the unions are disjoint. In Section 7 there are many propositions where the proofs depend on determining if the graph N C G (U )∩N C G (U ′ ) has isolated vertices or not, and the usual argument is to handle each part ( Let G be a graph and let S ⊆ E(G) be a subset so that every vertex in V 1 (G) ∪ V 2 (G) is in at least one edge in S. There is a graph F (G, S) that will be important in understanding the combinatorics of the hull resolutions of edge ideals.
The construction of F (G, S) is in two steps. Construct the graph F ′ (G, S) from G by subdividing every edge in S. The vertex set of F ′ (G, S) can be thought of as the union V (F ′ (G)) = V (G) ∪ S. In this way two elements in S are adjacent if they have a vertex in common. Elements in V (G) are adjacent if they were adjacent in G but the edge between them is not in S. Finally a vertex v in V (G) is adjacent to an element e in S if v is one of the endpoints of e.
Construct F (G, S) from F ′ (G, S) by contracting one edge ve for every v ∈ V 1 (G) ∪ V 2 (G) where e ∈ S. As the degree of v does not change by subdividing edges the degree in F ′ (G, S) is still one or two, in particular the combinatorics of the graph F (G, S) do not depend on the choice of edge. An explicit description of the vertex set and adjacency in F (G, S) will be useful.
. Two edges in S are adjacent if they have a common endpoint in It is immediate from the construction that G and F (G, S) are homotopy equivalent as topological spaces and this property will be important. Later there will be some operations on the topological spaces realized by graphs, for example contracting edges. This is the only situation where loops and multiple edges might occur.
Most graphs considered are undirected. In fact the only directed graphs occuring will be Hasse diagrams of posets, and graphs obtained from Hasse diagrams by reversing some edges. Recall that the vertices of the Hasse diagram of a poset is the elements of the poset and there is an edge from u to v if and only if u > v and there is no element w so that u > w > v. The dualization of a poset P is the poset whose Hasse diagram is obtained from the Hasse diagram of P by reversing all edges.

Edge ideals and edge polytopes
Let G be a graph. Let {e v | v ∈ V (G)} be the standard basis of R V (G) . The polytope P G obtained as the convex hull of {e i +e j | ij ∈ E(G)} is the edge polytope of G. It is immediate from the definition that the polytopes P G behave well with respect to the intersection operation on graphs P G1∩G2 = P G1 ∩ P G2 .
In order to give the facet description of P G some more notation is needed.   If U = U ′ are two acceptable sets in G then P N CG(U) = P N CG(U ′ ) .
Proposition 3.6. Let G be a connected not bipartite graph. The dimension of Induced subgraphs give faces in P G .
Proposition 3.7. Let G be a graph and let U be a nonempty subset of V (G). Let H be the linear subspace of Proof. The vertices of P G in H are exactly the points e i + e j so that ij ∈ E(G) and {i, j} ⊆ U . The intersection is a face as is the edge ideal of G. Define a map ℓ G from the set of nonempty faces of P G to the monic monomials in I G by ℓ G (σ) =lcm(x i x j | e i + e j ∈ σ). Sometimes it is useful to extend the domain of ℓ G to include the empty set and then ℓ G (∅) = 1, in this case the range of ℓ G is also extended. Let M G be the subposet of the face poset of If G has no edges the definitions are a bit degenerate, the conventions P G = ∅,

Discrete Morse theory and cellular resolutions
The machinery of cellular resolutions is a powerful tool used to construct free resolutions of monomial ideals. A cellular resolution of a monomial ideal I is encoded by a cell complex X and a labeling map ℓ from the set of cells of X to I, the map ℓ have to satisfy ℓ(σ) =lcm(ℓ(v) | v is a vertex of σ). There is an easy condition for when a pair X and ℓ gives a cellular resolution of I, the condition is that the image of ℓ generates I and the subcomplex consisting of all cells with labels dividing a monomial m is acyclic for all m. The condition for when cellular resolutions is minimal is that the resolution is minimal if and only if no cell is on the boundary of a cell with the same label.
It is always possible to construct a cellular resolution for a given monomial ideal, one construction is the hull resolution by Bayer and Sturmfels [2]. In the special case when I is the edge ideal of a graph G then the cell complex in the hull resolution is P G and the labeling map is ℓ G . In general it is not possible to give a minimal cellular resolution but algebraic discrete Morse theory can be used to make many cellular resolutions smaller.
The discrete Morse theory developed by Forman [5] provides a way to reduce the number of cells in a CW-complex without changing the homotopy type.
There are a few different ways to express discrete Morse theory, the way that works best for the algebraic setting is in terms of acyclic matchings in the Hasse diagram of the face poset of the complex. Let D be a directed graph. A subset M ⊆ E(D) is a matching if every vertex is in at most one of the edges in M . A matching is acyclic if the graph obtained by reversing the edges in the matching contain no directed cycles. An important property of Hasse diagrams of a posets is that they contain no directed cycles. Given an acyclic matching M of D the elements of V (D) that are not matched are critical.
The main theorem of discrete Morse theory [5] can be stated as follows.
Theorem 4.1. Let X be a regular CW-complex with face poset P . If M is an acyclic matching of P where the empty face is critical, then there is a CW-complex X homotopy equivalent to X. The critical cells are in bijection with the cells ofX, this bijection preserve dimension.
For one-dimensional complexes the theory is greatly simplified and it is always possible to find optimal matchings in the sense that the resulting complex have the minimal number of cells of any complex homotopy equivalent to the original complex. One-dimensional complexes are essentially graphs where loops and multiple edges are allowed, the complexes obtained from discrete Morse theory are the complexes obtained by contracting non-loop edges. The matchings are pairings of a vertex with an edge containing the vertex, and the matched edge is then contracted and the new vertex is identified with the endpoint of the contracted edge not paired to the contracted edge. In particular it is possible to contract edges in a graph until there is only a single vertex in each component and there is a matching realizing this. The space of acyclic matchings for the Hasse diagram of posets of one-dimensional complexes has interesting structure and was further studied by Chari and Joswig [4].
Batzies and Welker [1] extended discrete Morse theory to work well with cellular resolutions.
Let X be a CW-complex with labeling map ℓ and face poset P . An acyclic matching M of the Hasse diagram of P satisfying στ ∈ M ⇒ ℓ(σ) = ℓ(τ ) is homogenous, that is the matching is homogenous if cells are only matched to cells with the same label.
The main theorem of algebraic discrete Morse theory for cellular resolutions [1] can be stated as follows.
Theorem 4.2. Let X be a regular CW-complex with face poset P . Let ℓ be a labeling of X giving a cellular resolution of the ideal I. If M is a homogenous acyclic matching of P thenX also supports a cellular resolution of I. The cell corresponding to the critical cell σ has label ℓ(σ).

Hull resolutions of edge ideals
A first step to understand the hull resolution of I G is to understand the set of cells with a given label.
Proof. If G has an isolated vertex v then x v does not divide any of the generators of I G and then x v does not divide any monomial in the image of ℓ G . If G has no isolated vertex then for every vertex v ∈ V (G) there is some edge uv ∈ E(G), in particular x v x u divides ℓ G (P G ).
It is possible to describe the image of ℓ G . Proof. Any face with label v∈U x v has to be contained in the subspace H in Proposition 3.7, this proves that any face with the desired label has to be contained has no isolated vertex by Proposition 5.1.
One useful aspect of Proposition 5.2 is that it makes it possible to think of the set of faces with label v∈U x v as the set of faces with the maximal label for some hopefully smaller graph.
When G is disconnected then the behavior of the label can be understood in terms of the components. Proposition 5.3. Let G be the disjoint union of the connected graphs G 1 , . . . , G n and let each G i have at least one edge. The polytope P G is a realisation of the join * i∈[n] P Gi where the label satisfies ℓ G ( * i∈[n] σ i ) = i∈[n] ℓ Gi (σ i ) with ℓ Gi (∅) = 1.
Proof. The polytopes P Gi are contained in mutually orthogonal and nonintersecting affine subspaces of R V (G) , furthermore P G is the convex hull of the union of faces ∪ i∈[n] P Gi and then P G is the indicated join.
The formula for the label is true by definition for the vertices of P G and the general case follows as no variable that divides ℓ Gi (σ i ) can divide ℓ Gj (σ j ) for i = j.
Now the posets of faces with a given label can be described. Using the facet descriptions of P G it is possible to understand the set of facets in M G for connected G.
Proof. The label of P G\v is not divisible by x v as v is not a vertex of G \ v.  Proof. The face ∩ n∈[n] P N CG(Ui) is P ∩ i∈[n] N CG(Ui) and the vertex set of the graph ∩ i∈[n] N C G (U i ) is V (G). Now the statement follow from Proposition 5.1.

Complements of triangle-free graphs
In general finding the set of independent sets of a graph is itself a challenging problem. We restrict our attention to the easier case when G is the complement of a triangle-free graph G. As G is triangle-free the set of independent sets of G is The acceptability concept can also be extended, but acceptability is only relevant for bipartite graphs and there is only a handful of bipartite graphs with triangle-free complements.
Proposition 6.1. If G is a connected bipartite graph so that G is triangle-free then G is a subgraph of the cycle with four vertices.
Proof. Neither part in the bipartition can have more than two vertices.   Example 6.4. If G is a path with two edges then P G is a line segment and M G only contains P G . Example 6.5. If G is the path with three edges then P G is a triangle and M G consists of P G and one of the edges in the triangle. The two elements in M G can be matched to give an acyclic matching in the Hasse diagram of M G with no critical elements.
Example 6.6. If G is the cycle with four vertices then P G is a square and M G only contains P G .
It is possible to understand the fundamental edges and vertices.
Proof. The graph C G (v) is a clique as G is triangle-free, the clique has a bipartite component if and only if it has one or two elements. The graph N G (v) is connected as it is a star.
The criterion for a vertex to be fundamental is sometimes called the degree criterion for fundamentality. Proposition 6.8. Let G be a graph so that G is triangle-free and let uv ∈ E(G). The graph C G (uv) has no vertices and N C G (uv) = N G (u) ∪ N G (v). In particular uv is fundamental if and only if u and v have a common neighbor in G.
Proof. The graph C G (uv) has no vertices as G is triangle-free. The graph N G (u) ∪ N G (v) is connected if and only if u and v have a common neighbor in G.  To prove the stated description of M G it is first necessary to determine all pairs of facets in M G whose intersection is a face in M G . In order to do this all possible pairs are divided into types depending on some combinatorial data.
There are eleven different types of combinatorial pairs of fundamental sets in G where G is triangle-free and G. The list is as follows. Proof. As uv is fundamental there is some vertex w adjacent to both u and v in G.
Proof. As uv is not fundamental all other vertices are adjacent to either u or v in G, and no vertex is adjacent to both. This property carries over to G. In particular Proof. The proof is split into two parts if u and v have a common neighbor in G or not.
If u and v have a common neighbor w in G then w is isolated in have no edges as all edges in N G (u) go to u while u / ∈ V (C G (v)) and similarly for N G (v) and C G (u). If u and v have no common neighbor then at least one of the graphs C G (u) ∩ N G (v) and C G (v) ∩ N G (u) have a vertex w as G is not bipartite. Now w is isolated in Proof. The graphs C G (uv) and C G (u ′ v ′ ) are empty as G is triangle-free. The edges in the graph Proof. By the degree criterion for fundamentality there is some vertex u ′ ∈ V (G) \ {u, v, w} not adjacent to u in G. Now u ′ is adjacent to both v and w in G as G is triangle-free. Now w is isolated in N G (uv) ∩ N G (uw).
In particular v and the neighbors of v are not isolated in N C G (uv) ∩ N C G (v), the vertex v has neighbors as G is connected and not bipartite. The vertices not adjacent to v in G are adjacent to u in G as G is triangle-free, there are vertices in V (G) \ {u, v} not adjacent to v by the degree criterion for fundamentality. Now N G (uv) ∩ C G (v) connects all the vertices not in N G (v) to u. Proof. The graph C G (w) ∩ N G (uv) has no edges as u and v are adjacent to w in G. As w is fundamental there is some vertex Proof. As uw is fundamental there is some vertex Proof. By the degree criterion for fundamentality there is a vertex u ′ ∈ V (G) \ {u, v, w} not adjacent to u in G. As G is triangle-free u ′ is adjacent to both v and w in G. Now u ′ is isolated in N G (uv) ∩ N G (w). The edge uv is in N G (w) ∩ C G (uv) and no vertex is isolated in N C G (uv) ∩ N C G (w) The set of facets of The identifications v ↔ P N CG(v) and uv ↔ P N CG(uv) are used in the following lemma and in this way the facets in M G is viewed as the set Proof. First it is proved that no codimension three face is in M G . Following the proofs of the propositions 7.3, 7.7, 7.8 and 7.12 the codimension two faces in M G are the edge polytopes of disjoint unions of stars. In particular any further intersections will isolate edges in the underlying graphs and then there can be no codimension three face. Now M G is the face poset of some one-dimensional complex with the same vertex set as F (G, S G ). The final step is to show that the adjacencies agree.
The adjacencies come from pairs of type 2, 6, 7 and 11. This agrees with the adjacency description of F (G, S G ). Two vertices in V (G) \ (V 1 (G) ∪ V 2 (G)) are adjacent if they are adjacent in G but the edge between them is not in S G , this comes from pairs of type 2. Two edges in S G are adjacent if they have a common endpoint in V 1 (G)∪V 2 (G), this comes from pairs of type 6. Vertices in V (G)\(V 1 (G)∪V 2 (G)) are adjacent to the edges in S G containing them, this comes from pairs of type 7. Finally a vertex u in V (G) \ (V (G) ∪ V (G)) is adjacent to an edge vw in S G not containing u if uv ∈ E(G) \ S G , this comes from pairs of type 11.
The point of Lemma 7.13 is that all parts of the hull resolution of I G now can be understood in terms of graphs homotopy equivalent to G or induced subgraphs of G.  If Lemma 7.13 applies to G i consider again ordinary discrete Morse theory. The optimal acyclic matching contracts all components without cycles to single vertices without loops and if there is a component with cycles it is unique and it is contracted to a vertex with potentially many loops. For M Gi this translates to a partial matching where P Gi is critical and there is a critical facet for each component and at most one of them has critical codimension two faces attached. If there is component with cycles then the corresponding facet is matched to P Gi otherwise any of the facets can be matched to P Gi . Now there are matchings for each M Gi and these glue together to a matching of i∈[n] M Gi in the following way. For every matched pair σ 1 , τ 1 ∈ M G2 match σ 1 ×σ 2 ×· · ·×σ n to τ 1 ×σ 2 ×· · ·×σ n . Now there might be some critical cell φ 1 ∈ M G1 . Proceed to for every matched pair σ 2 , τ 2 ∈ M G2 match φ 1 × σ 2 × σ 3 × · · · × σ n to φ 1 × τ 2 × σ 3 × · · · × σ n and so on. In the end the critical cells are of the form φ 1 × · · · × φ n where each φ i is critical in M Gi . This way of constructing acyclic matchings is standard in discrete Morse theory but an argument for acyclicity is given anyway as the argument is also used to show minimality of the resulting resolution.
Assume that there is a directed path in the Hasse diagram of i∈[n] M Gi where the matched edges are reversed. Suppose one of the edges in the cycle is from σ 1 × σ 2 × · · · σ n to σ 1 × σ 2 × · · · σ i−1 × τ i × σ i+1 × · · · σ n so that the edge comes from the edge from σ i to τ i in the reversed Hasse diagram of M Gi . Following the cycle it is possible to get back to σ 1 × σ 2 × · · · σ n and then the edges from M Gi give a cycle and this is a contradiction.
What remains is to show that the resulting resolution is minimal. In order to do this a slight strengthening of Theorem 4.2 is needed including a sufficient condition for minimality. One such condition is that the resulting resolution is minimal if there is no directed path between critical cells with the same label in the graph obtained by reversing the matched edges in the Hasse diagram. This condition is a special case of Lemma 7.5 in [1].
It is enough to consider directed paths where all cells have the same label as the matching is homogenous.
Consider the Hasse diagrams of M Gi where the matched edges are reversed. There can not be any directed path between critical cells with the same dimension as the endpoint then have to be matched. Any directed path between critical cells then have to go from a facet to a codimension two face. In particular the path has to pass through P Gi as the critical elements from codimension two faces correspond to edges in a single component of G i and the critical facets correspond to the other components. Now there is no path between critical faces of M Gi as the facet matched to P Gi is a sink. In the same way as acyclicity of the matchings for each M Gi gives acyclicity of the matching of i∈[n] M Gi this argument extends to show that there is no directed path between critical cells in the Hasse diagram of i∈[n] M Gi with matched edges reversed.