Planar Graphs as Minimal Resolutions of

Trivariate Monomial Ideals

Ezra Miller

Received: May 4, 2001 Revised: March 11, 2002

Communicated by Günter M. Ziegler

Abstract. We introduce the notion of rigid embedding in a grid surface, a new kind of plane drawing for simple triconnected planar graphs. Rigid embeddings provide methods to (1) find well-structured (cellular, here) minimal free resolutions for arbitrary monomial ideals in three variables; (2) strengthen the Brightwell–Trotter bound on the order dimension of triconnected planar maps by giving a geometric reformulation; and (3) generalize Schnyder’s angle coloring of planar triangulations to arbitrary triconnected planar maps via geometry. The notion of rigid embedding is stable under duality for planar maps, and has certain uniqueness properties.

2000 Mathematics Subject Classification: 05C10, 13D02, 06A07, 13F55, 68R10, 52Cxx Keywords and Phrases: planar graph, monomial ideal, free resolution, order dimension, (rigid) geodesic embedding

Contents

Introduction and summary  44

I Geodesic embedding in grid surfaces 49

1 Planar maps 49

2 Grid surfaces 51

3 Gluing geodesic embeddings 55 4 Contracting rigid geodesics 57 5 Triconnectivity and rigid embedding 66

II Monomial ideals 68 6 Betti numbers 68 7 Cellular resolutions 69 8 Graphs to minimal resolutions 70 9 Uniqueness vs. nonplanarity 72 10 Deformation and genericity 73 11 Ideals to graphs: algorithm 75 12 Ideals to graphs: proof 77

III Planar maps revisited 80 13 Orthogonal coloring 80 14 Orthogonal flows 81 15 Duality for geodesic embeddings 84 16 Open problems 86 Introduction Simple triconnected planar graphs admit numerous characterizations. Two famous examples include Steinitz’ theorem on the edge graphs of 3-polytopes, and the Koebe–Andreev–Thurston circle packing theorem (see [Zie95] for both). These results produce “correct” planar (or spherical) drawings of the graphs in question, from which a great deal of geometric and combinatorial information flows readily. This paper introduces a new kind of plane drawing for simple triconnected planar graphs, from which a great deal of algebraic and combinatorial information flows readily. These geodesic embeddings inside grid surfaces provide methods to

• solve the problem of finding well-structured (cellular, in this case) mini-

mal free resolutions for arbitrary monomial ideals in three variables;

Documenta Mathematica 7 (2002) 43–90

• strengthen the Brightwell–Trotter bound on the order dimension of triconnected planar maps [BT93] by giving a geometric reformulation; and

• generalize Schnyder’s angle coloring for planar triangulations [Tro92, Chapter 6] to arbitrary triconnected planar maps via geometry.

We note that Felsner’s generalization of Schnyder’s angle coloring [Fel01] coincides with the orthogonal colorings independently discovered here as consequences of geometric considerations. In parallel with circle-packed and polyhedral graph drawings, additional evidence for the naturality of geodesic embeddings comes from their stability under duality, and the uniqueness properties enjoyed by “correct” geodesic embeddings—called rigid embeddings in what follows—for a given planar map. The plan of the paper is as follows. Immediately following this Introduction is a section containing two theorems summarizing the equivalences and constructions forming main results of the paper. After that, the paper is divided into three Parts. Part I lays the groundwork for geodesic and rigid embeddings in grid surfaces, and is geared almost entirely toward proving Theorem 5.1: the rigid embedding theorem. Terminology for the rest of the paper is set in Section 1, which also states a standard criterion for triconnectivity under edge contraction that serves as an inductive tool in the proof of Theorem 5.1. Then Section 2 presents the definition of grid surfaces, as well as the vertex and edge axioms for geodesic and rigid embeddings. Their consequences, the region and rigid region axioms, appear in Propositions 2.3 and 2.4. The first connection with order dimension comes in Corollary 2.5. Sections 3 and 4 consist of stepping stones to the rigid embedding theorem. The basic inductive step for abstract planar maps is Lemma 3.1, which motivates the preliminary grid surface construction of Lemma 3.2. Induction for grid surfaces occupies the three Propositions in Section 4. They have been worded so that their rather technical proofs (particularly that of Proposition 4.2) may be skipped the first time through; instead, the Figures should provide ample intuition. Section 5 completes the induction with a few more arguments about abstract planar maps. Corollary 5.2 recovers the Brightwell–Trotter bound on order dimension from rigid embedding. The focus shifts in Part II to the algebra of monomial ideals in three variables, specifically their minimal free resolutions. A review of the standard tools occupies Section 6, while Section 7 recaps the more recent theory of cellular resolutions, along with a triconnectivity result (Proposition 7.2) suited to the applications here. Theorem 8.4 says how geodesic embeddings become minimal free resolutions. Corollary 8.5 then characterizes triconnectivity as the condition guaranteeing that a planar map supports a minimal free resolution of some artinian monomial ideal. Section 9 displays even more reasons why rigid embeddings are better than arbitrary geodesic embeddings: they have a strong uniqueness property (Corollary 9.1), which implies in particular that every minimal cellular resolution of the corresponding monomial ideal is planar. Surprisingly, there can exist nonplanar cell complexes supporting minimal free resolutions of trivariate artinian monomial ideals that are sufficiently nonrigid; Example 9.2 illustrates one. Sections 10–12 are devoted to producing minimal cellular free resolutions of arbitrary monomial ideals in three variables (Theorem 11.1). The deformations reviewed in Section 10 serve as part of the algorithmic solution pseudocoded in Algorithm 11.2. The proof of correctness for the algorithm and the theorem, which occupy Section 12, are rather technical and delicate. As with Section 4, the pictures may give a better feeling for the methods than the proofs themselves, at least upon first reading. Part III continues where Part I left off, with more combinatorial theory for planar maps. Section 13 introduces orthogonal coloring, which generalizes Schnyder’s angle coloring and abstracts the notion of geodesic embedding (Proposition 13.1). Then, Section 14 shows how orthogonal coloring encodes the abstract versions of the orthogonal flows that played crucial roles in Section 2. As a consequence, Proposition 14.2 shows that orthogonal flows are examples of—but somewhat better than—normal families of paths, connecting once again with the work of Brightwell and Trotter on order dimension. Section 15 demonstrates how Alexander duality for grid surfaces (or monomial ideals) manifests itself as duality for planar maps geodesically embedded in grid surfaces. Finally, Section 16 presents some open problems related to the notions developed in earlier sections, including a conjecture on orthogonal colorings and some problems on classifying cell complexes supporting minimal resolutions. Further questions concern applications of the present results to broader combinatorial algebraic problems, notably how to describe the “moduli space” of all minimal free (or injective) resolutions of ideals generated by a fixed number of monomials. After completing an earlier version of this paper, the author was informed that Stefan Felsner had independently discovered the theory in Sections 13 and 14 [Fel01, Sections 1 and 2]. In addition, Felsner proved Conjecture 16.3 in [Fel02] after reading the preliminary version of this paper. See Section 16.3 for details and consequences. Part III is almost logically independent of Part II, the only exceptions being Lemmas 8.2 and 8.3. Thus, the reader interested primarily in the combinatorics of planar graphs (as opposed to resolutions of monomial ideals) can read Parts I and III, safely skipping everything in Part II except for these two lemmas. The reader interested primarily in resolutions of monomial ideals should skip everything in Sections 3–5 except for the statement of Theorem 5.1.

Acknowledgements

This paper grew out of conjectures developed with Bernd Sturmfels during a memorable train ride through the Alps, and subsequent discussions resulting in the expository paper [MS99], where some of the results were announced without proof. The Alfred P. Sloan Foundation and the National Science Foundation funded various stages of this project.

Summary theorems

For the sake of perspective and completeness, we collect the main ideas of the paper into a pair of precisely stated summary theorems. Their proofs are included, in the sense that the appropriate results from later on are cited. All of the notions appearing in Theorems A and B will be introduced formally in due time; until then, brief descriptions along with Figure 1 should suffice. Let M be a connected simple planar map—that is, a graph embedded in a surface S homeomorhpic to the plane ℝ^{2}. All graphs in this paper have finitely many vertices and edges. Fix a point ∞ ∈ S far from M, and define the exterior region of M to be the connected component of S ∖ M containing ∞. Given three vertices ẋ, ẏ, ż ∈ M bordering the exterior region, form the extended map M_{∞}(ẋ, ẏ, ż) by connecting ẋ, ẏ, ż to ∞. Call a graph triconnected either if it is a triangle, or if it has at least four vertices of which deleting any pair along with their incident edges leaves a connected graph. A set of paths leaving a fixed vertex ν ∈ M is said to be independent if their pairwise intersection is {ν}. Let k[x, y, z] be the polynomial ring in three variables over a field k, and let I ⊂ k[x, y, z] be an ideal generated by monomials. The grid surface S corresponding to I is the boundary of the staircase diagram of I, which is drawn (as usual) as the stack of cubes corresponding to monomials not in I. Rigid embedding of a planar map M in S involves identifying the edges of M as certain piecewise linear geodesics in S, and constitutes an inclusion of the vertex-edge-face poset of M into ℕ^{3}. Orthogonal coloring M involves coloring the angles in M with three colors according to certain rules. Since it would take too long to do real justice to the definitions of ‘rigid embedding’ and ‘orthogonal coloring’ here, Figure 1 will have to do for now. The outer corners in the orthogonal coloring and the vectors on the axes in S are called axial vertices. The grid surface S is called axial when I is artinian. Suppose M is a cell complex (finite CW complex) whose faces are labeled by vectors in ℕ^{3}, in such a way that the union M_{⪯α} of faces whose labels precede α ∈ ℕ^{3} is a subcomplex of M for every α. Roughly speaking, M supports a cellular free resolution of I if the boundary complex of M_{⪯α} with coefficients in k is the ℕ^{3}-degree α piece of a free resolution of I, for every α ∈ ℕ^{3}.

Theorem A Let M be a planar map. The following are equivalent.

1. M has three vertices ẋ, ẏ, ż bordering its exterior region for which M_{∞}(ẋ, ẏ, ż) is triconnected.

2. M has three vertices ẋ, ẏ, ż bordering its exterior region to which every vertex of M has independent paths.

3. M has an orthogonal coloring with axial vertices ẋ, ẏ, ż.

4. M can be rigidly embedded in an axial grid surface.

Figure 1: Orthogonal coloring and rigid embedding of an extended map

5. M supports a cellular minimal free resolution of some artinian monomial ideal in k[x, y, z].

Every artinian monomial ideal in k[x, y, z] has a minimal cellular resolution supported on a cell complex M satisfying these conditions; in fact, Algorithm 11.2 produces such an M automatically.

Proof. 4 ⇒ 3 follows from Proposition 13.1. 3 ⇒ 2 follows from Proposition 14.2. 2 ⇒ 1 follows easily from the definitions. 1 ⇒ 4 is Theorem 5.1. 4 ⇒ 5 follows from Theorem 8.4. 5 ⇒ 1 is Proposition 7.2.

The final statement comes from Theorem 11.1 and Proposition 12.4. □

Similar—but weaker—statements apply to minimal cellular free resolutions of arbitrary (not necessarily artinian) monomial ideals in k[x, y, z].

Theorem B Let N be a planar map. The following two conditions are equivalent.

1. N can be rigidly embedded in some grid surface.

2. N can be obtained by deleting ẋ, ẏ, ż and all edges incident to them from some planar map M satisfying the equivalent conditions in Theorem A.

These conditions imply that

3. N supports a minimal free resolution of some monomial ideal in k[x, y, z].

Every monomial ideal in k[x, y, z] has a minimal free resolution supported on a planar map N satisfying conditions 1 and 2; such an N can be produced algorithmically.

Proof. 1 ⇒ 2 follows from Theorem 8.4 and Lemma 8.2. 2 ⇒ 1 follows from Theorem 5.1 and Lemma 8.2. 1 ⇒ 3 follows from Theorem 8.4. The first half of the final statement is Theorem 11.1 along with the first paragraph of its proof on p. 80; add in Proposition 12.4 for the algorithmic part. □

In reality, the more detailed versions later on are considerably more precise, demonstrating how some of the equivalent descriptions naturally give rise to others.

Part I Geodesic embedding in grid surfaces

1 Planar maps

Let V = {ν_{1}, …, ν_{r}} be a finite set. A graph G with vertex set V is uniquely determined by a collection E ⊆ \binom{V}{2} of edges, each consisting of a pair of vertices. Except for one paragraph at the beginning of Section 15, we consider only simple graphs—that is, without loops or multiple edges—so G is an abstract simplicial complex of dimension 1 having vertex set V. Thus G can be regarded as a topological space, via any geometric realization. Let S be a surface homeomorphic to the Euclidean plane ℝ^{2}. A plane drawing of G in S is a continuous morphism G ↪ S of topological spaces that is a homeomorphism onto its image. If G is connected, the image M is called a planar map. Deleting the images of the vertices and edges of G from S leaves several connected components whose closures are the regions of M. The unique unbounded region is called the exterior region of M. Two planar maps are isomorphic if they result from plane drawings of the same graph G, their regions have the same boundaries in G, and the boundaries of their exterior regions correspond. We often blur the distinction between a planar map and the underlying graph, by not distinguishing a vertex (resp. edge) of G from the corresponding point (resp. arc) of M in the surface S. A graph G is k-connected either if G is the complete graph on k vertices, or if G has at least k + 1 vertices, and given any k − 1 vertices ν_{1}, …, ν_{k−1} of G, the deletion del(G; ν_{1}, …, ν_{k−1}) is connected. Here, the deletion is obtained by removing ν_{1}, …, ν_{k−1} as well as all edges containing them from G. In case k = 2 or 3, the graph G is called biconnected or triconnected, respectively. Suppose that e is an edge of a planar map M, and that none of the (one or two) regions containing e is a triangle. The contraction M/e of M along e is obtained by removing the edge e and identifying the two vertices of e. The underlying graph of M/e is the topological quotient G/e; it is still simple because e is the only edge connecting its vertices in G (so G/e has no loops) and no triangles contain e in G (so G/e has no multiple edges). Some plane drawing of M/e is obtained by literally contracting the edge e in M (technically: there is a homotopy G×[0, 1] → S such that G×t → S is a plane drawing of G for t < 1, while G × 1 → S is a composition G → G/e → S with the second map being a plane drawing). Contraction will be a crucial inductive tool, via a well-known criterion for triconnectivity under contraction:

Proposition 1.1 Let M be a triconnected planar map with at least four vertices, and let e be an edge. If there exist two regions F, F′ of M such that

1. e ∩ F and e ∩ F′ are the two vertices of e, and

2. F ∩ F′ is nonempty,

then either e borders a triangle or the contraction M/e fails to be triconnected. Conversely, if e borders no triangles and M/e is triconnected, then no such F, F′ exist.

Thinking of the surface S ≅ ℝ^{2} as the 2-sphere minus ∞, many of the planar maps M in this paper result by embedding some graph G_{∞} in the sphere with ∞ as a vertex, and then considering the induced plane drawing M of del(G_{∞}; ∞). When this is the case, we frequently need to consider the subset M_{∞} ⊂ S obtained by omitting the point ∞ from the plane drawing of G_{∞} in the sphere; thus some of the vertices in M connect to the missing point ∞ by unbounded arcs in S. More generally, define an extended map M_{∞} ⊂ S to be the union of a planar map M and a set of infinite nonintersecting arcs connecting some of its vertices to ∞. The closure \overline{M}_{∞} of M_{∞} in the sphere need not be a simple graph because it can have doubled edges: some vertex in M could have two or more unbounded arcs in M_{∞} containing it. Suppose the edges contained in the exterior region of M form a simple closed curve, called the exterior cycle. This occurs, for instance, when M is triconnected. Three vertices ẋ, ẏ, ż ∈ M are called axial if they are encountered (in order) proceeding counterclockwise around the exterior cycle. Having chosen axial vertices, define M_{∞}(ẋ, ẏ, ż) ⊂ S to be the union of M and three unbounded arcs, called the x, y, and z-axes, connecting ẋ, ẏ, ż to ∞. We sometimes blur the distinction between M_{∞}(ẋ, ẏ, ż) and its closure \overline{M}_{∞}(ẋ, ẏ, ż) in the sphere. For instance, we say that M_{∞}(ẋ, ẏ, ż) is triconnected if the graph underlying \overline{M}_{∞}(ẋ, ẏ, ż) is.

2 Grid surfaces

Let ℝ denote the real numbers. Write vectors in ℝ^{3} as α = (α_{x}, α_{y}, α_{z}), and partially order ℝ^{3} by setting α ⪯ β (read ‘α precedes β’) whenever α_{u} ≤ β_{u} for all u ∈ {x, y, z}. Say that α ∈ ℝ^{3} strongly precedes β ∈ ℝ^{3} when α_{u} < β_{u} for all u = x, y, z; this is stronger than saying α ≺ β. (Throughout this paper, the letter u denotes any one of x, y, z, in the same way that x_{i} denotes one of x_{1}, …, x_{n}.) Use α∨β and α∧β to denote the join (componentwise maximum) and meet (componentwise minimum) of α, β ∈ ℝ^{3}. Let V ⊂ ℕ^{3} ⊂ ℝ^{3} be a set of pairwise incomparable elements, where ℕ denotes the set of nonnegative integers. The order filter

⟨V⟩ = {α ∈ ℝ^{3} | α ⪰ ν for some ν ∈ V}

generated by V is a closed subset of the topological space ℝ^{3}. Its boundary S_{V} is called a grid surface or staircase. Orthogonal projection onto the plane x + y + z = 0 restricts to a homeomorphism S_{V} ≅ ℝ^{2}. (This homeomorphism gives the correspondence between rhombic tilings of the orthogonal projection of the |ẋ| × |ẏ| × |ż| parallelepiped and plane partitions of the |ẋ| × |ẏ| grid with parts at most |ż|. The grid surface in Figure 1 clearly demonstrates the homeomorphism: the diagram is, after all, drawn faithfully on the twodimensional page.) One of the basic properties of grid surfaces is that α ∈ S_{V} whenever ρ, σ ∈ S_{V} and ρ ⪯ α ⪯ σ. Therefore, if ρ, σ ∈ S_{V} and ρ ⪯ σ, then S_{V} contains the line segment in ℝ^{3} connecting ρ to σ. In particular, if ν, ω ∈ V satisfy ν∨ω ∈ S_{V}, then S_{V} contains the union [ν, ω] of the two line segments joining ν and ω to ν∨ω; we refer to such arcs as elbow geodesics^{1} in S_{V}. When ν and ω are the only vectors in V preceding ν∨ω, the arc [ν, ω] is called a rigid geodesic. Denote the nonnegative rays of the coordinate axes in ℝ^{3} by X, Y, and Z, and use the letter U to refer to any of X, Y, Z. The ray ν + U intersects S_{V} in an oriented line segment U_{ν} called the orthogonal ray leaving ν in the direction of U. Thus every point in V has precisely three orthogonal rays, one parallel to each coordinate axis and all contained in S_{V}, although some orthogonal rays may be unbounded while others are bounded. If U_{ν} is bounded, so it has an endpoint besides ν, then the other endpoint of U_{ν} can always be expressed as a join ν∨ω for some ω ∈ V. When there is exactly one such point ω, so [ν, ω] is a rigid geodesic, we say that ν or U_{ν} points toward ω. Observe that ν∨ω must share two coordinates with at least one (and perhaps both) of ν and ω, so every elbow geodesic contains at least one orthogonal ray. Making compatible choices of elbow geodesics containing all orthogonal rays yields a planar map. To be precise, a plane drawing M ↪ S_{V} is a geodesic grid surface embedding, or simply a geodesic embedding in S_{V}, if the following two axioms are satisfied:

1Elbow geodesics do minimize length for the metric on S_{V} induced by the usual metric on ℝ^{3}, but this fact has no practical application in this paper.

Documenta Mathematica 7 (2002) 43–90

(Vertex axiom) The vertices of M coincide with V.

(Elbow geodesic axiom) Every edge of M is an elbow geodesic in S_{V}, and every bounded orthogonal ray in S_{V} is part of an edge of M.

With the following stronger edge axiom instead, M ↪ S_{V} is a rigid embedding, which we sometimes phrase by saying that M is rigidly embedded in S_{V}:

(Rigid geodesic axiom) The elbow geodesic exiom holds, and every edge of M is a rigid geodesic in S_{V}.

The rigid geodesic axiom really consists of three parts, each of which puts nontrivial restrictions on S_{V} or M: every bounded orthogonal ray in S_{V} is part of a rigid geodesic (a priori, this has nothing to do with M); every rigid geodesic in S_{V} is an edge of M; and every edge of M is a rigid geodesic in S_{V}.

Lemma 2.1 Let M ↪ S_{V} be a geodesic or rigid embedding. Suppose V is in order-preserving bijection with another set Ṽ of vertices via ν ↔ ν̃, so that ν_{u} ≤ ω_{u} ⇔ ν̃_{u} ≤ ω̃_{u} for all ν, ω ∈ V and u ∈ {x, y, z}. Then the elbow or rigid geodesics in SṼ constitute another geodesic or rigid embedding of M. In particular, linearly scaling one or more coordinate axes by integer factors preserves geodesic or rigid embeddings.

Proof. Purely order-theoretic properties of V determine whether ν and ω are the endpoints of an elbow geodesic, or whether ν points toward ω. □

Any geodesic embedding M ↪ S_{V} determines an extended map

M_{∞} = M ∪ (unbounded orthogonal rays).

A special case occurs when S_{V} is axial, having axial vectors

ẋ = (|ẋ|, 0, 0), ẏ = (0, |ẏ|, 0), and ż = (0, 0, |ż|)

in V for nonzero |ẋ|, |ẏ|, |ż| ∈ ℕ. Thus, if M is geodesically embedded in an axial grid surface S_{V}, we can define the axial vertices of M to be the axial vectors in V, and set M_{∞}(ẋ, ẏ, ż) = M ∪ Xẋ ∪ Yẏ ∪ Zż. (Precisely two bounded orthogonal rays leave each axial vertex, while all three orthogonal rays leaving any other vertex are bounded). Conversely, if M comes equipped with axial vertices ẋ, ẏ, ż, then we require any geodesic embedding M ↪ S_{V} to send these axial vertices to axial vectors in V. Suppose M is geodesically embedded in the axial grid surface S_{V}. The edge of M leaving any vertex ν ≠ ż along the vertical orthogonal ray Z_{ν} connects ν to another vertex ω with strictly larger z-coordinate, but weakly smaller x and y-coordinates. Continuing in this manner constructs an orthogonal flow [ν, ż] from ν to ż that is increasing in z, but weakly decreasing in x and y. It follows that [ν, ż] and the similarly constructed paths [ν, ẋ] and [ν, ẏ] are independent, meaning that they intersect pairwise only at ν itself. Since [ẋ, ẏ], [ẏ, ż], and [ż, ẋ] partition the exterior cycle of M into three arcs, the contractible sets bounded by

[ẋ, ν, ẏ] := [ν, ẋ] ∪ [ν, ẏ] ∪ [ẋ, ẏ]

and its cyclically permuted analogues partition the regions of M.

Lemma 2.2 Suppose M ↪ S_{V} is an axial geodesic embedding, and ν ∈ V borders a region contained in [ẋ, ω, ẏ]. Then ν_{z} ≤ ω_{z}, with strict inequality if ν ∉ [ω, ẋ] ∪ [ω, ẏ]. A similar statement holds for arbitrary permutations of x, y, z.

Proof. The orthogonal flow [ν, ż] must cross [ω, ẋ] or [ω, ẏ], at ν′ ∈ [ω, ẋ], say. Concatenating the part of [ω, ẋ] from ω to ν′ with the part of [ν, ż] from ν′ to ν yields a path from ω to ν that is weakly decreasing in z. This path is strictly decreasing if ν ∉ [ω, ẋ] ∪ [ω, ẏ], for then it traverses (downwards) the vertical orthogonal ray Z_{ν}. □

Proposition 2.3 (Region axiom) Let M ↪ S_{V} be an axial geodesic embedding, and F a bounded region of M. If α_{F} is the join of the vertices of F, then α_{F} ∈ S_{V}, and every vertex ν ∈ F shares precisely one coordinate with α_{F}.

Proof. If ω ∈ V, then Lemma 2.2 implies there is some u ∈ {x, y, z} such that ν_{u} ≤ ω_{u} for all ν ∈ F. This shows ω cannot strongly precede α_{F}, so α_{F} ∈ S_{V}; every vertex ν ∈ F therefore shares at least one coordinate with α_{F}. Suppose by symmetry that ν_{z} = (α_{F})_{z}. The two edges of F containing ν cannot increase in z, so they exit ν counterclockwise of X_{ν} and clockwise of Y_{ν}. At least one of these edges strictly increases in x, and another strictly increases in y, completing the proof. □

The next proposition says that regions in rigid axial embeddings are 2dimensional analogues of rigid geodesics. In addition to its applications throughout Sections 3 and 4, this fact will play a crucial role in Corollary 5.2, by way of Corollary 2.5, below. Refer to Figure 2 for an illustration of the rigid region axiom as well as its failure for nonrigid embeddings; ν and σ are vertices of an elbow geodesic, but ρ ⪯ ν∨σ in the latter case. The diagram is labeled as in the coming proof of Proposition 2.4.

54 Ezra Miller

PSfrag replacements

rigid embedding nonrigid embedding

ρ σ ν ω ẋ ẏ ż F

Figure 2: The rigid region axiom and its failure for nonrigid embeddings

Proposition 2.4 (Rigid region axiom) Let M ↪ S_{V} be a rigid axial embedding, and F a region of M_{∞}(ẋ, ẏ, ż). If α_{F} is the join of the vertices of F and ω ∈ S_{V}, then ω ∈ F ⇔ ω ⪯ α_{F}.

Proof. The claim is obvious if F is one of the three unbounded regions, so assume F is bounded. Since ω ∈ F ⇒ ω ⪯ α_{F} by definition, let ω ∉ F, and assume F is contained in [ẋ, ω, ẏ] by symmetry. Either ω_{z} > ν_{z} for some vertex ν ∈ F with maximal z-coordinate ν_{z} = (α_{F})_{z}, in which case the proof is trivial, or all vertices of F with z-coordinate (α_{F})_{z} lie on [ω, ẋ] ∪ [ω, ẏ], by Lemma 2.2. Assume there is one on [ω, ẏ] by transposing x and y if necessary, and let ν ∈ F ∩ [ω, ẏ] be closest to ω. The vertex ρ ∈ [ω, ẏ] pointing toward ν has the same z-coordinate as ν (because ω_{z} ≥ ρ_{z} ≥ ν_{z} and ω_{z} = ν_{z}), so the rigid geodesic [ρ, ν] consists of the orthogonal rays Y_{ρ} and X_{ν}. Of ν’s two neighbors in F, let σ have smaller y-coordinate. Since ρ ≠ σ and σ ∉ [ω, ẏ], the edge connecting ν to σ exits ν strictly counterclockwise of X_{ν} and strictly clockwise of Y_{ν}. Thus σ_{z} < ν_{z}, whence σ_{x} = (α_{F})_{x} by the region axiom (Proposition 2.3). But ρ ⪯̸ ν∨σ by the rigid geodesic axiom, while ρ_{z} = ν_{z} = (ν∨σ)_{z} and ρ_{y} < σ_{y} = (ν∨σ)_{y} by construction. Therefore ρ_{x} > (ν∨σ)_{x} = σ_{x} = (α_{F})_{x}. The proof is complete because ω decreases in x along [ω, ẏ] to ρ. □

Corollary 2.5 Let M ↪ S_{V} be an axial rigid embedding. If P is a vertex, edge, or bounded region of M, let α_{P} denote join of the vertices in P. The map sending P ↦ α_{P} constitutes an embedding in ℕ^{3} of the vertex-edge-face poset of M.

Proof. Immediate from the vertex, rigid geodesic, and rigid region axioms. □

Recall that the order dimension of a partially ordered set (poset) P is the smallest d ∈ ℕ such that P includes into the poset ℝ^{d}. The previous corollary says that the order dimension of an axial rigidly embedded planar map is no greater than 3. See [Tro92] for more on order dimension.

3 Gluing geodesic embeddings

Let M be a planar map with axial vertices ẋ, ẏ, ż and extended map M_{∞} = M_{∞}(ẋ, ẏ, ż). Suppose C is a simple cycle in M having three counterclockwise ordered vertices ẍ, ÿ, z̈, and furthermore that C bounds a closed disk R ⊂ S that is a union of bounded regions in M. Following Brightwell and Trotter (cf. [Tro92, Chapter 6], although our definition differs slightly), we call C a ring if every edge of M not contained in R intersects R in a (possibly empty) subset of {ẍ, ÿ, z̈}. The double-dotted vertices play the roles of axial vertices for a smaller map N = M ∩ R “glued into” M by external edges emanating from N at ẍ, ÿ, z̈. Although we allow ü for u ∈ {x, y, z} to equal the original axial vertex u̇ ∈ M, we exclude the case where C is the exterior cycle of M by referring to a proper ring. Assume for each u = x, y, z that the vertex ü meets at least one edge in M_{∞} not contained in R (this occurs when M_{∞} is triconnected). If there are at least two such edges then set \underline{ü} = ü. Otherwise, call the unique edge eü and name its other endpoint \underline{ü}. Here, \underline{ü} = ∞ is allowed because ü = u̇ is; but if C is a proper ring, then at most one of \underline{ẍ}, \underline{ÿ}, \underline{z̈} can equal ∞, because there are no proper rings containing two axial vertices u̇ ∈ {ẋ, ẏ, ż} such that R contains all of their edges in M. Indeed, it would be impossible to choose the third vertex ü from the pair of last points on the exterior cycle of M going from the two axial vertices on C toward the third. The closure in the 2-sphere of the subset \overline{M}_{∞} ∖ R is a planar map whose intersection with R equals \{ẍ, ÿ, z̈\}. Construct the contraction \overline{M}_{∞}/R by leaving off the edges \{eü | \underline{ü} ≠ ü\} as well as their endpoints ü on C, and then connecting \underline{ẍ}, \underline{ÿ}, \underline{z̈} to a new vertex τ inside R. View M_{∞}/R := (\overline{M}_{∞}/R) ∖ ∞ as being the extension of a map M/R = del(\overline{M}_{∞}/R; ∞). Thus M_{∞}/R = (M/R)_{∞} has τ as a vertex, and still has axes drawn to ∞, although τ might replace one of ẋ, ẏ, ż as an axial vertex. When τ replaces u̇, however, we are free to choose τ = u̇, so we still write (M/R)_{∞}(ẋ, ẏ, ż).

Lemma 3.1 Let M_{∞}(ẋ, ẏ, ż) be triconnected and M contain a proper ring C as above. Then both M ∩ R and M/R are planar maps, with axial vertices, whose extended maps (M ∩ R)_{∞}(ẍ, ÿ, z̈) and (M/R)_{∞}(ẋ, ẏ, ż) are triconnected. Each of M ∩ R and M/R contains fewer edges and strictly fewer regions than M.

Proof. Deleting from M_{∞} any pair of vertices in M leaves every remaining vertex ν ∈ M ∩R connected to {ẍ, ÿ, z̈}, because every path connecting ν to ∞ in M_{∞} passes through {ẍ, ÿ, z̈}. By the same argument, every vertex in M_{∞} that remains after deleting any pair of vertices in M is connected to R—and hence to τ—in the deletion. (The removal of the edges eü ensures that M/R has no bivalent vertices on the way to τ.) The fact that ẋ, ẏ, ż and ẍ, ÿ, z̈ can be chosen as axial vertices follows from the triconnectivity of the extended maps of M/R and M ∩ R. Now M has at least one region inside (resp. outside) R, because C is a simple cycle (resp. a proper ring). Thus M/R (resp. M ∩ R) has strictly fewer regions than M. The edge number inequality is obvious for M ∩ R. For M/R, the number of edges is at most E + 3, counting the edges to τ, where E is the number of edges in M ∖ R. But the number of edges in M is at least E + 3, because R contains the cycle C. □

Let M and N be planar maps with axial vertices (ẋ, ẏ, ż) and (ẍ, ÿ, z̈), respectively, such that M_{∞}(ẋ, ẏ, ż) and N_{∞}(ẍ, ÿ, z̈) are both triconnected. We now show how to glue N into M at a vertex τ ∈ M that is trivalent in M_{∞}. Let the counterclockwise ordered neighbors of τ be α, β, γ (one of which might be ∞) in M_{∞}. (Think of M and N as M/R and M ∩R from Lemma 3.1, respectively.) Start by replacing τ with a small triangle in M_{∞} (a ‘Y –Δ’ transformation), adding three new vertices in the process. This action requires working in M_{∞} rather than M if τ ∈ {ẋ, ẏ, ż}. Next, replace the new triangle and its interior with N, in such a way that α, β, γ ∈ M connect to the axial vertices ẍ, ÿ, z̈ ∈ N via edges eẍ, eÿ, ez̈, called tethers in M_{∞}. The result is an extended map for M ∪_{τ} N, the tethered gluing of N into M at τ. Contracting some or all of the tethers yields a gluing of N into M, provided the resulting map is simple and triconnected. The construction of the tethered gluing works at the level of grid surfaces. For instance, the hypotheses in the next lemma can easily be attained by scaling M. This is a key observation, making the induction in the proof of Theorem 5.1 possible. The left columns of Figures 5 and 4 illustrate examples of S_{V_{M}} , S_{V_{N}} , τ, and M ∪_{τ} N ↪ S_{V}.

Lemma 3.2 Let M ↪ S_{V_{M}} and N ↪ S_{V_{N}} be rigid embeddings with respective axial vertices ẋ, ẏ, ż and ẍ, ÿ, z̈, and suppose τ ∈ M_{∞}(ẋ, ẏ, ż) is trivalent. If U_{τ} has length at least m + 1 for U = X, Y, Z, then τ is the unique vector in V_{M} preceding τ + m1, where 1 = (1, 1, 1). If, in addition, |ü| ≤ m for u = x, y, z and

V = (V_{M} ∖ τ) ∪ (τ + V_{N})

then the rigid geodesics in S_{V} provide a rigid embedding of the map M ∪_{τ} N.

Proof. The orthogonal rays X_{τ} , Y_{τ} , Z_{τ} point toward α, β, γ (one of these may be ∞) in S_{V_{M}} because τ is trivalent. Each vertex ν ∈ V_{M} with ν ≠ τ has ν_{x} ≥ α_{x}, ν_{y} ≥ β_{y}, or ν_{z} ≥ γ_{z}. Indeed, if ν lies in [ẋ, τ, ẏ] (say), then considering where the orthogonal flow [ν, ż] intersects [τ, ẋ] ∪ [τ, ẏ] shows that either ν_{x} ≥ α_{x} or ν_{y} ≥ β_{y}. Thus τ ⪯ τ + m1 is unique in S_{V_{M}}; the vertex axiom for V is immediate. The part of S_{V} preceding τ + m1 equals τ + (the part of S_{V_{N}} preceding m1), by the uniqueness in M of τ ⪯ τ + m1. Thus every vertex, rigid geodesic, or bounded orthogonal ray in N ↪ S_{V_{N}} gets translated by τ to the corresponding feature in S_{V}. Similarly, the parts of S_{V} and S_{V_{M}} not preceded by τ agree, so any vertex, rigid geodesic, or bounded orthogonal ray in M ↪ S_{V_{M}} survives in S_{V}, as long as it is contained in a (perhaps unbounded) region of M_{∞} not containing τ, by the rigid region axiom.

The only orthogonal rays unaccounted for as yet for the rigid geodesic axiom are those leaving τ +ü and α, β, γ. Observe that τ +ü is the unique element of V on the orthogonal ray U_{τ} ⊂ S_{V_{M}}. Thus an orthogonal ray leaving τ + ü either points toward the corresponding one of α, β, γ whenever the latter is not ∞, or it points away from V_{M}. An orthogonal ray leaving α, β, γ either points back toward ü along a rigid geodesic eü, or it points away from τ + V_{N}. We conclude that the rigid geodesics in S_{V} form a planar map isomorphic to M ∪_{τ} N. □

4 Contracting rigid geodesics

Proposition 4.1 Let M be a planar map with axial vertices ẋ, ẏ, ż. Suppose e is the edge in the exterior cycle of M leaving ẋ toward ẏ, and that e borders no triangles in M_{∞}(ẋ, ẏ, ż). If M/e can be rigidly embedded in some grid surface, then so can M.

Proof. Letting ν ∈ M be the other endpoint of e, we have ν ≠ ẏ because the unbounded region of M_{∞} containing e is not a triangle. The edge in M leaving ν clockwise from e determines an edge f in any rigid embedding N ↪ S_{V} isomorphic to M/e. Note that f ∈ N does not contain the orthogonal ray Yẋ because f ≠ e; and f ⊅ Zẋ because ν sits between ẋ and ẏ. Therefore the orthogonal ray X_{ω} at the other endpoint ω of f in N points toward ẋ. Assume all coordinates of vectors in V are even, by scaling. The claim is that the rigid geodesics in S_{V∪ν} constitute a rigid embedding isomorphic to M, where the coordinates of ν are defined by

ν = (ν_{x}, ν_{y}, ν_{z}) = (|ẋ| − 1, ω_{y}, 0).

The addition of ν to V affects at most the rigid geodesics in N containing one of the following: an orthogonal ray X_{σ} for some vertex σ ∈ V pointing toward ẋ; an orthogonal ray at ν; or Yẋ. All other rigid geodesics lie behind the plane x = |ẋ| − 1. If σ_{y} < ω_{y}, then X_{σ} is unaffected by ν, while if σ_{y} ≥ ω_{y}, then ẋ and ν are the only elements of V preceding σ∨ẋ = σ∨ν + (1, 0, 0). Thus X_{σ} points toward ν if σ_{y} ≥ ω_{y}, because ẋ ⪯̸ σ∨ν. The three orthogonal rays X_{ν}, Z_{ν}, and Y_{ν} leaving ν point respectively toward ẋ, ω, and the vertex to which Yẋ ⊂ S_{V} points in N. Finally, Yẋ ⊂ S_{V∪ν} points toward ν. (Figure 3 illustrates the transition M/e ⇝ M.) □

In the situation of Lemma 3.1, gluing M ∩R into M/R may involve contracting some of the tethers in (M/R) ∪_{τ} (M ∩ R). For the rest of this section, let M ↪ S_{V_{M}} and N ↪ S_{V_{N}} be rigid embeddings having respective axial vertices ẋ, ẏ, ż and ẍ, ÿ, z̈, with τ ∈ M_{∞}(ẋ, ẏ, ż) a trivalent vertex having neighbors α, β, γ. Let B be the region of M ∪_{τ} N containing eÿ and ez̈.

Proposition 4.2 Assume that τ ≠ ẏ, that Yẋ points toward τ, and that no edge in M has vertices {ẋ, γ}. Contracting eẍ along with neither, either, or PSfrag replacements

e
f
ν
ẋ

⇝

PSfrag replacements

e
f
ν
ẋ
M/e  M

Figure 3: Uncontracting the lower-left edge

(if B has at least five vertices) both of ez̈ and eÿ in M ∪_{τ} N yields a planar map possessing a geodesic grid surface embedding.

Proof. Paragraph headings are included below to make parts of the proof easier to follow and cross-reference.

Plan of proof

Given the conditions of the present proposition, assume all hypotheses and notation of Lemma 3.2, as well; this is possible by Lemma 2.1. If |V_{N}| = n, scale M so that all coordinates of vectors in V_{M} are divisible by n + 1. Until further notice (see the special construction for (8), below), assume in addition that the orthogonal rays X_{τ} , Y_{τ} , Z_{τ} all have length exactly m + 1. Set

ν′ := τ + ν for ν ∈ V_{N}.

The plan of the proof is to split into a number of cases, each of which demands slightly different treatment. In every case, Lemma 2.1 allows a judicious choice of coordinates for vectors in V_{N}. Most often, omitting one or more of the vertices \{ẍ′, ÿ′, z̈′, β\} from V leaves a set \underline{V} such that the desired contraction of M ∪_{τ} N geodesically embeds into S\underline{V}; two of the cases require additional fiddling with the surviving vertices to get the desired grid surface.

Eight cases

Let A and B be the bounded regions of M ∪_{τ} N containing eẍ and eÿ, respectively. By the region axiom, we think of A = (A_{x}, A_{y}, A_{z}) and B = (B_{x}, B_{y}, B_{z}) as the vectors given by the joins of their vertices. Denote by A(u) the set of vertices of A having u-coordinate A_{u}. For instance, A(x) = {ẋ} = {α}, and β ∈ B(y). Here is the list of constructions yielding S\underline{V}. In each of (1)–(7), choose V_{N} so that every coordinate of every vector in V_{N} is at most n; we treat the last case (8) separately later, since it involves somewhat different choices. Construct \underline{V} from V = (V_{M} ∖ τ) ∪ (τ + V_{N}) by omitting the indicated vectors, and (in (5) and (8)) making the specified alterations.

(1) To contract only eẍ: omit ẍ′.

(2) To contract eẍ and eÿ: omit ẍ′, ÿ′.

To contract eẍ and ez̈...

(3) if no edge in N has endpoints {ẍ, z̈}: omit ẍ′, z̈′. if {ẍ, z̈} are the endpoints of an edge in N...

(4) and A_{z} > γ_{z}: omit ẍ′, z̈′.

(5) and A_{z} = γ_{z}: omit ẍ′, z̈′; then add 1 to ν_{z} for all ν ∈ A(z)∖γ. To contract eẍ, eÿ, and ez̈...

(6) if no edge in N has endpoints {ÿ, z̈}: omit ÿ′ after (3)–(5). if {ÿ, z̈} are the endpoints of an edge in N...

(7) and β_{x} ≥ γ_{x}: omit β after (3)–(5).

(8) and β_{x} < γ_{x}: make the special construction below.

In general, observe that the only vertices connected to ẍ, ÿ, or z̈ in M ∪_{τ} N are α, β, γ, and some vertices in N. Also, one of (6)–(8) must occur if B has at least 5 vertices. Representative instances of the cases (1)–(8) appear in Figures 4 and 5.

Omitting vertices

In general, omitting one or more elements from V always leaves a set of pairwise incomparable vectors. The vertex axiom will follow immediately in the applications below, in the sense that the surviving vertex vectors \underline{V} are in obvious bijection with the vertices of the desired map. To check the rigid geodesic axiom after omitting one vertex ν, we must verify that any orthogonal ray U pointing toward ν before the omission of ν points to some other uniquely determined surviving vertex afterwards. This will show that the surviving vertices \underline{V} define a rigid embedding L ↪ S\underline{V} for some map L. Specifically, L is obtained from M ∪_{τ} N by first deleting ν along with all of its incident edges, and then reconnecting the neighbors of ν to other surviving vertices according to where their orthogonal rays point. It is important to remember that some edges incident to ν may fail to reappear upon reconnecting its neighbors: these non-reappearing edges are precisely those rigid geodesics that, before the omission of ν, do not contain any orthogonal ray pointing toward ν. (There are at most three such edges, because each one must contain an orthogonal ray leaving ν.)

60 Ezra Miller

PSfrag replacements

... ⋯
...

⋮ ẍ′ ÿ′

z̈′ α β γ
S_{V}  ⇝^{omit ẍ′} result in case (1) ⇝^{omit ÿ′} result in case (2)

S_{V} in case (3) ⇝^{omit ẍ′}  S_{V∖ẍ′}  ⇝^{omit z̈′}  S_{V∖{ẍ′,z̈′}}

S_{V} in case (4) ⇝^{omit ẍ′}  S_{V∖ẍ′}  ⇝^{omit z̈′} result in case (4)

S_{V} in case (5) ⇝^{omit {ẍ′,z̈′}} S_{V∖{ẍ′,z̈′}}  ⇝^{add} result in case (5)

S_{V} in case (6) ⇝^{case (3)}  S_{V∖{ẍ′,z̈′}}  ⇝^{omit ÿ′} result in case (6)

Figure 4: Gluing grid surfaces: cases (1)–(6)

Documenta Mathematica 7 (2002) 43–90

result of case (3)  ⇝^{omit β}  result in case (7)

S_{V_{N}} and S_{V_{M}} in case (8)

special construction

⇝ contraction of ez̈

⇝^{omit {ẍ′,ÿ′}}  result in case (8)

Figure 5: Gluing grid surfaces: cases (7)–(8)

Scale principle

We chose the relative sizes of V_{N} and V_{M} so that some arguments in what follows can rely on the following principle: If ω, σ are two vectors whose coordinates are all divisible by n + 1, then ω ⪯ σ if and only if ω ⪯ σ + n1.

Rays leaving τ + V_{N}

An orthogonal ray leaving ν′ ∈ τ + V_{N} and pointing toward z̈′ in S_{V} must be Z_{ν′} ⊂ S_{V}. We claim that after omitting z̈′, the ray Z_{ν′} points toward γ, regardless of whether or not one or both of ẍ′, ÿ′ has already been omitted. Moreover, this statement remains valid after permuting the roles of x, y, z. To see why, suppose that ω ⪯ ν′∨γ for ω ∈ V. We must show that ω ∈ {ν′, z̈′, γ}. If ω ∈ τ + V_{N} then ω_{z} ≤ τ_{z} + |z̈| and thus ω ⪯ ν′∨z̈′, so ω ∈ {ν′, z̈′} because [ν′, z̈′] is a rigid geodesic (Lemma 3.2). When ω ∈ V_{M} ∖ τ, apply the scale principle with σ = γ∨z̈′, using the fact that γ∨ν′ ⪯ γ∨z̈′ + n1 because τ ⪯ z̈′, ν′ ⪯ τ + n1. The argument is invariant under permutation of x, y, z.

Proof of (1)

The rigid geodesics containing orthogonal rays X_{ν′} pointing toward ẍ′ before the omission and toward α afterwards account for all of the necessary edges in the contraction. It remains only to verify that Y_{α} ⊂ S_{V∖ẍ′} points toward the next vertex after ẍ′ whose z-coordinate is zero—that is, the counterclockwise next vertex after ẍ′ on the exterior cycle of M ∪_{τ} N. This easy argument is left to the reader, completing the proof of (1). Until the proof of (8), assume ẍ′ has been omitted.

Proof of (2)

The orthogonal rays pointing toward ÿ′ in S_{V∖ẍ′} are Y_{ν′} for some vertices ν ∈ V_{N}, the ray X_{β}, and possibly Y_{α} (if ẍ and ÿ are the vertices of an edge in N). The arguments in ‘Rays in τ + V_{N}’ and ‘Proof of (1)’ apply as well to the omission of ÿ′, including the fact that the ray X_{β} points toward the next vertex after ÿ′ whose z-coordinate is zero (which may be α). None of the edges incident to ÿ′ vanish (see ‘omitting vertices’), although X_{β} and the Y -orthogonal ray at height z = 0 pointing toward ÿ′ point toward each other after omitting ÿ′, effectively contracting eÿ.

Cases (3)–(5)

Every rigid geodesic incident to z̈′ in S_{V∖ẍ′} contains an orthogonal ray pointing toward z̈′, except the geodesic connecting α to z̈′, if there is one (this occurs in (4) and (5) only, where X_{}_{z̈′} points toward α in S_{V∖ẍ′}), and sometimes the geodesic connecting γ to z̈′. After omitting z̈′, we will verify the rigid geodesic axiom at γ separately for each of (3)–(5), by checking only that an orthogonal ray leaving γ and pointing toward z̈′ (if there is one) points instead to another surviving vertex after omitting z̈′. Any other orthogonal ray in S_{V∖ẍ′} either leaves some vector in τ + V_{N} before omitting z̈′ (these have been dealt with in a paragraph above), or points toward another vertex in V_{M} ∖ τ both before and after omitting z̈′. Verifying the rigid geodesic axiom will complete the proof unless the edges connecting α and γ to z̈′ (if these exist) both vanish upon omitting z̈′, for otherwise all of the edges in the contraction of ez̈ are accounted for as in the proofs of (1) and (2). Both geodesics vanish in (5) only: in (3), there is no edge connecting α to z̈′; while in (4), the region axiom implies γ_{y} = A_{y}, whence X_{γ} points toward z̈′. In (5), we show that the addition procedure reconstructs a rigid geodesic connecting α to γ.

Proof of (3)

If X_{γ} points toward z̈′ in S_{V∖ẍ′}, and ν′ is the vertex to which X_{}_{z̈′} points in S_{V∖ẍ′}, then X_{γ} points toward ν′ ∈ τ + V_{N} after omitting z̈′ by the scale principle (the hypothesis for (3) guarantees that ν′ ≠ ẍ′). A similar statement holds by switching the roles of x and y (but ν′ ∈ τ + V_{N} is always guaranteed to exist, since ÿ′ has not been omitted). This verifies the rigid geodesic axiom at γ.

Proof of (4)

The assumption A_{z} > γ_{z} implies A_{y} = γ_{y}, so that X_{γ} points toward z̈′ in S_{V∖ẍ′}. If ν ∈ V ∖ ẋ and ν_{y} < γ_{y}, then ν_{z} > γ_{z}, by the region axiom. The omission of z̈′ therefore causes the ray X_{γ} ⊂ S_{V∖{ẍ′,z̈′}} to point toward α.

Proof of (5)

The region axiom implies γ_{y} < τ_{y}, so X_{γ} does not point toward z̈′. When Y_{γ} points toward z̈′, the rigid geodesic axiom holds for S_{V∖{ẍ′,z̈′}} by the argument in the proof of (3), although no elbow geodesic connects α to γ in S_{V∖{ẍ′,z̈′}}. Now we verify that the addition procedure outputs a rigid geodesic embedding, and that an edge connecting α to γ is the only new rigid geodesic. We can safely ignore all orthogonal rays contained in rigid geodesics on the positive side of the plane y = γ_{y}. All of the vertices ω ∉ A satisfying ω_{y} ≤ γ_{y} must also satisfy ω_{z} > γ_{z} by the rigid region axiom. The adding rule therefore causes X_{γ} to point toward α after omitting z̈′. The orthogonal rays leaving vertices originally in A(z) ∖ γ still point to the same vertices, by the scale principle. If ω ∉ A(z) ∪ {α}, then any orthogonal ray U_{ω} pointing toward ν ∈ A(z) before the addition still points toward the same vertex ν afterwards, because ω_{z} > ν_{z}, whence the join ν∨ω remains unaffected. Finally, if Z_{α} points toward a vertex in A(z) before the addition procedure, then Z_{α} still points to the same vertex afterwards, by the scale principle, while Y_{α} remains unaffected.

Proof of (6)

No new phenomena occur here; see Proof of (3).

Technical lemma

The following result will be applied in the proofs of (7) and (8). For the proof of (8), note that it holds after any rescaling of V_{M} as in Lemma 2.1.

Let ω ∈ V_{M}. If τ_{x} ≥ ω_{x} ≥ β_{x}, then ω ∈ {τ, β} or ω_{z} ≥ γ_{z}.
Similarly, if τ_{y} ≥ ω_{y} ≥ α_{y} = 0, then ω ∈ {τ, α} or ω_{z} ≥ γ_{z}.

Proof of technical lemma. Suppose τ_{x} ≥ ω_{x} ≥ β_{x}, but ω_{z} < γ_{z}. If ω ≠ τ, then ω_{y} ≥ β_{y} by the uniqueness in Lemma 3.2 of τ among vectors preceding τ + m1 in V_{M}. Thus β ⪯ ω, so β = ω. Swap the roles of x and y to prove the other statement.

Proof of (7)

First claim: The only orthogonal rays pointing toward β are Y_{}_{ÿ′}, and X_{ν} for some vertices ν ∈ M. These vertices ν all have ν_{z} < m + 1. The final sentence of the first claim is easy, because otherwise γ ⪯ β∨ν. For the rest of the claim, use the inequalities B_{x} = τ_{x} > β_{x} ≥ γ_{x} and B_{y} = β_{y} > τ_{y} ≥ γ_{y}, which follow from the hypotheses of (7). These imply γ_{z} = m + 1 = B_{z}, thanks to the region axiom. By the technical lemma, any orthogonal ray Y_{ν} pointing toward β in S_{V} (and therefore in S_{V∖{ẍ′,z̈′}}) must have either ν_{x} ≥ τ_{x} or ν_{z} ≥ m + 1. When ν_{x} ≥ τ_{x}, we get ν_{y} < β_{y} and hence ÿ′ ⪯ ν∨β, so ν = ÿ′. The case ν_{z} ≥ m + 1 is actually impossible, for it implies γ ⪯ ν∨β, so ν = γ is connected to β by an edge in M ∪_{τ} N; this cannot happen in (7) if B has at least five vertices. The fact that β_{z} = 0 rules out Z_{ν} pointing toward β, completing the proof of the first claim. Now we verify that X_{ν} ⊂ S_{V∖{ẍ′,β,z̈′}} points toward ÿ′ whenever X_{ν} ⊂ S_{V∖{ẍ′,z̈′}} points toward β. In other words, we need ω ⪯ ν∨ÿ′ for ω ∈ V to imply ω ∈ {ẍ′, z̈′, ÿ′, β, ν}. If ω ∈ τ + V_{N}, then ω_{x} = ÿ′_{x} = τ_{x} implies ω ∈ {ÿ′, z̈′}. If ω ∈ V_{M} ∖ τ, then either ω_{x} ≤ β_{x}, in which case ω ⪯ β∨ν implies ω ∈ {β, ν}, or ω_{z} < m + 1 in addition to τ_{x} ≥ ω_{x} ≥ β_{x}, in which case ω = β by the technical lemma. It is easy to verify that ÿ′ points toward the next vertex after β having zcoordinate zero. Note that such a next vertex must exist, since the rigid geodesic leaving β and containing Z_{β} strictly decreases in x. This completes the proof of (7).

Special construction for (8)

The meet (componentwise minimum) of τ and γ is τ∧γ = (γ_{x}, γ_{y}, 0) = γ − (0, 0, m + 1) since Z_{τ} points toward γ in S_{V_{M}}. Observe that

ω ∈ V_{M} and τ∧γ ⪯ ω implies ω ∈ {τ, γ}.  (9)

Indeed, if τ ⪯̸ ω but τ∧γ ⪯ ω, then either τ_{x} ≥ ω_{x} ≥ γ_{x} or τ_{y} ≥ ω_{y} ≥ γ_{y}. The hypothesis γ_{x} > β_{x} of (8) plus the technical lemma imply ω_{z} ≥ γ_{z}, whence γ ⪯ ω. It follows from (9) that the set

\underline{V}_{M} = (V_{M} ∖ \{τ, γ\}) ∪ τ∧γ

of vectors determines a grid surface S_{\underline{V}_{M}}. Use the freedom afforded by Lemma 2.1 to rechoose V_{M} and m so that n + 3 divides all coordinates of vectors therein, while γ_{z} as well as the lengths of the orthogonal rays X_{τ∧γ} and Y_{τ∧γ} ⊂ S_{\underline{V}_{M}} equal m + 2. Applying (9) again, further alter V_{M} by moving τ so that τ − τ∧γ equals (1, 0, 0), (0, 1, 0), or (1, 1, 0), depending on whether τ_{y} = γ_{y}, τ_{x} = γ_{x}, or neither. Now choose V_{N} so that all of its nonzero x and y-coordinates lie in the interval [m − n, m], but all of its z-coordinates are no greater than n. Let

\underline{V} = (\underline{V}_{M} ∖ τ∧γ) ∪ (τ∧γ + V_{N}),

and denote by \underline{ν} the vector τ∧γ +ν for ν ∈ V_{N}. Our (final) goal is to show that the rigid geodesics in S\underline{V} constitute an embedding of (M ∪_{τ} N)/ez̈. After that, eẍ and eÿ can be contracted by omitting \underline{ẍ} and \underline{ÿ}, using the same arguments appearing in Scale principle, Rays leaving τ +V_{N}, Proof of (1), and Proof of (2).

Proof of (8)

Begin by mimicking as closely as possible the proof of Lemma 3.2. First, τ∧γ is the unique vector in \underline{V}_{M} preceding τ∧γ + m1, by Lemma 3.2 applied to V_{M}; this is why τ needs to be so close to τ∧γ. The vertex axiom for S\underline{V} is immediate. Moreover, the part of S\underline{V} that precedes τ∧γ +m1 equals τ∧γ +(the part of S_{V_{N}} preceding m1). Thus every vertex, rigid geodesic, or bounded orthogonal ray in N ↪ S_{V_{N}} gets translated by τ∧γ to the corresponding feature in S\underline{V}. Similarly, the parts of S\underline{V} and S_{\underline{V}_{M}} not preceded by τ∧γ agree, so any vertex, rigid geodesic, or bounded orthogonal ray in M ↪ S_{\underline{V}_{M}} survives in S_{V} whenever it is contained in a (perhaps unbounded) region of M_{∞} not containing τ or γ, by the rigid region axiom. The only orthogonal rays unaccounted for as yet for the rigid geodesic axiom are X\underline{ẍ}, Y\underline{ÿ}, Y_{α}, X_{β}, Z\underline{z̈}, and any orthogonal ray U_{ν} ⊂ S\underline{V} such that U_{ν} ⊂ S_{V_{M}} points toward γ and ν ≠ τ. (Neither the rigid geodesic connecting τ to γ in M nor the orthogonal rays leaving γ in S_{V_{M}} play roles in this verification.) The only case requiring significant effort are the U_{ν} rays, which must point toward \underline{z̈} in S_{V}. Suppose ω ⪯ ν∨\underline{z̈} for some ω ∈ \underline{V}. The technical lemma and (9) imply that ν_{z} ≥ γ_{z} for any τ ≠ ν ∈ V_{M} pointing toward γ, whence ν∨\underline{z̈} = ν∨γ for any such ν. Therefore ω ≠ ν implies ω ∈ τ∧γ + V_{N}. On the other hand, either ν_{y} < β_{y} or ν_{x} < α_{x}, because otherwise β or α precedes ν∨γ = ν∨\underline{z̈}. By the choice of scaling, ω_{y} ≤ ν_{y} < β_{y} forces ω_{y} ≤ ν_{y} ≤ β_{y} − (n + 3) < γ_{y} + m − n, whence ω = \underline{z̈} whenever ω ∈ τ∧γ + V_{N}. This argument also works with the roles of x and y switched. The above reasoning proves that the rigid geodesics in S\underline{V} embed some planar map L. To conclude that L ≅ (M ∪_{τ} N)/ez̈, one last item remains: show that no geodesics in M vanish. More precisely, whenever X_{γ} or Y_{γ} does not point toward τ in V_{M}, we require it to point toward a vertex in V_{M} that points back toward γ in S_{V_{M}}. Suppose Y_{γ} ⊂ S_{V_{M}} does not point toward τ. Then γ_{x} < τ_{x} = B_{x}, whence γ_{z} = B_{z} by the region axiom, because γ_{y} < β_{y} = B_{y}. If B(z) = {γ}, then Y_{γ} ⊂ S_{V_{M}} must point toward β, because β_{x} < γ_{x}. This is impossible whenever the region B in M ∪_{τ} N has at least five vertices, by the hypothesis of (8) stipulating that [ẍ, z̈] is an edge in N. The analogous argument works for X_{γ}, but the reason why X_{γ} cannot point toward α is different: it is ruled out by the statement of the Proposition. □

Recall the conventions set before the statement of Proposition 4.2.

Proposition 4.3 Suppose τ = ẋ is trivalent. Contracting neither, either, or (if B has at least five vertices) both of ez̈ and eÿ in M ∪_{τ} N yields a planar map possessing a rigid embedding.

Proof. Pretend eẍ has already been contracted, and apply the constructions in the proofs of (6)–(8) in Proposition 4.2. (In reality, only (6) and (7) are required here, given the symmetry switching the roles of y and z). □

5 Triconnectivity and rigid embedding

Theorem 5.1 (Rigid embedding) A planar map M with given axial vertices ẋ, ẏ, ż can be rigidly embedded in a grid surface if and only if the extended map M_{∞}(ẋ, ẏ, ż) is triconnected. In particular, every triconnected planar map can be rigidly embedded.

Proof. (⇒) Let M ↪ S_{V} be an axial rigid embedding, and delete two vertices ν, ω from M_{∞}. If {ν, ω} ⊂ {ẋ, ẏ, ż} then each remaining vertex has an orthogonal flow to the third axial vertex, by independence of the orthogonal flows to ẋ, ẏ, ż. If {ν, ω} ⊄ {ẋ, ẏ, ż} then what remains of the exterior cycle is connected, and every vertex in the deletion still has an orthogonal flow to the exterior cycle. (⇐) Induct on the sum of the number of regions and the number of edges in M, observing that the minimal sum of five is attained only when M is a triangle. Assume the notation of Section 3, and suppose M is not a triangle. Letting e be the edge leaving ẋ towards ẏ on the exterior cycle of M, we claim that at least one of the following occurs:

1. The endpoints of e are ẋ and ẏ.

2. The edge e does not border a triangle in M_{∞}(ẋ, ẏ, ż), and M/e is triconnected.

3. The edge e does not contain ẏ, and M contains a proper ring C for which \underline{ẍ} = ∞.

4. The edge e does not contain ẏ, and M contains a proper ring C for which

(a) \underline{ẍ} = ẍ = ẋ;

(b) ÿ is the other endpoint of e, and ÿ ≠ ẏ (that is, \underline{ÿ} ≠ ∞); and

(c) \underline{z̈} does not lie between ẋ and ż on the exterior cycle of M, and no single edge outside the region bounded by C has endpoints \{ẋ, \underline{z̈}\}.

If the first three cases do not occur, then Proposition 1.1 produces a ring C in which ẍ and ÿ are the two endpoints of e, while z̈ is a vertex in F ∩ F′ as in Proposition 1.1.2. Note that C is proper because ÿ ≠ ẏ. Let C be a maximal such ring. The first half of 4(c) holds; if not, construct a ring satisfying option 3 as follows: replace the arc of C connecting ẋ to z̈ with the arc traversing the exterior cycle from ẋ to \underline{z̈} and then ez̈ (the latter only if z̈ ≠ \underline{z̈}). The second half of 4(c) also holds, for if an edge f outside C connects ẋ to \underline{z̈}, then replace the arc of C connecting ẋ to z̈ in C by f and ez̈ (if \underline{z̈} ≠ z̈). The resulting cycle is a larger ring satisfying the condition defining C, contradicting maximality. Finally, 4(a) holds by the failure of option 3: C does not contain the edge of M leaving ẋ toward ż on the exterior cycle of M. Given the first option, M has a proper ring C, with \underline{z̈} = z̈ = ż, containing every bounded region of M except the one containing e. Let M ∩ R ↪ S_{V} be a geodesic embedding, where R is the union of regions contained within C. Leaving ẋ, ẏ fixed while adding 1 to the z-coordinates of every other vector in V yields a grid surface S_{V′} whose rigid geodesics constitute an embedding of M; the easy proof is omitted. Given the second option, use Proposition 4.1. Given the third or fourth option, use Lemma 3.1 with M = M/R and N = M ∩ R, along with Proposition 4.3 for option 3, or Lemma 3.2 and Proposition 4.2 for option 4. The ‘five vertex’ conditions in Propositions 4.2 and 4.3 are always satisfied when reconstructing M from the tethered gluing (M/R) ∪_{τ} (M ∩ R), because M is simple and triconnected. □

The next corollary clarifies the close connection between grid surfaces and order dimension for posets. It shows that Theorem 5.1 generalizes the three-variable special case of [BPS98, Theorem 6.4], which is presented in the equivalent language of monomial ideals.

Corollary 5.2 (Brightwell–Trotter [BT93]) The vertices, edges, and bounded regions of any triconnected planar map form a partially ordered set of order dimension ≤ 3.

Proof. Theorem 5.1 and Corollary 2.5. □

Example 5.3 Theorem 5.1 is stronger than Corollary 5.2, even for triconneted maps. In general, every inclusion of the vertex-edge poset of M into ℕ^{3} yields an inclusion of the vertex set V ↪ S_{V} such that each edge of M is a rigid geodesic in S_{V}. What fails is that there may be orthogonal rays in S_{V} that are not contained in any edges of M. Faces such as the central face in Figure 6 are then forced to lie off of S_{V}. □

Remark 5.4 Rigid embeddings give a fresh perspective on a standard fact, known as Menger’s theorem: If G is a triconnected planar graph and ν, ω ∈ G are distinct vertices, then there are three independent paths from ν to ω in G. To explain Menger’s theorem via Theorem 5.1, let M be a plane drawing of G, and suppose e_{1}, …, e_{r} are the edges of M containing ν, in cyclic order. Form PSfrag replacements

↪

Figure 6: A vertex-edge-face poset embedding that is not a geodesic embedding

a new map M′ by drawing a small circle C around ν and adding new vertices ν_{1}, …, ν_{r} where e_{1}, …, e_{r} intersect C. Then set M^{ν} = del(M′; ν), with underlying graph G^{ν}. Clearly G^{ν} is triconnected. Choose a plane drawing of G^{ν} in which C is the exterior cycle, and let G^{ν} ↪ S be an axial geodesic embedding compatible with some (any) choice of axial vertices ẋ, ẏ, ż ∈ C. The orthogonal flows from ω to ẋ, ẏ, ż in G^{ν} first intersect C at points ν_{i_{x}}, ν_{i_{y}}, ν_{i_{z}}, giving rise to truncated orthogonal flows [ω, ν_{i_{u}}] for u ∈ {x, y, z}. Connecting [ω, ν_{i_{u}}] to ν via the arc in G between ν_{i_{u}} and ν yields independent paths in G from ω to ν.

Part II Monomial ideals

6 Betti numbers

Let k be a field, and consider the polynomial ring R = k[x, y, z] with the ℤ^{3}- grading in which deg(x) = (1, 0, 0), deg(y) = (0, 1, 0), and deg(z) = (0, 0, 1). Use I_{V} = ⟨m^{ν} | ν ∈ V⟩ to denote the ideal generated the monomials m^{ν} = x^{ν_{x}}y^{ν_{y}}z^{ν_{z}} for ν ∈ V. The integer points in ⟨V⟩ coincide with the exponent vectors on monomials in I_{V}, and V is axial if and only if I_{V} is artinian, containing a power of each variable. Any principal monomial ideal ⟨m⟩ is a free ℤ^{3}-graded R-module of rank 1. If ϕ is ℤ^{3}-graded homomorphism ⨁⟨m_{q}⟩ ⟵ ⨁⟨m_{p}⟩ of degree zero, then we can express ϕ as a monomial matrix. This is a matrix whose entries λ_{pq} ∈ k are scalars, and whose p^{th} row (resp. q^{th} column) is labeled by the monomial m_{p} (resp. m_{q}) that generates the corresponding p^{th} source (resp. q^{th} target) summand. Of course, λ_{pq} = 0 whenever m_{q} does not divide m_{p}, because then there are no nonzero ℤ^{3}-graded maps ⟨m_{q}⟩ ← ⟨m_{p}⟩. The map ϕ is called minimal if also λ_{pq} = 0 whenever m_{p} = m_{q}. See [Mil00a, Section 2] for more on monomial matrices. We consider free resolutions of I_{V} that are exact sequences having the form

F. : 0 ← I_{V} ⟵^{ϕ_{0}} F_{0} ⟵^{ϕ_{1}} F_{1} ⟵^{ϕ_{2}} F_{2} ← 0,  (10)

in which F_{i} ≅ ⨁_{p}⟨m_{ip}⟩ for some (finite set of) monomials m_{ip} ∈ R. We call F. minimal if ϕ_{1} and ϕ_{2} are minimal (for any such direct sum decomposition). The Betti number β_{i,α}(I_{V}) is the number of m_{ip} equal to m^{α}, when F. is minimal. This homological data reflects the local properties of S_{V} near the vector α via the Koszul simplicial complex of V at α ∈ ℕ^{3},

K_{α}(V) = {σ ∈ {0, 1}^{3} | α − σ ∈ ⟨V⟩},

which is a subcomplex of the abstract triangle ({0, 1}^{3}, ⪯).

Proposition 6.1 ([Hoc77, Roz70]) β_{i,α}(I_{V}) = dim_{k} H̃_{i−1}(K_{α}(V); k) is the dimension of the (i−1)^{st} reduced simplicial homology of K_{α}(V) with coefficients in k.

The small number of simplicial complexes on three vertices seriously limits the possibilities for nonzero Betti numbers.

Lemma 6.2 If V ⊂ ℕ^{3} and i ∈ ℕ then β_{i,α}(I_{V}) ≠ 0 for at most one α ∈ ℤ^{3}. If β_{i,α} is nonzero then β_{i,α} = 1 unless K_{α}(V) has 3 vertices and no edges (so β_{1,α} = 2).

Proof. Use the previous proposition, and list all simplicial complexes on 3 vertices. □

7 Cellular resolutions

Suppose M is a cell complex (precisely, a finite CW complex) of dimension 2 whose cells P have vector labels α_{P} ∈ ℕ^{3}, in such a way that α_{P} ⪯ α_{P′} if P lies in the closure of P′. For instance, if the vertices have natural labels, then define α_{P} to be the join of the labels on the vertices of P. Such a labeled cell complex determines monomial matrices ϕ_{vertex}, ϕ_{edge}, and ϕ_{region} for a cellular free complex F_{M}, by labeling the rows and columns of matrices for the boundary map of the ordinary chain complex of M with the monomials m^{α_{P}}. Using P also to denote the basis vector of a rank 1 free R-module ⟨m^{α_{P}} ⟩, the cellular free complex F_{M} takes the form

ϕ_{vertex}  ϕ_{edge}  ϕ_{region} 0 ← I_{V} ⟵ ⨁_{vertices ν} R · ν ⟵ ⨁_{edges e} R · e ⟵ ⨁_{regions F} R · F ← 0.

(11)

We say M supports F_{M}; see [BS98, Mil00a] for more on cellular monomial matrices. Our main examples of labeled cell complexes are of course the geodesically embedded planar maps M ↪ S_{V}, whose labels are determined by the obvious vertex labels by taking joins. We shall see in the next section that this cellular free complex is exact and minimal, so it provides a cellular minimal free resolution of I_{V}. Unfortunately, there are monomial ideals whose associated grid surfaces contain no geodesically embedded map.

Example 7.1 Let I_{V} = ⟨x, y, z⟩^{2} = ⟨x^{2}, y^{2}, z^{2}, xy, xz, yz⟩. The orthogonal rays X_{yz}, Y_{xz}, Z_{xy} meet at a single point not in V, so there can be no planar map geodesically embedded in S_{V}. However, ⟨x, y, z⟩^{2} still has a minimal cellular resolution: connect the midpoints of the edges of a triangle, and delete any one of the three interior edges. Label the resulting planar map M with x^{2}, y^{2}, z^{2} on the corners of the outside triangle; xy between x^{2} and y^{2}; yz between y^{2} and z^{2}; and xz between x^{2} and z^{2}. Label the edges and regions of M by the joins of their vertex labels. □

Although the map M in the above example fails to embed geodesically in S_{V}, the extended map M_{∞}(x^{2}, y^{2}, z^{2}) is still triconnected. This phenomenon is general. In the following proposition, we do not require planarity of M, so we use G_{∞}(ẋ, ẏ, ż) to mean the abstract graph obtained from G by adding a new vertex ∞ connected to each of ẋ, ẏ, ż.

Proposition 7.2 If the labeled cell complex M supports a minimal free resolution of an artinian ideal I_{V}, and the 1-skeleton of M is a graph G, then the extended graph G_{∞}(ẋ, ẏ, ż) is triconnected, where ẋ, ẏ, ż are the vertices whose labels lie on the axes.

Proof. Given ν ∈ V with ν ≠ ż, the orthogonal ray Z_{ν} leaving ν has its head at some vector α ∈ ℕ^{3} for which K_{α}(V) is disconnected; indeed, the vertex (0, 0, 1) is isolated in K_{α}(V). Choose a vertex ω′ ≠ ν preceding α, so that m^{α−ν}ν − m^{α−ω′}ω′ ∈ ker(ϕ_{vertex}). Since α − ν = Z(ν) lies on the z-axis Z, there must be an edge e ∈ M connecting ν to a vertex ω (possibly different from ω′) such that ϕ_{edge}(e) = z^{d}ν −m^{ν∨ω−ω}ω for some d ∈ ℕ. Clearly ω_{x} ⪯ ν_{x} and ω_{y} ⪯ ν_{y}. Repeating the procedure with ω in place of ν, and with x or y in place of z, we find that M contains paths analogous to orthogonal flows from ν to each axial vertex ẋ, ẏ, ż. As in Section 2, these paths are independent, intersecting only at ν. □

8 Graphs to minimal resolutions

Lemma 8.1 If M ↪ S_{V} is a geodesic embedding, then β_{1,α}(I_{V}) ≠ 0 if and only if α = ν∨ω for some elbow geodesic [ν, ω] ∈ M, and β_{1,ν∨ω}(I_{V}) = 1 in this case.

Proof. Assume β_{1,α}(I_{V}) ≠ 0. Then K_{α}(V) is disconnected by Proposition 6.1, and this occurs if and only if K_{α}(V) contains an isolated vertex. An isolated vertex of K_{α}(V) occurs if and only if α lies on an orthogonal ray leaving some vertex ν ∈ V. Therefore, α = ν∨ω for some ω ≠ ν by the edge axiom. Since [ν, ω] is an elbow geodesic, K_{ν∨ω}(V) cannot have three isolated points because three orthogonal rays cannot meet at the point ν∨ω in the relative interior of the edge [ν, ω] of M. □

Here is a result that sometimes reduces statements about arbitrary geodesic or rigid embeddings to axial ones. Its straightforward proof is omitted.

Lemma 8.2 Append axial vertices to V by letting \overline{V} = V ∪ \{u̇ | S_{V} ∩ U = ∅\} for sufficiently large |u̇|. A planar map M is geodesically embedded in S\overline{V} if and only if N = del(M; \overline{V} ∖ V) is geodesically embedded in S_{V}. Furthermore, M ↪ S\overline{V} is rigidly embedded if and only if N ↪ S_{V} is rigidly embedded.

Lemma 8.3 Let M ↪ S_{V} be a geodesic embedding, and S_{V}^{max} the set of points in S_{V} maximal under the partial order induced by the relation ⪯ on ℝ^{3}. Then α ∈ S_{V}^{max} ⇔ β_{2,α}(I_{V}) ≠ 0 ⇔ α = α_{F} is the join of the vertices in a bounded region F of M.

Proof. For the equivalence α ∈ S_{V}^{max} ⇔ β_{2,α}(I_{V}) ≠ 0, use the fact that K_{α}(V) is the boundary of the triangle; the easy details are omitted. The equivalence α ∈ S_{V}^{max} ⇔ α = α_{F} holds for all vertex sets V if it holds when V is axial. Indeed, using the notation and result of Lemma 8.2, the maximal points of S_{V} are still maximal in S\overline{V}, while the points in Smax ; \overline{V} ∖ S_{V}^{max} are exactly those having u-coordinate |u̇| for some u such that S_{V} ∩ U = ∅, by the region axiom applied to S\overline{V}. The bounded regions of N having such joins disappear upon deleting u̇. Assume henceforth that M ↪ S_{V} is axial. If ρ ∈ S_{V} has some coordinate ρ_{u} = 0, then ρ ∉ S_{V}^{max} because adding ε to any other coordinate of ρ yields another point in S_{V}. Therefore each maximal point of S_{V} lies in a bounded region of M. When F is such a bounded region, the region axiom implies α_{F} ∈ S_{V}^{max}, because some vertex ν ∈ V strongly precedes α_{F} +εu̇ for any ε > 0 and u ∈ {x, y, z}. Every point ρ on a given elbow geodesic [ν, ω] precedes ν∨ω by definition, so ρ ⪯ ν∨ω ⪯ α_{F} whenever [ν, ω] ⊆ F. Any point σ on the line segment in ℝ^{3} connecting ρ to α_{F} therefore satisfies ρ ⪯ σ ⪯ α_{F}, whence σ ∈ S_{V}. It follows that F is the union of such line segments, so every point of F precedes α_{F}. □

Theorem 8.4 Given a geodesic embedding M ↪ S_{V}, the cellular free complex F_{M} is a minimal free resolution of I_{V}.

Proof. Since β_{i,α}(I_{V}) ≠ 0 if and only if β_{i,α}(I_{V}) = 1 by Lemmas 6.2 and 8.1, it makes sense simply to speak of the i^{th} Betti degrees α, for which β_{i,α} = 1. The zeroth, first, and second Betti degrees are the labels on the vertices, edges, and regions of M, respectively, by Lemmas 6.2, 8.1, and 8.3. Any minimal free resolution F. of I_{V} as in (10) therefore takes the form of (11), at least as a homologically graded module; that is, F. ≅ F_{M} abstractly as modules. We need to show that some choice of this abstract isomorphism is a homomorphism of complexes. Identifying the homological degree zero parts of F. and F_{M}, the zeroth homology of F_{M} surjects onto I_{V} because the image of ϕ_{edge} is clearly contained in the kernel of ϕ_{0}. Since F. is exact and F_{M} is a complex of free modules, there exists a homomorphism ψ : F_{M} → F. lifting the surjection on zeroth homology and the isomorphism in homological degree zero. Suppose e ∈ F_{M} maps to ψ(e) = ∑ m_{j}e′_{j}, where each m_{j} ∈ R is a monomial with nonzero scalar coefficient, and each e′_{j} denotes the generator of F_{1} corresponding to the edge e_{j} ∈ M. The elbow geodesic e = [ν, ω] in M contains an orthogonal ray U_{ν}, so that ±ϕ_{1}(∑ m_{j}e′_{j}) = m^{ν∨ω−ν}ν − m^{ν∨ω−ω}ω, where the first term is m^{ν∨ω−ν}ν = m^{U(ν)}ν. Thus m^{U(ν)}ν = u^{|U_{ν}|}ν appears with nonzero scalar coefficient in ϕ_{1}(m_{j}e′_{j}) for some j. Since there is a unique first Betti degree α satisfying α − ν ∈ U, namely α_{e} = ν∨ω, it must be that e′_{j} = e′ and m_{j} is a nonzero scalar. Nakayama’s lemma implies ψ_{1} : (F_{M})_{1} → F_{1} is surjective, and hence an isomorphism by rank considerations. No summand R · F ⊂ F_{M} can map to zero in F_{2} because ϕ_{region}(F) is nonzero in F_{M}, and ψ is an isomorphism in homological degree 1. On the other hand, the second Betti degrees are pairwise incomparable by Lemma 8.3. Thus ψ(F) is some nonzero scalar multiple of the unique generator of F_{2} in degree α_{F}. The map ψ is therefore an isomorphism in homological degree 2, completing the proof. □

Corollary 8.5 A planar map M with axial vertices ẋ, ẏ, ż supports a minimal free resolution of an artinian monomial ideal if and only if M_{∞}(ẋ, ẏ, ż) is triconnected. In particular, every triconnected planar map supports a minimal free resolution.

Proof. ‘Only if’ is Proposition 7.2; apply Theorem 8.4 to Theorem 5.1 for ‘if’.

□

9 Uniqueness vs. nonplanarity

Continuing with the analogy at the beginning of the Introduction, circle packings and polytopes that realize planar graphs are unique up to Möbius transformation and spherical rotation, respectively (see [Zie95] for discussion and references). Rigid embeddings M ↪ S_{V} for a fixed planar map are similarly not unique: at the very least, any order-preserving bijection of V as in Lemma 2.1 gives another rigid embedding. Of course, such bijections affect neither the combinatorics nor the algebra. In fact, rigid embeddings are uniquely determined by the algebraic properties of the grid surface in question, specifically the minimal free resolution of the corresponding monomial ideal.

Corollary 9.1 When M ↪ S_{V} is rigidly embedded, M is the unique cell complex supporting a minimal cellular free resolution of I_{V}.

Proof. Let N be a labeled cell complex supporting a minimal cellular free resolution of I_{V}. The abstract graph underlying N (the 1-skeleton) coincides with that of M by Theorem 8.4 and rigidity. The label α_{F} on any region F of N is a second Betti degree of I_{V}, and hence coincides with the label on a region F′ of M by Theorem 8.4. The boundary of F in N is a cycle of edges

Planar Graphs as Minimal Resolutions 73

PSfrag replacements

500 050 005 211 121 302 032 430 340

Figure 7: Nonplanar minimal free resolution

whose degrees precede α_{F}. The only such cycle consists of all the edges whose degrees precede α_{F}, by the rigid region axiom for F′ in M (by Lemma 8.2 the rigid region axiom holds for nonaxial grid surfaces). □

Nonrigid monomial ideals can have many distinct isomorphism classes of minimal cellular resolutions; [MS99, Figure 4] depicts an example of this phenomenon. In fact, the bad behavior gets much worse.

Example 9.2 Minimal cellular resolutions of ideals in k[x, y, z] need not be supported planar cell complexes. In fact, explicit examples crop up with even the smallest violations of rigidity. For instance, let

V = {(4, 3, 0), (3, 4, 0), (3, 0, 2), (2, 1, 1), (1, 2, 1), (0, 3, 2)}

and \overline{V} = V ∪ \{(5, 0, 0), (0, 5, 0), (0, 0, 3)\}. The cell complex M depicted in Figure 7 consists of five triangles in addition to the three quadrilaterals with vertices

{500, 430, 121, 211}, {430, 121, 211, 341}, {050, 121, 211, 340}.

Label the edges and regions by the joins of their vertex labels. That M supports a minimal free resolution of I\overline{V} can be checked by verifying for each α ⪯ (5, 5, 3) that M_{⪯α} is acyclic [BS98, Corollary 1.3]. That M cannot be planar follows by contracting the edges labeled 530 and 350 while deleting the edges labeled 312 and 132 to get the complete graph K_{5} as a minor of the 1-skeleton. □

10 Deformation and genericity

Given a finite subset W ⊂ ℝ^{3}, write ∨W for the join of the vectors in W, and set m^{W} = m^{∨W}. Following [BPS98], define the Scarf complex of V,

Δ_{V} = {W ⊆ V | if ∨W′ = ∨W for some W′ ⊆ V then W′ = W},

to consist of the subsets whose joins are uniquely attained. It is an easy (but not obvious) fact that Δ_{V} is a simplicial complex. Each face W ∈ Δ_{V} comes with a natural label ∨W, and the resulting cellular free complex F_{Δ_{V}} is called the free Scarf complex of I_{V}. The Scarf complex is planar by virtue of its containment in the hull complex [BS98], so the union of its edges and vertices is a planar map. This planar map has already appeared, in Section 2: two vertices ν, ω ∈ V are connected by a rigid geodesic if and only if {ν, ω} ∈ Δ_{V}. Under special circumstances, the Scarf complex is rigidly embedded in S_{V}. To be precise, call V strongly generic if no two distinct elements of V share a nonzero coordinate. In other words, ν_{u} = ω_{u} ≠ 0 for some u ∈ {x, y, z} implies ν = ω.

Corollary 10.1 (Bayer–Peeva–Sturmfels [BPS98, §3]) The free Scarf complex F_{Δ_{V}} minimally resolves I_{V} when V is strongly generic.

Proof. Strong genericity easily implies that every orthogonal ray is contained in a rigid geodesic, so the Scarf graph rigidly embeds in S_{V}. It is straightforward to verify that the labels on triangles (2-dimensional faces) in Δ_{V} are maximal in S_{V}. Furthermore, every maximal point of S_{V} has exactly three vectors in V preceding it by Lemma 8.3, the region axiom, and strong genericity. Therefore, all maximal points are labels on regions in Δ_{V}, and the result holds by Theorem 8.4. □

Since the definition of the Scarf complex depends only on the coordinatewise order of the exponents of the generators, it also makes sense for (formal) monomials with real exponents in ℝ^{n}. This makes way for the following definition. Let ℚ denote the rational numbers. A deformation ϵ of V is a choice of vectors ϵ^{ν} = (ϵ_{x}^{ν}, ϵ_{y}^{ν}, ϵ_{z}^{ν}) ∈ ℚ^{3} for each ν ∈ V satisfying

ν_{u} < ω_{u} ⇒ ν_{u} + ϵ_{u}^{ν} < ω_{u} + ϵ_{u}^{ω},  and  ν_{u} = 0 ⇒ ϵ_{u}^{ν} = 0

for u ∈ {x, y, z}. In practice, everything we do is invariant under scaling of V, so we will always assume V^{ϵ} = {ν + ϵ^{ν} | ν ∈ V} consists of integer vectors. Set ν^{ϵ} = ν + ϵ^{ν}. The sole purpose of the ϵ vectors is to break ties one way or the other between equal nonzero coordinates of vectors in V. In this manner, deformations of V are closer to being generic than V is. The verb specialize is used here to indicate that a deformation (generization) is being reversed; thus V is a specialization of V^{ϵ} if the latter is a deformation of the former. One particular deformation will play a key role in the coming sections. To define it, let V(u, a) = {ν ∈ V | ν_{u} = a} for each 0 < a ∈ ℕ and u ∈ {x, y, z}. Up to order-preserving bijection (as in Lemma 2.1), there is a unique deformation ϵ satisfying the following condition as well as its analogues via cyclic permutation of x, y, z:

If the elements of V(z, a) satisfy ν_{x} > ⋯ > ω_{x}, then a = ν_{z}^{ϵ} < ⋯ < ω_{z}^{ϵ}. (12)

Note that ν_{x} > ⋯ > ω_{x} is equivalent to ν_{y} < ⋯ < ω_{y} for elements of V(z, a), by pairwise incomparability. Thus, looking down the x-axis, ϵ raises the vectors in V(z, a) higher as they move to the right.

11 Ideals to graphs: algorithm

Arbitrary monomial ideals in more than three variables need not have minimal cellular free resolutions [RW01], but limiting to three variables forces better behavior.

Theorem 11.1 Any monomial ideal I_{V} ⊂ k[x, y, z] has a cellular minimal free resolution supported on a labeled planar map M.

The proof (at the end of Section 12) will reduce to the artinian case, for which Algorithm 11.2 produces M. The justification of Algorithm 11.2 appears in Section 12. Heuristically, the idea is to apply the deformation ϵ of (12), and show that specializing V^{ϵ} ⇝ V step by step makes the spurious edges in the Scarf triangulation disappear one at a time. More precisely, the algorithm specializes V^{ϵ} back to V by making strict inequalities ν_{u}^{ϵ} < ω_{u}^{ϵ} into equalities ν_{u} = ω_{u}, judiciously and one at a time. Before each specialization step, the (already partially specialized) ideal has a cellular minimal resolution by induction; after each specialization step, the same planar map still supports a cellular free resolution, although it may not be minimal. However, in the nonminimal case, minimality is achieved by removing exactly one edge.

Algorithm 11.2

input an artinian ideal I_{V} ⊂ k[x, y, z] output a planar map M supporting a cellular minimal free resolution of I_{V}

initialize ϵ := the deformation of I_{V} in (12) to a strongly generic ideal I_{V^{ϵ}}

M := Scarf complex of V^{ϵ} while V^{ϵ} ≠ V do

choose ν ∈ V and u ∈ {x, y, z} such that ν_{u}^{ϵ} ≠ ν_{u} and ν_{u}^{ϵ} is minimal; for ease of notation, assume u = x by applying a cyclic permutation of {x, y, z} translating u to x, if necessary

γ_{x} := ν_{x}

γ_{y} := ν_{y}^{ϵ} + |Y_{ν^{ϵ}}|
γ_{z} := min_{ω≠ν}{ω_{z}^{ϵ} | ω_{x}^{ϵ} ≤ ν_{x} and ω_{y}^{ϵ} < γ_{y}}

ρ := the element of {ω^{ϵ} ∈ V^{ϵ} | ω_{y}^{ϵ} = γ_{y} and ω_{z}^{ϵ} < γ_{z}} with

maximal ω_{z}^{ϵ}

redefine ϵ by replacing the x-coordinate ϵ_{x}^{ν} with 0

M by changing the label on ν^{ϵ} accordingly if ρ_{x} = ν_{x}

then redefine M by removing edge labeled γ = (γ_{x}, γ_{y}, γ_{z}) else leave M unchanged

end if-then-else end while-do

output M PSfrag replacements

⇝ ?

(ν_{x}^{ϵ}, ν_{y}^{ϵ}, ν_{z}^{ϵ}) (γ_{x}, γ_{y}, γ_{z})

ρ

y-coordinate γ_{y} z-coordinate γ_{z}

then else

...

⋮

Figure 8: The geometry of Algorithm 11.2

Remark 11.3 Here are some elementary observations to aid in parsing the algorithm. See also Figure 8, which illustrates the geometry.

(i) It may be necessary to scale V in order to choose ϵ^{ν} ∈ ℕ^{3} for all ν, because of the condition a = ν_{u}^{ϵ}.

(ii) Note that γ_{x} = ν_{x}, not ν_{x}^{ϵ}. (iii) The orthogonal ray Y_{ν^{ϵ}} used to define γ_{y} is bounded because ν^{ϵ} ≠ ν, so

that ν cannot be the axial vertex ẏ. (iv) The set used to define γ_{z} is nonempty because the axial vector ż is in the

set; indeed, ν^{ϵ} ≠ ν implies ν ≠ ż.

(v) γ_{z} > ν_{z}^{ϵ} because V^{ϵ} consists of pairwise incomparable vectors. (vi) The set defining ρ is nonempty because ν^{ϵ} + Y_{ν^{ϵ}} = ν^{ϵ}∨ω^{ϵ} for some ω^{ϵ} in

this set. Uniqueness of ρ follows from pairwise incomparability of elements in V^{ϵ}.

(vii) Relabeling M at the redefine step yields a cellular free resolution of the resulting ideal with the new ϵ by [GPW00, Theorem 3.3], though it need not be minimal.

Example 11.4 If I_{V} = ⟨x^{4}, x^{2}y^{2}, x^{2}z^{2}, y^{4}, y^{2}z^{2}, z^{4}⟩ is obtained from Example 7.1 by a scale factor of 2, then the generic deformation I_{V^{ϵ}} = ⟨x^{4}, x^{2}y^{3}, x^{3}z^{2}, y^{4}, y^{2}z^{3}, x^{4}⟩ satisfies the condition of Algorithm 11.2. Furthermore, the Scarf complex of I_{V^{ϵ}} is the triangle with its edge-midpoints connected, as in Example 7.1. If Algorithm 11.2 is run on this I_{V}, then one of the three nonminimal edges is removed on the first iteration of the while loop. Precisely which of the nonminimal edges is removed depends on which u ∈ {x, y, z} is chosen first; any u will work, not just u = x. In the remaining two iterations of the while loop, no further edges are removed. It is instructive to work out this example by hand; see Figure 8 for general pictures. □

12 Ideals to graphs: proof

The gruntwork in proving that the algorithm accomplishes its goal is contained in the following two technical lemmas, whose hypotheses are designed to be satisfied by the deformation taking place in one pass of the while loop (after a cyclic permutation of (x, y, z) and an order-preserving bijection as in Lemma 2.1, perhaps).

Lemma 12.1 Suppose I_{V} ⊂ k[x, y, z] is artinian, and that ν ∈ V has ν_{x} ≠ 0 and satisfies ω_{y} ≥ ν_{y} whenever ω_{x} = ν_{x}. Suppose further that ϵ = {ϵ^{ω}}_{ω∈V} is a deformation of V with ϵ^{ω} = 0 for ω ≠ ν and ϵ^{ν} = (1, 0, 0). Let γ_{y} = ν_{y}^{ϵ} + |Y_{ν^{ϵ}}|. If α ∈ ℕ^{3} then K_{α}(V^{ϵ}) = K_{α}(V) unless

ν_{z} ≤ α_{z} and ν_{y} ≤ α_{y} ≤ γ_{y} and α_{x} ∈ {ν_{x}, 1 + ν_{x}}.  (13)

If α_{y} ≠ γ_{y} and α satisfies (13) with α_{x} = ν_{x}, then K_{α+ϵ^{ν}} (V^{ϵ}) = K_{α}(V) while both K_{α}(V^{ϵ}) and K_{α+ϵ^{ν}} (V) have no reduced homology.

The last sentence takes care of the case where α satisfies (13) and α_{x} = 1 + ν_{x}, because α + ϵ^{ν} has x-coordinate 1 + ν_{x}; the case α_{y} = γ_{y} will be covered in Lemma 12.2. The idea comes from Figure 8, where the grey dots represent elements of V^{ϵ}, the white dots represent maximal points of S_{V^{ϵ}} (= second syzygies of I_{V^{ϵ}} = irreducible components of I_{V^{ϵ}}), and the black dots represent first syzygies of I_{V^{ϵ}}. Looking from far down the x-axis, the vector ν^{ϵ} has a vertical plateau behind it: the big medium-grey wall, parallel to the yz-plane. Pushing ν^{ϵ} back to ν moves that vertical wall back a single unit. The only places where the topology of K_{α}(V) can possibly change are at lattice points α that sit either on the original wall in S_{V^{ϵ}} or its pushed-back image in S_{V}; these are the vectors α described in (13). For vectors α + ϵ^{ν} that sit on the original wall but to the left of its right-hand edge (i.e. those with α_{y} ≠ γ_{y}), the Koszul simplicial complex K_{α+ϵ^{ν}} (V^{ϵ}) gets carried along for the ride to K_{α}(V) as the wall gets pushed back; the empty circles denote where the filled (black and white) dots get moved to. On the other hand, if α sits on the pushed-back image of the wall in S_{V} (as the empty circles strictly to the left of γ_{y} do), then S_{V^{ϵ}} is translation-invariant in the x-direction near α, making K_{α}(V^{ϵ}) a cone; the same goes for K_{α+ϵ^{ν}} (V). Cones have no reduced homology. Having this geometry in mind, here’s the official proof of the lemma.

Proof. First assume α fails to satisfy (13). Use σ to denote an element of {0, 1}^{3}. To start off with, ω ⪯ α − σ if and only if ω^{ϵ} ⪯ α − σ whenever ω ∈ V ∖ ν, so the only possible differences in the simplicial complexes K_{α}(V) and K_{α}(V^{ϵ}) come from the placement of ν and ν^{ϵ} relative to the vectors α − σ. If α_{x} ∉ {ν_{x}, 1 + ν_{x}} then clearly ν ⪯ α − σ if and only if ν^{ϵ} ⪯ α − σ. And if α_{y} < ν_{y} or α_{z} < ν_{z}, then neither ν nor ν^{ϵ} precedes α − σ. The only remaining case of α not satisfying (13) has α_{x} ≥ ν_{x} and α_{y} > γ_{y} and α_{z} ≥ ν_{z}. Suppose ν^{ϵ} + Y_{ν^{ϵ}} = ν^{ϵ}∨ω. Then ν^{ϵ} ⪯ α ⇒ ω ⪯ α, and also ν ⪯ α ⇒ ω ⪯ α, so K_{α}(V) and K_{α}(V^{ϵ}) do not depend on ν or ν^{ϵ}. Now assume α satisfies (13) and α_{y} < γ_{y}. Then ω ⪯ α − σ if and only if ω ⪯ α − (σ ∪ ϵ^{ν}) whenever ω ∈ V ∖ ν by the assumption ‘ω_{y} ≥ ν_{y} whenever ω_{x} = ν_{x}’. If α_{x} = ν_{x} then ν^{ϵ} ⪯̸ α and thus K_{α}(V^{ϵ}) is a cone with vertex ϵ^{ν}. If α_{x} = 1 + ν_{x} then ν ⪯ α − σ if and only if ν ⪯ α − (σ ∪ ϵ^{ν}), so K_{α}(V) is another cone with vertex ϵ^{ν}. Finally, suppose that α_{x} = ν_{x} in addition to (13) and α_{y} < γ_{y}. Then ω ⪯ α + ϵ^{ν} − σ if and only if ω ⪯ α − σ for ω ∈ V ∖ ν by the assumption ‘ω_{y} ≥ ν_{y} whenever ω_{x} = ν_{x}’. And clearly ν^{ϵ} ⪯ α + ϵ^{ν} − σ if and only if ν ⪯ α − σ, since ν^{ϵ} = ν + ϵ^{ν}. Therefore K_{α+ϵ^{ν}} (V^{ϵ}) = K_{α}(V) in this case. □

Lemma 12.2 Assume the hypotheses and notation from Lemma 12.1, let γ_{x} = ν_{x}, and let

γ_{z} = min_{ω≠ν}{ω_{z} | ω_{x} ≤ ν_{x} and ω_{y} < γ_{y}},

which exists because I_{V} is artinian. Denote by F.^{ϵ} a minimal free resolution of I_{V^{ϵ}} and by F. the specialized free resolution of I_{V} via [GPW00, Theorem 3.3]. (This amounts to the redefine step applied to any cellular resolution supported on a complex with vertex set V^{ϵ}.) Then at most two syzygies of F.^{ϵ} become nonminimal in F.: a second syzygy s_{2}^{ϵ} in degree γ + ϵ^{ν} = (1 + γ_{x}, γ_{y}, γ_{z}) and a first syzygy s_{1}^{ϵ} in degree γ. Choose the unique ρ ∈ V with ρ_{y} = γ_{y} such that ρ_{z} < γ_{z} is maximal. Then the specializations (s_{1}, s_{2}) of (s_{1}^{ϵ}, s_{2}^{ϵ}) are nonminimal if and only if ρ_{x} = γ_{x}.

Proof. The only possible nonminimal summands of F. occur in degrees (ν_{x}, γ_{y}, α_{z}) or (ν_{x}^{ϵ}, γ_{y}, α_{z}) for some value of α_{z} ≥ ν_{z}, because the other Betti numbers of I_{V} and I_{V^{ϵ}} are in bijection by Lemma 12.1. Furthermore, nonminimal summands cannot come from zeroth syzygies of I_{V^{ϵ}}, since these are in bijection with those of I_{V} (no elements of V^{ϵ} disappear when the ϵ is removed). Therefore, nonminimal syzygies in F. can only be first or second syzygies. It is a general fact about nonminimal free resolutions that nonminimal summands come in pairs (s_{1}, s_{2}) consisting of a first and second syzygy. In the present case, such pairs arise from minimal first and second syzygies (s_{1}^{ϵ}, s_{2}^{ϵ}) of I_{V^{ϵ}}. Since deg(s_{1}) = deg(s_{2}) but deg(s_{1}^{ϵ}) ≠ deg(s_{2}^{ϵ}), and the only change is occurring in the x-direction, it must be that deg(s_{2}^{ϵ}) = ϵ^{ν} + deg(s_{1}^{ϵ}). Lemma 12.1 therefore implies that any minimal syzygy s_{2}^{ϵ} becoming nonminimal in F. must have deg(s_{2}^{ϵ}) along the vertical ray (ν_{x}^{ϵ}, γ_{y}, α_{z}) for varying α_{z} ≥ ν_{z}. Furthermore, there can be at most one value γ_{z} for α_{z}, since there can be only one second syzygy along any line parallel to an axis. This proves all but the last sentence. The two specialized syzygies are nonminimal if and only if either one of them is. The specialization of s_{2}^{ϵ} is a second syzygy in degree γ that is minimal if and only if K_{γ}(V) is the boundary of a triangle by Proposition 6.1. In any case, γ−(1, 1, 1) ∉ ⟨V⟩ by minimality of γ_{z}. Suppose ρ_{x} ≠ γ_{x}. Then (0, 1, 1) ∈ K_{γ}(V) because γ_{z} > ν_{z} and γ_{y} > ν_{y}. Any vector ω ∈ V whose z-coordinate was used to define γ_{z} has ω_{x} < ν_{x} by the assumption ‘ω_{y} ≥ ν_{y} whenever ω_{x} = ν_{x}’; thus (1, 1, 0) ∈ K_{γ}(V). And (1, 0, 1) ∈ K_{γ}(V) because of ρ. Therefore, K_{γ}(V) is the boundary of the triangle when ρ_{x} ≠ γ_{x} (in this case, there is no first syzygy of I_{V^{ϵ}} in degree γ waiting to cancel s_{2}^{ϵ} as it specializes to s_{2}). Finally, if ρ_{x} = γ_{x}, then (1, 0, 1) ∉ K_{γ}(V), whence K_{γ}(V) cannot be the boundary of a triangle.

□

Example 12.3 Some possible combinatorial types for K_{α}(V), where α = deg(s_{1}) is the degree of the specialized first syzygy of Lemma 12.2, are depicted in Figure 8. The headings ‘else’ and ‘then’ correspond to the cases in Algorithm 11.2. Observe that in the single then case, the white dot s_{2}^{ϵ} at (1 + γ_{x}, γ_{y}, γ_{z}) gets smashed into the vertical plane during specialization and cancels the black dot s_{1}^{ϵ} at (γ_{x}, γ_{y}, γ_{z}). On the other hand, the topology remains constant in the first two else cases. In the final else case, two of the black dots merge to become a “double” black dot, since the resulting Koszul simplicial complex (3 disjoint vertices), has 2-dimensional H̃_{0} after the wall is pushed back. □

Proposition 12.4 At every iteration of the line end while-do in Algorithm 11.2, the labeled map M provides a minimal cellular free resolution of I_{V^{ϵ}}.

Proof. This has two parts, of course: then and else. Both follow from Lemma 12.2, given Remark 11.3(vii). Indeed, removing the unique nonminimal edge automatically destroys the unique nonminimal region by merging it with an adjacent region. This argument implicitly uses Proposition 7.2, which guarantees that the deleted edge equals the entire intersection of the two regions containing it, so that matrices for the ordinary boundary complex of the deletion are obtained from those for M by removing the appropriate rows and columns. It should also be reiterated that we can choose the deformation in Lemma 12.1 to be the one occurring in each pass of the while loop; indeed it is here that the precise condition (12) on the deformation ϵ in Algorithm 11.2 is used in an essential way. □

Proof of Theorem 11.1. It remains only to reduce to the artinian case. Let \overline{V} = V ∪ {u̇ | S_{V} ∩ U = ∅} for sufficiently large |u̇|, as in Lemma 8.2. Given any labeled cell complex \overline{M} supporting a minimal cellular resolution of I\overline{V}, taking the subcomplex M ⊆ \overline{M} whose labels precede the join ∨V\} produces a cell complex supporting a minimal resolution of M. This is the content of [BS98, Corollary 1.3]. □

Part III Planar maps revisited

13 Orthogonal coloring

Let M be a planar map with vertex set V and M_{∞} an extended map. Since M_{∞} is embedded in a surface S homeomorphic to the plane, it makes sense to order the angles at any of its vertices cyclically, and to say that a list of angles at a vertex is consecutive. The same comment applies as well to the angles in any bounded region of M_{∞}, to the four angles having any fixed bounded edge as a leg (two at each vertex), and to the unbounded edges (read as the hands on an analog clock). With these cyclically ordered sets in mind, let A be any finite set of objects arranged cyclically in the surface S. Given three colors x, y, z, the set A is trichromatic if

• there is an element in A colored u, for each u = x, y, z;

• the elements in A colored u are consecutive, for each u = x, y, z; and • the block of elements colored z is immediately counterclockwise from the

block of elements colored y.

Deleting ‘counter’ from the last item defines clockwise trichromatic instead. An orthogonal coloring O of M_{∞} is a labeling of the angles in M_{∞} at every vertex in M by three colors x, y, z such that

(i) all vertices of M are trichromatic in M_{∞}; (ii) all bounded edges of M are clockwise trichromatic in M_{∞}; (iii) all bounded regions of M are trichromatic in M_{∞}; (iv) the two angles adjacent to each unbounded edge have different colors; and (v) attaching to each unbounded edge the color missing from its two angles

makes the set of unbounded edges in M_{∞} trichromatic.

Suppose, in addition, that M has axial vertices ẋ, ẏ, ż, so M_{∞} = M_{∞}(ẋ, ẏ, ż). The angles interior to the three unbounded regions of M_{∞} are called exterior angles of M_{∞}; besides the obvious pair of angles at each of ẋ, ẏ, ż, they include one angle at each nonaxial vertex lying on the exterior cycle. The interior angles at vertices on the exterior cycle are the angles lying inside M—that is, the nonexterior angles. Call an orthogonal coloring of M axial if the following boundary conditions, which imply axioms (iv) and (v), are satisfied for u = x, y, z:

(iv)′ all interior angles at the axial vertex u̇ are colored u; (v)′ all exterior angles of M_{∞} in the unbounded region not touching u̇ are

colored u.

For example, the orthogonal coloring in Figure 1 is axial. Roughly speaking, even axioms (iv)′ and (v)′ say that something is trichromatic: (iv)′ says that the exterior cycle, thought of as a triangle with vertices ẋ, ẏ, ż, is trichromatic; while (v)′ says that the set of exterior angles is trichromatic. This observation makes it particularly easy to remember the axioms defining an orthogonal coloring. Felsner independently defined what he called Schnyder colorings in [Fel01, Section 1]. These are the same thing as axial orthogonal colorings. Felsner also pointed out that axiom (ii) follows from the others [Fel01, Lemma 1]. When the planar map is a triangulation of a simplex with no new vertices on the boundary, axial orthogonal coloring reduces to the angle-coloring of Schnyder [Tro92, Theorem 6.2.1], justifying Felsner’s terminology. The next result and its proof justify the adjective “orthogonal”.

Proposition 13.1 Any (axial) geodesic embedding M ↪ S_{V} induces an (axial) orthogonal coloring of M_{∞} = M ∪ (unbounded orthogonal rays).

Proof. Any angle in a geodesic embedding, whether between bounded or unbounded edges or both, locally lies in a plane u = constant for some u ∈ {x, y, z}. Color such an angle by u. The orthogonality axioms follow readily from the definition of axial geodesic embedding and the region axiom (which holds for nonaxial grid surfaces by Lemma 8.2) in Section 2. □

14 Orthogonal flows

In this section the planar map M has axial vertices ẋ, ẏ, ż, and M_{∞}(ẋ, ẏ, ż) is orthogonally colored. We derive properties of orthogonal flows in grid surfaces (Section 2) from the axioms for axial orthogonal coloring, for comparison with [BT93]. In an earlier version of this paper, the current section was intended to serve as a possible proof method for Conjecture 16.3, below. Felsner in fact carried out this program [Fel02], having independently found the results in this section already [Fel01]. To begin, interpret an orthogonal coloring as a family of three orthogonal vector fields on M_{∞}: for each vertex of M_{∞}, assign precisely three arrows pointing away from it—one of each color—along the edges separating the blocks of differently colored angles. Thus, for example, the z-colored arrows point upward along an edge if and only if the angles around the edge have colors _{y}^{z}|_{x}^{z}, _{y}^{y}|_{x}^{z}, _{y}^{z}|_{x}^{x}, or _{y}|_{x} (the z-axis). The first of these edges has no arrow pointing downward from its top vertex, while the second and third have downward arrows colored x and y, respectively. The u-colored vector fields for u = x, y, z can be “integrated” to get orthogonal flow lines: the u-colored flow line from ν ∈ M is a directed path in M_{∞}, beginning with ν, that is a union of edges underlying u-colored arrows. Thus the next vertex after ν is at the other end of the edge whose u-colored arrow points away from ν. Orthogonal flow lines can only meet in certain orientations. To make a precise statement, let L be a directed path passing through a vertex ν, and K a directed path containing an edge e⃗ pointing toward ν. Then K approaches L from the left at ν if e⃗ is distinct from L’s two arrows at ν, and these three arrows are oriented as in Eq. (14), below (ignoring the labels for the moment). Similarly, given the mirror orientations, K approaches L from the right.

Lemma 14.1 A flow line colored x never approaches a flow line colored z from the left. A flow line colored y never approaches a flow line colored z from the right. These statements remain true for cyclic permutations of x, y, z.

Proof. Suppose e⃗ approaches the z-colored flow line L from the left at ν. The angle coloration around ν looks like the following diagram,

\begin{aligned}& & L \\ y & ↑ & x \\ \frac{c e⃗}{b} → & & ν \\ {a \atop y} & ↑ & x \end{aligned}  (14)

in which a ≠ x by edge trichromatics. (There may be other edges containing ν but not shown.) Since none of the angles going clockwise between a and y at ν can be x-colored (by vertex trichromatics), it is impossible to have {b, c} ⊆ {y, z}, by edge trichromatics. The other case is similar, and the symmetry is obvious. □

The observation in Lemma 14.1 imposes useful conditions on flow lines. The next proposition says that orthogonal flow lines satisfy conditions slightly stronger than the five “path properties” defining a normal family of paths, as introduced by Brightwell and Trotter [BT93] (see [Tro92, Chapter 6] for an exposition). A set of paths whose pairwise intersections consist of a single vertex is called independent.

Proposition 14.2 (Path Properties) Endow M_{∞}(ẋ, ẏ, ż) with an axial orthogonal coloring. Suppose ν ∈ M is a vertex and u ∈ {x, y, z} is a color.

1. There is a unique u-colored flow line beginning at ν; it connects ν to ∞ via u̇.

2. If [ν, u̇] denotes the part of the u-colored flow line starting with ν and ending with u̇, then [ν, ẋ], [ν, ẏ], and [ν, ż] are independent paths from ν.

3. The six paths [ẋ, ẏ], [ẏ, ẋ], [ẏ, ż], [ż, ẏ], [ẋ, ż], [ż, ẋ] are on the exterior cycle of M.

4. If ω ∈ M is a vertex such that ω ∈ [ν, u̇], then [ω, u̇] ⊆ [ν, u̇].

5. If ω is in the union [ẋ, ν, ẏ] of [ν, ẋ], [ν, ẏ], [ẋ, ẏ], and any regions they enclose, then [ẋ, ω, ẏ] ⊆ [ẋ, ν, ẏ]; the same holds with ż in place of ẋ or ẏ.

Proof. Existence and uniqueness in part 1 are obvious. Since the only arrows in M_{∞} pointing out of M are on the axes by orthogonality axioms (iv)′ and (v)′, part 1 is equivalent to statement that flow lines contain no cycles. Any flow cycle C containing a vertex in the interior of the region it bounds contains an entire flow cycle of some other color in its interior: one of the other colors cannot escape by Lemma 14.1. Thus we may assume C has no vertices interior to it. But then the argument in the proof of Lemma 14.1 forces the coloration of the angles in the interior of C to omit one color entirely, violating region trichromatics. Now suppose two flow lines from ν—colored x and y, say—intersect, and consider the cycle C formed by their arcs connecting ν to their first intersection point. Assume for the moment that ω lies interior to C. Depending on the orientations of the two flow lines around C, either z-flow lines cannot escape C, or the u-flow line from ω exits through the u-colored arc of C, for u = x, y. The first case contradicts acyclicity, while the second case produces a smaller cycle C. Again, we may therefore assume C contains no vertices interior to it. In the first orientation, no interior angle of C is colored z, while in the second orientation, all interior angles of C are colored z. Part 3 follows easily by applying orthogonality axiom (ii) to the edges on the exterior cycle of M, each of which has two of its four colors specified by (v)′. Part 4 is obvious from the definition of flow line. To prove part 5, first observe that a flow line colored x or y cannot escape [ẋ, ν, ẏ] if it originates at a vertex ω ∈ [ẋ, ν, ẏ] that is on neither [ν, ẋ] nor [ν, ẏ]. Indeed, if [ω, ẋ] intersects [ν, ẋ], then these two flow lines agree thereafter; and [ω, ẋ] cannot even approach [ν, ẏ], thanks to Lemma 14.1. On the other hand, if ν ≠ ω ∈ [ν, ẏ], say, then [ω, ẏ] ⊂ [ν, ẏ] by part 4. Moreover, vertex trichromatics force the first edge of [ω, ẋ] to exit ω clockwise from the y-colored arrow pointing away ω, but counterclockwise from the other edge leaving ω and in [ν, ẏ]. Therefore, [ω, ẋ] remains inside [ẋ, ν, ẏ] either by part 4 or the first sentence of this paragraph. □

Example 14.3 Orthogonal flow lines are better behaved than arbitrary normal families of paths, since their strong local properties imply Path Property 2, and especially the crucial Path Property 5, which are global. Figure 9 depicts two triples of vector fields determined by trichromatic angle colorings whose corresponding flow lines satisfy the conclusion of Proposition 14.2, and therefore constitute normal families of paths. The vector fields in the left diagram are not orthogonal because of the edge connecting the rightmost interior vertices, the edge connecting the remaining interior vertex to ẋ, the interior region, and the bottom region bordering [ẋ, ż]. Recoloring the angles at the leftmost interior vertices yields the orthogonal vector fields at right. □ normal family of paths orthogonal vector fields

Figure 9: Nonorthogonal and orthogonal vector fields

Corollary 14.4 Let M be a planar with axial vertices ẋ, ẏ, ż. The extended map M_{∞}(ẋ, ẏ, ż) can be orthogonally colored if and only if it is triconnected.

Proof. Proposition 14.2.2 proves the ‘only if’ direction, while Theorem 5.1 and Proposition 13.1 prove the ‘if’ direction. □

Remark 14.5 The results of this section can be massaged to work for nonaxial orthogonally colored extended maps M_{∞}, as well. In fact, everything reduces to the axial case: draw a large triangle containing all of M—not M_{∞}—in its interior, and call its three vertices ẋ, ẏ, ż, in counterclockwise order. Then connect each u-colored unbounded edge to u̇. It is straightforward to verify the axioms for axial orthogonal colorings, given the ordinary axioms for M_{∞}. Observe the analogy with Lemma 8.2.

15 Duality for geodesic embeddings

Let G be a graph embedded in the sphere S ∪ {∞}, where S ≅ ℝ^{2}, and assume that G∩S is a planar map or extended map. For this paragraph only, we allow graphs and planar maps to have multiple edges, although we assume G has no loops, and that the edges of G in each one of its regions form a simple cycle. Define the spherical dual Ĝ of G as usual: place a vertex Â in each region A of G, and draw an edge connecting Â to B̂ through each edge contained in A∩B. Then Ĝ also satisfies the no-loop and simple-cycle conditions, which are dual to each other. Assume that ∞ is a vertex of either G or Ĝ. When ∞ ∉ G, so G is a planar map M ⊂ S, then Ĝ is an extended map that we denote by M̂_{∞} (with associated planar map del(Ĝ; ∞) = M̂) and call the planar dual of M. When ∞ ∈ G, so G ∩ S = N_{∞} is an extended map satisfying N = del(G; ∞), then Ĝ is a planar map that we denote by N̂ and call the planar dual of N_{∞}. For an arbitrary grid surface S_{V}, let α̂ be any vector preceded by 1 + the join of the vectors in V, where 1 = (1, 1, 1). Define \overline{V} by throwing in axial vertices missing from V:

\overline{V} = V ∪ \{u̇ | S_{V} ∩ U = ∅\}, where u̇ ∈ U has length |u̇| = α̂_{u}.

This notation agrees with that in Lemma 8.2, but specifies the length of u̇. Define the Alexander dual grid surface SV̂ by

V̂ = \{α̂ − ρ | ρ ∈ Smax ; \overline{V}\},

where the notation comes from Lemma 8.3. Neither SV̂ nor S\overline{V̂} depends combinatorially on α̂, in the sense of Lemma 2.1. By definition, \overline{V} = V and α̂ ⪰ ẋ + ẏ + ż + 1 when S_{V} is axial. Define S_{V} to be radial if ν_{u} ≠ 0 for all ν ∈ V and u ∈ \{x, y, z\}. In particular, \overline{V} = V ∪ \{ẋ, ẏ, ż\} is a disjoint union when S_{V} is radial. Although the following duality theorem is stated only for axial and radial grid surfaces, similar (but slightly harder to state) considerations apply to arbitrary geodesic and rigid embeddings; the definition of Alexander dual grid surface extends verbatim. Recall that M_{∞} = M ∪ (unbounded orthogonal rays in S_{V}) for geodesic embeddings M ↪ S_{V}.

Theorem 15.1 Let M ↪ S_{V} be an axial geodesic embedding, and N ↪ S_{W} a radial geodesic embedding.

1. M ≅ N̂ if and only if M̂ ≅ N.

2. There is a natural radial geodesic embedding M̂ ↪ SV̂ that is rigid if and only if M ↪ S_{V} is rigid.

3. There is a natural axial geodesic embedding N̂ ↪ SŴ that is rigid if and only if N ↪ S_{W} is rigid.

Proof. Part 1 is simply duality for spherical maps, as in the first paragraph of this section. We prove part 2, since part 3 is similar and can even be simplified by using parts 1 and 2. The vertex axiom for SV̂ follows immediately from Lemma 8.3. The main point for the rest of the proof is that

{σ ∈ SV̂ | σ ⪯ α̂} = {α̂ − σ | σ ∈ S_{V} and σ ⪯ α̂}.

In other words, {σ ∈ S_{V} | σ ⪯ α̂} lies in the topological boundary of ℝ^{3} ∖ ⟨V⟩. Every elbow geodesic [ν, ω] in M borders precisely two regions of M_{∞} because M_{∞} is triconnected (apply Proposition 7.2 along with Theorem 8.4, or Proposition 13.1 along with Corollary 14.4). If these two regions A and B are bounded, then the maximal points Â and B̂ in them (Lemma 8.3) connect via straight line segments in S_{V} to ν∨ω by the region axiom (see the proof of Lemma 8.3). Furthermore, one of these segments must transform into an orthogonal ray in SV̂ via σ ↦ α̂ − σ, because ν∨ω = Â∧B̂ (by the region axiom: for each u ∈ {x, y, z} one of the two vectors ν and ω shares its u-coordinate with one of the vectors Â and B̂). Thus every bounded edge of M̂_{∞} is an elbow geodesic in SV̂. If [ν, ω] borders a bounded region A and an unbounded region, then ν_{u} = ω_{u} = 0 for some u ∈ {x, y, z}. The vector ν∨ω shares both of its nonzero coordinates with Â in this case, so Â is the unique maximal point of S_{V} preceded by ν∨ω. This forces the negative ray Â − U passing through Â and ν∨ω to transform axial radial

Figure 10: Duality for geodesic embeddings

into an unbounded orthogonal ray α̂ − (Â − U) = (α̂ − Â) + U in SV̂. Thus the unbounded edges of M̂_{∞} are unbounded orthogonal rays in SV̂. Now we show that every orthogonal ray in SV̂ is contained in an edge of M̂. Equivalently, for each maximal point Â ∈ S_{V} and U ∈ {X, Y, Z}, there is an elbow geodesic [ν, ω] ∈ M such that Â − ν∨ω ∈ U. By symmetry, set U = Z. Choose the edge [ν, ω] ⊂ A so that ν_{x} = Â_{x} and ω_{y} = Â_{y}; such an edge exists by orthogonality property (iii) and Proposition 13.1. For the statement about rigidity, use the rigid region axiom: ν∨ω ⪯ Â ⇔ ν ⪯ Â and ω ⪯ Â, and this occurs precisely when ν ∈ A and ω ∈ A. Thus, when [ν, ω] ⊂ S_{V} is a rigid geodesic, ν∨ω precedes the maximal points in exactly two regions of M: the regions A and B containing both ν and ω. That ν∨ω = Â∧B̂ was shown above. □

Example 15.2 Figure 10 illustrates Theorem 15.1 for a particular (nonrigid) geodesic embedding. Turning the picture upside-down yields two pictures of the Alexander dual grid surface, with the radial embedding appearing the right way out and the axial embedding backwards. □

Considering the Theorem 8.4, the duality result here essentially falls under the umbrella of duality for resolutions of monomial ideals [Mil00a, Section 4.2]. Although the above proof can be simplified greatly by applying duality for resolutions, particularly in concert with [Mil00a, Proposition 3.20], it seemed appropriate to keep Theorem 15.1 as self-contained as possible.

16 Open problems

16.1 Planar maps supporting resolutions of nonartinian ideals

Problem 16.1 Characterize those planar maps that support minimal resolutions of trivariate monomial ideals.

It would be nice to clean up the statement of Theorem B by proving 3 ⇒ 2. Unfortunately, the most direct proof attempt fails. To be precise, suppose the planar map N supports a minimal cellular free resolution of some ideal I_{V}. Following the procedure in the proof of Proposition 7.2, the underlying graph H of N has paths analogous to orthogonal flows. However, since V may not be axial, these flows do not reach axial vertices, but instead reach unbounded orthogonal rays. As an abstract graph, we can define \overline{H} by adding three new vertices ẋ, ẏ, ż to H, and then connecting each vertex ν ∈ N to u̇ if the orthogonal ray U_{ν} is unbounded. Judging from Theorems A and B, one might expect that \overline{H} is planar and triconnected, supporting a minimal free resolution of some artinian approximation to I_{V}. But although \overline{H} is obviously triconnected, it need not be planar! Take, for instance, the set V from Example 9.2, without the axial vectors. Deleting ẋ, ẏ, ż from the nonplanar map M there yields a planar map N supporting a minimal free resolution of I_{V}, but reconnecting to ẋ, ẏ, ż as above returns M again.

16.2 Nonrigid geodesic embeddings

Conjecture 16.2 Let the axial grid surface S_{V} have vertices ν_{1}, ν_{2}, ν_{3}, ν_{4} ∈ V, each with no coordinate zero, such that [ν_{i}, ν_{j}] is an elbow geodesic whenever i ≠ j. Then the ideal I_{V} possesses a nonplanar cellular minimal free resolution.

Thus relatively minor violation of rigidity for S_{V} not only implies nonuniqueness of minimal cellular resolutions (cf. Corollary 9.1), but should even imply nonplanarity. Intuitively, it should be possible to construct K_{5} out of elbow geodesics (two of which cross) using two of the ν_{i} and ẋ, ẏ, ż, as in Example 9.2. Given such a configuration, one is tempted to “fill in” the resulting 1-skeleton to form a cell complex minimally resolving I_{V}. This is, in fact, how Example 9.2 was constructed.

16.3 Orthogonal coloring to rigid embedding

Conjecture 16.3 (Felsner’s Theorem [Fel02]) Every orthogonal coloring on a planar map is induced by a rigid embedding, as in Proposition 13.1.

This converse to Proposition 13.1 reduces easily to the axial case, via Lemma 8.2 and Remark 14.5. Since the axial case was proved by Felsner [Fel02] in response to seeing the conjecture here, this is in fact no longer an open problem. But see [Fel02] for Felsner’s open questions regarding the set of orthogonal colorings. Besides its applications to the questions discussed in the next subsection, the motivation behind formulating the above statement was that it reduces Theorem 5.1 to verifying that every planar map there has an orthogonal coloring. This actually follows by the same induction used for rigid embeddings, but the details become much simpler; moreover, Felsner already proved existence of orthogonal colorings in [Fel01]. Thus we get a substantially more palatable proof of Theorem 5.1 via [Fel01, Fel02].

16.4 The Scarf stratification

Part of the motivation for the results presented here stems from the desire to understand not just how to assign a minimal free resolution to any particular monomial ideal, but to understand the collection of all minimal free or injective resolutions of monomial ideals. Some recent results, notably those in [GPW00], aim to classify monomial ideals according to whether their minimal resolutions are in some sense isomorphic, by ascertaining what data determines the minimal resolutions. Other results, such as those in [MSY00], raise the question of which deformations (as in Section 10) preserve minimal resolutions. This latter idea originated from [BPS98, PS98], which was in turn based upon work of H. Scarf on related classifications for integer programs. It seems that the most universal approach for minimal resolutions of monomial ideals should combine the two types of classification above. Heuristically, the question becomes, ‘What are all possible ways of deforming continuously between monomial ideals having “nearby” isomorphism classes of resolutions?’ Ideally one would like a ‘fine moduli space’ for minimal resolutions, in the sense that arcs in that space correspond to families of monomial ideals whose minimal resolutions deform continuously. Of course, there are only finitely many deformation classes of minimal resolutions, so the space should interact well with the poset of monomial ideals under deformation. One tempting candidate for ‘fine moduli space’ can be defined as follows. Giving r monomials in n variables is the same as giving an r×n matrix of exponents. The generic monomial ideals partition an open dense subset of the nonnegative orthant in this matrix space, by [BPS98, MSY00]. Taking the cells formed by intersections of the closures of the generic loci yields a decomposition that we propose to call the Scarf stratification. It should be a rational polyhedral fan, if life is fair; but at least there should be a subdividing fan with finitely many maximal cones such that the maximal Scarf cells are unions of maximal cones. Any classifying space such as the Scarf stratification will feel rather more like an algebraic stack than a fine moduli space, because even if it classifies deformations of minimal resolutions, the actual set of isomorphism classes of minimal resolutions would be a quotient by some finite group (containing the symmetric group on the variables, at least) of the set of strata: two monomial ideals differing by a permutation of the variables might be far from each other in the stratification. Whatever the correct space of minimal resolutions ends up being, the methods introduced here can be applied to elucidate its combinatorial structure, for n = 3. Note that Felsner’s theorem (Conjecture 16.3) classifies the maximal strata for the case of three variables—that is, the generic trivariate monomial ideals—by [MSY00]:

Corollary 16.4 Deformation classes of generic artinian trivariate monomial ideals correspond bijectively to orthogonally colored axial planar triangulations.

The triangulations referred to here are orthogonally colored triangulations of the simplex with new vertices on the boundary, so they are not Schnyder normal colorings. Corollary 16.4 and Corollary 9.1 prompt the following:

Question 16.5 In terms of monomial ideals, what do deformation classes of axial rigid embeddings correspond to in general, for non-triangulations?

For instance, do they correspond to certain Scarf strata? If the Scarf stratification is a rational polyhedral fan, what linear equations define these cones? We note that arbitrary geodesic embeddings have considerably more freedom than do rigid embeddings, from the point of view of deformations (hence the adjective ‘rigid’). The possible application of the material in this paper to the classification of deformations of minimal resolutions was one of the motivations for stating as many results as possible in the context of arbitrary geodesic embeddings. Our final remark concerns the bias in this paper toward artinian monomial ideals. Combinatorial considerations such as triconnectivity notwithstanding, the bias also makes sense algebraically. Briefly, the homological characterization of genericity for arbitrary monomial ideals [MSY00, Theorem 1.5 and Remark 1.7] is a statement about graded injective resolutions under deformation; and any result concerning ℤ^{3}-graded injective resolutions of arbitrary monomial ideals has an equivalent statement in terms of ℤ^{3}-graded free resolutions of artinian monomial ideals, by the duality results in [Mil00a]. We emphasize that the theory surrounding injective resolutions played a crucial role in properly formulating the graph-theoretic results in Part I, as well as the algebraic results in Part II (the exposition in Sections 10–12 is based on [Mil00b, Theorem 5.60]). Moreover, concentrating on injective resolutions (equivalently, artinian monomial ideals) should ease the nonplanarity difficulties raised in Section 16.1, by applying [Mil00a, Theorem 4.5.5 and Example 4.8.5], which says how to recover free resolutions from injective resolutions.

References

[BPS98] Dave Bayer, Irena Peeva, and Bernd Sturmfels, Monomial resolutions, Math. Res. Lett. 5 (1998), no. 1-2, 31–46.

[BS98] Dave Bayer and Bernd Sturmfels, Cellular resolutions of monomial modules, J. Reine Angew. Math. 502 (1998), 123–140.

[BT93] Graham Brightwell and William T. Trotter, The order dimension of convex polytopes, SIAM J. Discrete Math. 6 (1993), no. 2, 230–245.

[Fel01] Stefan Felsner, Convex drawings of planar graphs and the order dimension of 3-polytopes, Order 18 (2001), no. 1, 19–37.

[Fel02] Stefan Felsner, Geodesic embeddings and planar graphs, Preprint, 2002.

[GPW00] Vesselin Gasharov, Irena Peeva, and Volkmar Welker, The LCMlattice in monomial resolutions, Math. Res. Lett. 6 (1999), no. 5–6, 521–532.

[Hoc77] Melvin Hochster, Cohen-Macaulay rings, combinatorics, and simplicial complexes, Ring theory, II (Proc. Second Conf., Univ. Oklahoma, Norman, Okla., 1975) (B. R. McDonald and R. Morris, eds.), Lect. Notes in Pure and Appl. Math., no. 26, Dekker, New York, 1977, pp. 171–223. Lecture Notes in Pure and Appl. Math., Vol. 26.

[Mil00a] Ezra Miller, The Alexander duality functors and local duality with monomial support, J. Algebra 231 (2000), 180–234.

[Mil00b] Ezra Miller, Resolutions and duality for monomial ideals, Ph.D. thesis, University of California at Berkeley, 2000.

[MS99] Ezra Miller and Bernd Sturmfels, Monomial ideals and planar graphs, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (M. Fossorier, H. Imai, S. Lin, and A. Poli, eds.), Springer Lecture Notes in Computer Science, no. 1719, Springer Verlag, 1999, Proceedings of AAECC-13 (Honolulu, Nov. 1999), pp. 19–28.

[MSY00] Ezra Miller, Bernd Sturmfels, and Kohji Yanagawa, Generic and cogeneric monomial ideals, J. Symbolic Comp. 29 (2000), 691–708.

[PS98] Irena Peeva and Bernd Sturmfels, Generic lattice ideals, J. Amer. Math. Soc. 11 (1998), no. 2, 363–373.

[Roz70] I. Z. Rozenknop, Polynomial ideals that are generated by monomials, Moskov. Oblast. Ped. Inst. Učen. Zap. 282 (1970), 151–159, (in Russian).

[RW01] Victor Reiner and Volkmar Welker, On the linear syzygies of a Stanley–Reisner ideal, Math. Scand. 89 (2001), no. 1, 117–132.

[Tro92] William T. Trotter, Combinatorics and partially prdered sets: Dimension theory, Johns Hopkins University Press, Baltimore, MD, 1992.

[Zie95] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995.

Ezra Miller

Department of Mathematics M.I.T. Cambridge, Massachusetts ezra@math.mit.edu