Printer Friendly

Divisors on graphs, connected flags, and syzygies.

1 Introduction

The theory of divisors on finite graphs can be viewed as a discrete version of the analogous theory on Riemann surfaces. This notion arises in different fields of research including the study of "abelian sandpiles" ([Dha90, Gab93]), the study of component groups of Nron models of Jacobians of algebraic curves ([Ray70, Lor89]), and the theory of chip-firing games on graphs ([Big97]). Riemann-Roch theory for finite graphs (and generalizations to tropical curves) is developed in this setting ([BN07, GK08, MZ08]).

We are interested in the linear equivalence of divisors on graphs from the point of view of commutative algebra. Associated to every graph G there is a canonical binomial ideal [I.sub.G] which encodes the linear equivalences of divisors on G. Let R denote the polynomial ring with one variable associated to each vertex. For any two effective divisors [D.sub.1] ~ [D.sub.2] there is a binomial [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The ideal [I.sub.G] [subset or equal to] R is generated by all such binomials. Two effective divisors are linearly equivalent if and only if their associated monomials are equal in R/[I.sub.G]. This ideal is already implicitly defined in Dhar's seminal statistical physics paper [Dha90]; R/[I.sub.G] is the "operator algebra" defined there. To our knowledge, this ideal (more precisely, an affine piece of it) was first introduced in [CRS02] to address computational questions in chip-firing dynamics using Grobner basis. From a purely computational point of view there are now much more efficient methods available (see, e.g., [BS13] and references therein). However this ideal seems to encode a lot of interesting information about G and its linear systems. Some of the algebraic properties of [I.sub.G] (and its generalization for directed graphs) are studied in [PPW11]. In [MS13a], Manjunath and Sturmfels relate Riemann-Roch theory for finite graphs to Alexander duality in commutative algebra using this ideal.

In this paper we study the syzygies and free resolutions of the ideals [I.sub.G] and in([I.sub.G]) from the point of view of Grobner theory. Here in([I.sub.G]) denotes the initial ideal with respect to a natural term order which is defined after distinguishing a vertex q (see Definition 2.1). When G is a complete graph, the syzygies and Betti numbers of the ideal in([I.sub.G]) are studied by Postnikov and Shapiro in [PS04]. Again for complete graphs, Manjunath and Sturmfels in [MS13a] study the ideal [I.sub.G] and show that the Betti numbers coincide with the Betti numbers of in([I.sub.G]). Finding minimal free resolutions for a general graph G was stated as an open problem in both [PS04] and [MS13a] (also in [PPW11], where a conjecture is formulated). It was not even known whether the Betti numbers for a general graph depend on the characteristic of the base field or not.

We construct free resolutions for both in([I.sub.G)] and [I.sub.G] for a general graph G. Indeed we describe, combinatorially, the minimal Grobner bases for all higher syzygy modules of [I.sub.G] and in([I.sub.G)]. In each case the minimal Grobner basis is also a minimal generating set and the given resolution is minimal. In particular the Betti numbers of in([I.sub.G)] and [I.sub.G] coincide. This gives a positive answer to [CHT06, Question 1.1] for ideal IG. For a complete graph the minimal free resolution for in([I.sub.G)] is nicely structured by a Scarf complex. The resolution for [I.sub.G] when G a tree is given by a Koszul complex since [I.sub.G] is a complete intersection. A more conceptual and geometric proof for a general graph G will be given in [MS13b].

The description of the generating sets and the Betti numbers is in terms of the "connected flags" of G. Fix a vertex q [member of] V(G) and an integer k. A connected k-flag of G (based at q) is a strictly increasing sequence [U.sub.1] [subset or not equal to] [U.sub.2] [subset or not equal to] ... [subset or not equal to] [U.sub.k] = V (G) such that q [member of] [U.sub.1] and all induced subgraphs on vertex sets [U.sub.i] and [U.sub.i+1]\[U.sub.i] are connected. Associated to any connected k-flag one can assign a "partial orientation" on G (Definition 3.3). Two connected k-flags are considered equivalent if the associated partially oriented graphs coincide. The Betti numbers correspond to the numbers of the connected flags up to this equivalence. We give a bijective map between the connected flags of G and the minimal Grobner bases for higher syzygy modules of [I.sub.G] and in([I.sub.G)]. For a complete graph all flags are connected and all distinct flags are inequivalent. So in this case the Betti numbers are simply the face numbers of the order complex of the poset of those subsets of V(G) that contain q (ordered by inclusion). These numbers can be described using classical Stirling numbers (see Example 4.6). Hence our results directly generalize the analogous results in [PS04] and [MS13a]. Analogous results with different methods were obtained independently in [MSW12] and in [DS12].

The paper is structured as follows. In [section] 2 we fix our notation and provide the necessary background from the theory of divisors on graphs. We also define the ideal [I.sub.G] and the natural Pic(G)-grading and a term order < on the polynomial ring relevant to our setting. In [section] 2.2 we quickly recall some basic notions from commutative algebra. Our main goal is to fix our notation for Schreyer's algorithm for computing higher syzygies, which is slightly different from what appears in the existing literature but is more convenient for our application. In [section] 3 we define connected flags and their equivalence relation. In [section] 4 we study the free resolution and higher syzygies of our ideals from the point of view of Grobner theory, and as a corollary we give our description of the graded Betti numbers. In [section] 5 we describe some connections with the theory of reduced divisors. We refer to [MS12] for proofs and more details.

2 Definitions and background

2.1 Graphs and divisors

Throughout this paper, a graph means a finite, connected, unweighted multigraph with no loops. As usual, the set of vertices and edges of a graph G are denoted by V(G) and E(G). We set n = [absolute value of V (G)]. A pointed graph (G, q) is a graph together with a choice of a distinguished vertex q [member of] V(G).

Let Div(G) be the free abelian group generated by V(G). An element of Div(G) is written as [[summatio].sub.[upsilon] [member of] V(G)] [a.sub.[upsilon]]([upsilon]) and is called a divisor on G. The coefficient [a.sub.[upsilon]] in D is also denoted by D(v). A divisor D is called effective if D(v) [greater than or equal to] 0 for all [upsilon] [member of] V(G). The set of effective divisors is denoted by [Div.sub.+](G). We write D [less than or equal to] E if E - D [member of] [Div.sub.+](G). For D [member of] Div(G), let deg(D) = [[summation].sub.[upsilon] [member of] V](G) D(v). For [D.sub.1], [D.sub.2] [member of] Div(G), the divisor E = max([D.sub.1], [D.sub.2]) is defined by E(v) = max([D.sub.1]([upsilon]), [D.sub.2]([upsilon])) for [upsilon] [member of] V(G).

We denote by M(G) the group of integer-valued functions on the vertices. For A [subset or equal to] V(G), [[chi].sub.A] [member of] M(G) denotes the {0,1}-valued characteristic function of A. The Laplacian operator [DELTA]: M(G) [right arrow] Div(G) is defined by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The group of principal divisors is defined as the image of the Laplacian operator and is denoted by Prin(G). It is easy to check that Prin(G) [subset or equal to] [Div.sup.0] (G) where [Div.sup.0](G) denotes the set consisting of divisors of degree zero. The quotient [Pic.sup.0](G) = [Div.sup.0](G)/Prin(G) is a finite group whose cardinality is the number of spanning trees of G (see, e.g., [BS13] and references therein). The full Picard group of G is defined as

Pic(G) = Div(G)/Prin(G)

which is isomorphic to Z [direct sum] [Pic.sup.0](G). Since principal divisors have degree zero, the map deg: Div(G) [right arrow] Z descends to a well-defined map deg: Pic(G) [right arrow] Z. Two divisors [D.sub.1] and [D.sub.2] are called linearly equivalent if they become equal in Pic(G). In this case we write [D.sub.1] ~ [D.sub.2]. The linear system [absolute value of D] of D is defined as the set of effective divisors that are linearly equivalent to D.

To an ordered pair of disjoint subsets A, B [subset or not equal to] V(G) we assign an effective divisor

D(A,B) = [summation over ([upsilon] [member of] A)] [absolute value of {w [member of] B : {[upsilon], w} [member of] E(G)}]([upsilon]).

In other words, the support of D(A, B) is a subset of A and for [upsilon] [member of] A the coefficient of ([upsilon]) in D(A, B) is the number of edges between [upsilon] and B.

Let K be a field and let R = K[x] be the polynomial ring in the n variables {[x.sub.[upsilon]]: [upsilon] [member of] V(G)}. Any effective divisor D gives rise to a monomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Associated to every graph G there is a canonical ideal which encodes the linear equivalences of divisors on G. Our main object study is the ideal

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

which was introduced in [CRS02].

Once we fix a vertex q, there is a natural monomial order that gives rise to a particularly nice Grobner basis for [I.sub.G]. This term order was first introduced in [CRS02]. Fix a pointed graph (G, q). Consider a total ordering of the set of variables {[x.sub.[upsilon]]: [upsilon] [member of] V(G)} compatible with the distances of vertices from q in G:

dist(w, q) < dist([upsilon], q) [??] [x.sub.w] < [x.sub.v]. (1)

Here, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. The above ordering can be thought of an ordering on vertices induced by running the breadth-first Fsearch algorithm starting at the root vertex q.

Definition 2.1 We denote by < the degree reverse lexicographic ordering on R = [K.sub.[x]] induced by the total ordering on the variables given in (1).

Throughout this paper in([I.sub.G)] denotes the initial ideal of [I.sub.G] with respect to this term order. Note that in([I.sub.G)] is denoted by Mg in [PS04].

2.2 Syzygies and Betti numbers

In this subsection we quickly recall some basic notions from commutative algebra in order to fix our notation. We refer to standard books (e.g. [Eis95, GP08]) for more details.

Let K be any field and let R = K[x] be the polynomial ring in n variables graded by an abelian group A. The degree map will be denoted by deg. Let M be a graded submodule of a free module and fix a module ordering [<.sub.0] extending the monomial ordering < on R. Assume that the finite totally ordered set (G, [??]) forms a Grobner basis for (M, [<.sub.0]) consisting of homogeneous elements. Let [F.sub.0] be the free module generated by G. For g [member of] G we let the formal symbol [g] denote the corresponding generator for [F.sub.0]; each element of [F.sub.0] can be written as a sum of these formal symbols with coefficients in R. There is a natural surjective homomorphism

[[phi].sub.0]: [F.sub.0] [right arrow] M

sending [g] to g for each g [member of] G. Moreover, we enforce this homomorphism to be graded (or homogeneous of degree 0) by defining deg([g]): = deg(g) for all g [member of] G.

By definition the syzygy module of M with respect to G, denoted by syz(G), is the kernel of this map. Let [syz.sub.0](G): = M and [syz.sub.1](G): = syz(G). For i > 1 the higher syzygy modules are defined as [syz.sub.i](G): = syz([syz.sub.i-1](G)).

We now discuss a method to compute a Grobner basis for syz(G). One can "pull back" the module ordering [<.sub.0] along [[phi].sub.0] to get a compatible module ordering [<.sub.1] on [F.sub.0]; for f, h [member of] G define

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

To simplify the notation we assume the leading coefficients of all elements of G are 1. For a pair of elements f [??] h of G assume

LM(f) = [x.sup.[alpha](f)][e] and LM(h) = [x.sup.[alpha](h)][e]

for some e [member of] E. Since G is a Grobner basis, setting [gamma](f, h): = max([alpha](f), [alpha](h)), we have the "standard representation":

spoly(f, h) = [x.sup.[gamma](f,h)-[alpha](f)] f - [x.sup.[gamma](f,h)- [alpha](h)] h = [summation over (g [member of] G) [a.sup.(f,h).sub.g]g (3)

for some polynomials [a.sup.(f,h).sub.g] [member of] R. We set

s(f, h) = [x.sup.[gamma](f,h)-[alpha](f)] [f] - [x.sup.[gamma](f,h)-[alpha](h)] [h] - [summation over (g [member of] G) [a.sup.(f,h).sub.g] [g] [member of] [F.sub.0]. (4)

Theorem 2.2 (Schreyer [Sch80], [Eis95]) The set

S(G) = {s(f, h): f, h [member of] G, f [?/] h, LM(f) = [x.sup.[alpha]](f)[e], LM(h) = [x.sup.[alpha](h)] [e] for some e [member of] E}

forms a homogeneous Grobner basis for (syz(G), <1).

To read the Betti numbers for M one needs to find a minimal generating set for the syzygy modules. In general the set S(G) is far from being even a minimal Grobner basis. However there exist some criterions to find a subset [S.sub.min](G) of S(G) which forms a minimal Grobner basis for (syz(G), [<.sub.1]); see, e.g., [MS12, Lemma 3.4]. Moreover, Theorem 2.2 gives rise to Algorithm 1 for computing free resolutions. The following result gives a general sufficient criterion for an ideal to have the same Betti numbers as its initial ideal.

Theorem 2.3 If the constructed resolution by Schreyer's algorithm is a minimal graded free resolution then [[beta].sub.i,j](M) = [[beta].sub.i,j](in(M)) for all i [greater than or equal to] 0 and j [member of] A.

3 Connected flags on graphs

3.1 Connected fags, partial orientations, and divisors

From now on we fix a pointed graph (G, q) and we let n = [absolute value of V(G)]. Consider the poset

C(G, q) := {U [subset or equal to] V(G): q [member of][member of] U}

ordered by inclusion. The following special chains of this poset arise naturally in our setting.

Definition 3.1 Fix an integer 1 [less than or equal to] k [less than or equal to] n. A connected k-flag of (G, q) is a (strictly increasing) sequence U of subsets of V (G)

[U.sub.1] [subset or equal to] [U.sub.2] [subset or equal to] ... [subset or equal to] [U.sub.k] = V(G)

such that q [member of] [U.sub.1] and, for all 1 [less than or equal to] i [less than or equal to] k - 1, both G[[U.sub.i]] and G[[U.sub.i+1]\[U.sub.i]] are connected.

The set of all connected k-flags of (G, q) will be denoted by [F.sub.k] (G, q).
Algorithm 1: Algorithm for computing a free resolution of M
(Schreyer's algorithm)

Input:

Graded polynomial ring R = K[x],
Monomial ordering < on R,
Graded submodule M of the free R-module F-1 generated by formal
symbols [{[e]}.sub.e [member of] E],
Module ordering [<.sub.0] on F-1 extending the monomial ordering <,
Finite set G forming a homogeneous Grobner basis for (M,
[<.sub.0]).

Output:

A free resolution: [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN
ASCII].

Initialization:

[G.sub.0]:= G;
[F.sub.0]:= free R-module generated by formal symbols [MATHEMATICAL
EXPRESSION NOT REPRODUCIBLE IN ASCII]; Output [F.sub.0];
[[phi].sub.0]: [F.sub.0] [right arrow] M [subset or equal to]
[F.sub.-1] defined by [g] [right arrow] g for each g [member of]
[G.sub.0]; Output [[phi].sub.0]; i=0;
while [F.sub.i] [not equal to] 0 do
  [[??].sub.i]: arbitrary total ordering on [G.sub.i];
  [<.sub.i+1]: module ordering on [F.sub.i] obtained from [<.sub.i]
    on [F.sub.i-1] (as in (2));
  [G.sub.i+1]: = [S.sub.min]([G.sub.i]) [subset] [F.sub.i], a minimal
    Grobner basis of ([syz.sub.i+1](G), [<.sub.i+1]) (as in Theorem
    2.2);
  [F.sub.i+1]: = free R-module generated by formal symbols
    [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; Output
    [F.sub.i+1];
  [[phi].sub.i+1]: [F.sub.i+1] [right arrow] [F.sub.i] defined by [u]
    [right arrow] u for each u [member of] [G.sub.i+1]; Output
    [[phi].sub.i+1]; i [left arrow] i + 1;
end


Remark 3.2 For a complete graph, [F.sub.k](G, q) is simply the order complex of C(G, q), but in general [F.sub.k](G, q) is not a simplicial complex.

Definition 3.3 Given U [member of] [F.sub.k] (G, q) we define:

(a) a "partial orientation" of G by orienting edges from [U.sub.i] to [U.sub.i+1]\[U.sub.i] (for all 1 [less than or equal to] i [less than or equal to] k - 1) and leaving all other edges unoriented. We denote the resulting partially oriented graph by G(U).

(b) an effective divisor D(U) [member of] Div(G) given by D(U): = [[summation].sup.k-1.sub.i=1] D([U.sub.i+1]\[U.sub.i], [U.sub.i]).

Remark 3.4 It is easy to check that D(U) = [[summation].sub.[upsilon] [member of] V(G)] ([indeg.sub.G](W) ([upsilon]))([upsilon]), where [indeg.sub.G](W) ([upsilon]) denotes the number of oriented edges directed to [upsilon] in G(U).

3.2 Total ordering on [F.sub.k](G, q)

We endow each [F.sub.k](G, q) with a total orderings [[??].sub.k] for all 1 [less than or equal to] k [less than or equal to] n. These total orderings are compatible with each other for different values of 1 [less than or equal to] k [less than or equal to] n. Let [??] denote the ordering on [C.sup.op](G, q) given by reverse inclusion:

U [??] V [??] U [contains or equal to] V.

Definition 3.5 We fix, once and for all, a total ordering extending [??]. By a slight abuse of notation, [??] will be used to denote this total ordering extension. In particular [??] will denote the associated strict total order.

We consider one of the natural "lexicographic extensions" of [??] to the set of connected k-flags.

Definition 3.6 For U [not equal to] V in [F.sub.k] (G, q) written as

U: [U.sub.1] [subset or not equal to] [U.sub.2] [subset or not equal to] ... [subset or not equal to] [U.sub.k] = V(G)

V: [V.sub.1] [subset or not equal to] [V.sub.2] [subset or not equal to] ... [subset or not equal to] [V.sub.k] = V(G)

we say U [[??].sub.k] V if for the maximum 1 [less than or equal to] l [less than or equal to] k - 1 with U = V we have [U.sub.l] [??] [V.sub.l].

As usual, we write U [[??].sub.k] V if and only if U [[??].sub.k] V or U = V.

Lemma 3.7 ([F.sub.k](G, q), [[??].sub.k]) is a totally ordered set.

It is easy to find two different connected k-flags having identical associated partially oriented graphs. This motivates the following definition.

Definition 3.8 Two k-flags U, V [member of] [F.sub.k] (G, q) are called equivalent if the associated partially oriented graphs G(U) and G(V) coincide.

Notation 1 The set of all equivalence classes in [F.sub.k] (G, q) will be denoted by [[??].sub.k] (G, q). The set [S.sub.k] (G, q) denotes the collection of minimal representatives of the classes in [E.sub.k](G, q) with respect to [[??].sub.k].

Given an element in [[??].sub.k](G, q) there is a canonical way to obtain two related elements in [[??].sub.k-1](G, q).

Definition 3.9 Given U [member of] [F.sub.k](G, q), the elements [U.sup.(1)], [U.sup.(2)] [member of] [F.sub.k-1](G, q) are obtained from U by removing the 1st and 2nd elements in the following appropriate sense. Let

U: [U.sub.1] [subset or not equal to] [U.sub.2] [subset or not equal to] ... [subset or not equal to] V(G) .

(a) [U.sup.(1)] will denote

[U.sub.2] [subset or not equal to] [U.sub.3] [subset or not equal to] [U.sub.4] [subset or not equal to] ... C V(G).

(b) [U.sup.(2)] will denote

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Remark 3.10 [MS12, Section 6.1] Assume that U [member of] [[??].sub.k](G, q). Let [G.sub./U] be the graph obtained from G by contracting the unoriented edges of G(U) and let [phi]: G [right arrow] G/W be the contraction map. More precisely, [G.sub./U] is the graph on the vertices [u.sub.1], ..., [u.sub.k] corresponding to the collection [([U.sub.i]\[U.sub.i-1]).sup.k.sub.i=1], i.e. [u.sub.i] = [phi]([U.sub.i]\[U.sub.i-1]). For any edge between [U.sub.i]\[U.sub.i-1] and [U.sub.j]\[U.sub.j-1] there is an edge between [u.sub.i] and [u.sub.j]. The contraction map [phi]: G [right arrow] [G.sub./U] induces the maps

(i) [[phi].sub.*]: Div(G) [right arrow] Div([G.sub./U]) with [[phi].sub.*]([[summation].sub.[upsilon] [member of] V(G)] [a.sub.[upsilon]]([upsilon])) = [[summation].sub.[upsilon] [member of] V(G)] [a.sub.v]([phi]([upsilon])). In particular, a total ordering [u.sub.1], ..., [u.sub.k] of V([G.sub./U]) gives a total ordering on the collection of subsets [([U.sub.i]\[U.sub.i-1]).sup.k.sub.i=1] of V(G). By Definition 3.3 we get a divisor D' on [G.sub./U] and a divisor D on G, and [[phi].sub.*](D) = D'. In other words, such a divisor D' has a canonical section.

(ii) [[phi].sup.*]: [[??].sub.s]([G.sub./U], [u.sub.1]) [right arrow] [[??].sub.s](G, q) with [[phi].sup.*](V') = V where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4 Minimal free resolution and Betti numbers for [I.sub.G] and in([I.sub.G])

Let K be a field and let R = K[x] be the polynomial ring in n variables {[x.sub.[upsilon]]: [upsilon] [member of] V(G)}. Recall that K[x] has a natural A-grading, where A = Z or A = Pic(G) and [I.sub.G] is also A- graded. Let the monomial ordering < on R be as in Definition 2.1.

The following theorem gives a generalization of [CRS02, Theorem 14]. Indeed [CRS02, Theorem 14] can be rephrased as providing a bijection between [[??].sub.2](G, q) and G(G, q).

Theorem 4.1 Fix a pointed graph (G, q) and let A = Z or A = Pic(G). For each k [greater than or equal to] 0 there exists a natural injection

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

such that

(i) For some module ordering [<.sub.k], the set [G.sub.k](G, q): = Image([[psi].sub.k]) forms a minimal A-homogeneous Grobner basis of ([syz.sub.k](G(G, q)), [<.sub.k]),

(ii) For U [member of] [[??].sub.k+2](G, q) of the form [U.sub.1] [subset or not equal to] [U.sub.2] [subset or not equal to] ... [subset or not equal to] V (G) we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (5)

(iii) The set [[psi].sub.k]([[??].sub.k+2](G, q)) minimally generates [syz.sub.k](G(G, q)).

Sketch of proof: Here we list the key steps of the proof. For a complete proof we refer to [MS12]. For consistency in the notation we define [syz.sub.-1] (G(G, q)) = {0} and the map

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] {0}

sends the canonical connected 1-flag V(G) to 0. The proof is by induction on k [greater than or equal to] 0.

Base case. For k = 0 the result is proved in [CRS02, Theorem 14]. Here [G.sub.0](G, q) = G(G, q) and [<.sub.0] is <, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Induction hypothesis. Now let k > 0 and assume that there exists a bijection

[[psi].sub.k-1]: [[??].sub.k+1](G, q) [right arrow] [G.sub.k-1](G, q) [subset or not equal to] [syz.sub.k-1](G(G, q))

such that [G.sub.k-1] (G, q) forms a minimal homogeneous Grobner basis of [syz.sub.k-1](G(G, q)) with respect to [<.sub.k-1]), and (5) for the leading monomials holds.

Via the bijection the set [G.sub.k-1] (G, q) inherits a total ordering [[??]'.sub.k-1] from the total ordering [[??].sub.k+1] on [[??].sub.k+1] (G, q), i.e.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Inductive step. Given U [member of] [[??].sub.k+2] (G, q) let [U.sup.(1)] and [U.sup.(2)] be as defined in Definition 3.9. We define

[[psi].sub.k]: [[??].sub.k+2](G, q) [right arrow] [syz.sub.k](G(G, q)) u [right arrow] s([[psi].sub.k-1]([U.sup.(1)]), [[psi].sub.k-1]([U.sup.(2)])). (6)

In the following U, V [member of] [[??].sub.k+2] (G, q) are of the form

[U.sub.1] [subset or not equal to] [U.sub.2] [subset or not equal to] ... [subset or not equal to] V(G) [V.sub.1] [subset or not equal to] [V.sub.2] [subset or not equal to] ... C V(G).

The result is follows from a series of claims.

Claim 1. [[psi].sub.k] is a well-defined and [G.sub.k] (G, q): = Image([[psi].sub.k]) consists of homogeneous elements.

Since [[psi].sub.k-1]([U.sup.(1)]) and [[psi].sub.k-1]([U.sup.(2)]) are homogeneous by induction hypothesis, it follows that s([[psi].sub.k- 1]([U.sup.(1)]) [[psi].sub.k-1]([U.sup.(2)])) is also homogeneous.

Claim 2. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

It suffices to show that D([U.sub.2]\[U.sub.1], [U.sub.1]) = max([alpha], [beta]) - [alpha] where

LM([[psi].sub.k-1] ([U.sup.(1)]) = [x.sup.[alpha]][[[psi].sub.k- 2]([U.sup.(1,1)], LM([[psi].sup.k-1]([U.sup.(2)])) = [[[psi].sub.k- 2]([U.sup.(2,1)])].

Claim 3. [[psi].sub.k] is injective.

If U, V [member of] [[??].sub.k+2](G, q) be such that [[psi].sub.k](U) = [[psi].sub.k](V) then their leading terms are equal:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Therefore [[psi].sub.k-1] ([U.sup.(1)]) = [[psi].sub.k-1] ([V.sup.(1)]) and D([U.sub.2]\[U.sub.1], [U.sub.1]) = D([V.sub.2]\[V.sub.1], [V.sub.1]). By induction hypothesis [[psi].sub.k-1] is injective which implies [U.sup.(1)] = [V.sup.(1)] and D([U.sub.2]\[U.sub.1], [U.sub.1]) = D([V.sub.2]\[V.sub.1], [V.sub.1]). Therefore [U.sub.1] = [V.sub.1] and U = V.

The following claim (proved in [MS12]) will finish the inductive step.

Claim 4. Image([[psi].sub.k]) forms a minimal homogeneous Grobner basis of [syz.sub.k] (G(G, q)) with respect to [<.sub.k] obtained from [<.sub.k-1] according to (2).

These all together show that Image([[psi].sub.k]) [subset or not equal to] S([G.sub.k-1] (G, q)). In order to show the reverse inclusion by Theorem 2.2 it remains to show that

(I) 0 [not member of] Image([[psi].sub.k]).

(II) For any element s(f, h) [member of] S([G.sub.k-1](G, q)) there exists an element g [member of] Image([[psi].sub.k]) such that LM(g) | LM(s(f, h)).

(III) For any two elements g, g' [member of] Image([[psi].sub.k]), if LM(g) | LM(g') then g = g'.

Claim 5. For [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where c(U, W) [member of] {-1, 0, 1} and [theta](U, W) = D([U.sub.i]\[U.sub.i-1], [U.sub.j]\[U.sub.j-1]) if W differs from U by merging [U.sub.i]\[U.sub.i-1] and [U.sub.j]\[U.sub.j-1] for some i, j.

Note that this proves (III) which is equivalent to the minimality of the resolution.

From Theorem 4.1 we obtain the following important corollaries.

Corollary 4.2 The Betti numbers of the ideals [I.sub.G] and in([I.sub.G)] are independent of the characteristic of the base field K.

Corollary 4.3 For all i [greater than or equal to] 0, [[beta].sub.i](R/[I.sub.G]) = [[beta].sub.i](R/in([I.sub.G)]) = [absolute value of [[??].sub.i+1](G,q)] = [absolute value of [E.sub.i+1] (G,q)].

Let A = Z or A = Pic(G). Recall that [I.sub.G] and in([I.sub.G)] are graded (or homogeneous) with respect to the Z and Pic(G) gradings. One can also read the graded Betti numbers from Theorem 4.1.

Corollary 4.4 For all i [greater than or equal to] 0 and j [member of] A we have [[beta].sub.i,j] = [absolute value of [[??].sub.i+1,j] (G, q)] where [[??].sub.k,j](G, q) = {U [member of] [[??].sub.k]c(G, q): [deg.sub.A]([x.sup.D(U)]) = j}.

We conclude this section with some examples.

Example 4.5 It follows from above descriptions that [[beta].sub.n-1] (R/[I.sub.G]) = [[beta].sub.n-1], m(R/[I.sub.G]) is equal to the number of acyclic orientations of G with unique source.

Example 4.6 Let G be the complete graph [K.sub.n] on n vertices. Then [[beta].sub.k-1](R/[I.sub.G]) = [absolute value of [[??].sub.k](G, q)] = (k - 1)! S(n, k) where S(n, k) denotes the Stirling number of the second kind (i.e. the number of ways to partition a set of n elements into k nonempty subsets).

Example 4.7 Let G be a tree on n vertices. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Example 4.8 For the cycle [C.sub.n] on n vertices and k [greater than or equal to] 2 we have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5 Relation to maximal reduced divisors

Recall the definition of reduced divisors.

Definition 5.1 Let ([GAMMA], [[upsilon].sub.0]) be a pointed graph. A divisor D [member of] Div([GAMMA]) is called [[upsilon].sub.0]-reduced if it satisfies the following two conditions :

(i) D([upsilon]) [greater than or equal to] 0 for all [upsilon] [member of] V([GAMMA])\{[[upsilon].sub.0]}.

(ii) For every non-empty subset A [subset or equal to] V([GAMMA])\{[[upsilon].sub.0]}, there exists a vertex [upsilon] [member of] A such that D([upsilon]) < [outdeg.sub.A]([upsilon]).

These divisors arise precisely from the normal forms with respect to the Grobner basis given in Theorem 4.1. There is a well-known algorithm due to Dhar for checking whether a given divisor is reduced (see, e.g., [BS13] and references therein).

Lemma 5.2 For U [member of] [[??].sub.k](G, q), [[phi].sub.*](D(U)) = E + 1, where E is a maximal ([phi]([U.sub.1]))-reduced divisor and 1 is the all-one divisor.

Since different acyclic orientations with unique source at q' give rise to inequivalent q'-reduced divisors we deduce that if U, V [member of] [[??].sub.k] (G, q) and the graphs [G.sub./U] and [G.sub./V] coincide, then [[phi].sub.*](D(U)) - 1 and [[phi].sub.*](D(V)) - 1 are two inequivalent maximal reduced divisors. These observations lead to the following formula for Betti numbers which was conjectured in [PPW11] for [I.sub.G]:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum is over all distinct contracted graphs [G.sub./U] as U varies in [[??].sub.i+1](G, q), and [[upsilon].sub.0] is an arbitrary vertex of [G.sub./U].

Here is another connection with reduced divisors. Hochster's formula for computing the Betti numbers topologically (see, e.g., [MS05, Theorem 9.2]), when applied to [I.sub.G] and the "nice" grading by Pic(G), says that for each j [member of] Pic(G) the graded Betti number [[beta].sub.i,j](R/[I.sub.G]) is the dimension of the ith reduced homology of the simplicial complex [[DELTA].sub.j] = {supp(E): 0 [less than or equal to] E [less than or equal to] D' e [member of] [absolute value of j]} where [absolute value of j] denotes the linear system of j [member of] Pic(G).

Remark 5.3

(i) For j [member of] Pic(G), we have [[beta].sub.n-1,j](R/[I.sub.G]) = 1 if and only if j ~ E + 1 where E is a maximal q-reduced divisor.

(ii) One can use Corollary 4.3 to read all dimensions of the reduced homologies of [[DELTA].sub.j]. Although we now know all the Betti numbers, giving an explicit bijection between connected flags and the bases of the reduced homologies of [[DELTA].sub.j] is an intriguing problem. In a recent work, Horia Mania in [Man12] studies the number of connected components of [[DELTA].sub.j].

Acknowledgements

The first author is grateful to Helene Barcelo and Volkmar Welker for numerous comments and many helpful conversations. Part of this work was done while the second author was visiting UC Berkeley, which he would like to thank for the hospitality.

References

[Big97] N. Biggs. Algebraic potential theory on graphs. Bull. London Math. Soc., 29(6): 641-682, 1997.

[BN07] M. Baker and S. Norine. Riemann-Roch and Abel-Jacobi theory on a finite graph. Adv. Math., 215(2): 766-788, 2007.

[BS13] M. Baker and F. Shokrieh. Chip-firing games, potential theory on graphs, and spanning trees. Journal of Combinatorial Theory, Series A, 120(1) :164- 182, 2013.

[CHT06] A. Conca, S. Hosten, and R. R. Thomas. Nice initial complexes of some classical ideals. In Algebraic and geometric combinatorics, volume 423 of Contemp. Math., pages 11- 42. Amer. Math. Soc., Providence, RI, 2006.

[CRS02] R. Cori, D. Rossin, and B. Salvy. Polynomial ideals for sandpiles and their Grobner bases. Theoret. Comput. Sci., 276(1-2): 1-15, 2002.

[Dha90] D. Dhar. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett., 64(14):1613-1616, Apr 1990.

[DS12] A. Dochtermann and R. Sanyal. Laplacian ideals, arrangements, and resolutions. Preprint available at arXiv:1212.6244, 2012.

[Eis95] D. Eisenbud. Commutative algebra, with a view toward algebraic geometry, volume 150 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.

[Gab93] A. Gabrielov. Abelian avalanches and Tutte polynomials. Phys. A, 195(1- 2):253-274, 1993.

[GK08] A. Gathmann and M. Kerber. A Riemann-Roch theorem in tropical geometry. Math. Z., 259(1):217-230, 2008.

[GP08] G. Greuel and G. Pfister. A Singular introduction to commutative algebra. Springer, Berlin, extended edition, 2008.

[Lor89] D. Lorenzini. Arithmetical graphs. Math. Ann., 285(3) :481-501, 1989.

[Man12] H. Mania. Wilmes' conjecture and boundary divisors. Preprint, 2012.

[MS05] E. Miller and B. Sturmfels. Combinatorial commutative algebra, volume 227 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2005.

[MS12] F. Mohammadi and F. Shokrieh. Divisors on graphs, connected flags, and syzygies. Preprint available at arXiv:1210.6622, 2012.

[MS13a] M. Manjunath and B. Sturmfels. Monomials, binomials and Riemann-Roch. Journal of Algebraic Combinatorics, pages 1-20, 2013. to appear.

[MS13b] F. Mohammadi and F. Shokrieh. Divisors on graphs and cellular resolutions. In preparation, 2013.

[MSW12] M. Manjunath, F. Schreyer, and J. Wilmes. Minimal free resolutions of the g-parking function ideal and the toppling ideal. Preprint available at arXiv:1210.7569v2, 2012.

[MZ08] G. Mikhalkin and I. Zharkov. Tropical curves, their Jacobians and theta functions. In Curves and abelian varieties, volume 465 of Contemp. Math., pages 203-230. Amer. Math. Soc., Providence, RI, 2008.

[PPW11] D. Perkinson, J. Perlman, and J. Wilmes. Primer for the algebraic geometry of sandpiles. 2011. Preprint available at arXiv:1112.6163.

[PS04] A. Postnikov and B. Shapiro. Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Amer. Math. Soc., 356(8):3109-3142 (electronic), 2004.

[Ray70] M. Raynaud. Specialisation du foncteur de Picard. Inst. Hautes Etudes Sci. Publ. Math., (38):27-76, 1970.

[Sch80] F. Schreyer. Die Berechnung von Syzygien mit dem verallgemeinerten Weierstrass'schen Divisionssatz. Diplom Thesis, University of Hamburg,

Germany., 1980.

Fatemeh Mohammadi (1) ([dagger]) and Farbod Shokrieh (2) ([double dagger])

(1) Fachbereich Mathematik und Informatik, Philipps-Universitat, Marburg, Germany

(2) Georgia Institute of Technology, Atlanta, Georgia, USA

([dagger]) Supported by the Mathematical Sciences Research Institute and the Alexander von Humboldt Foundation.

([double dagger]) Partially supported by NSF grants DMS-0901487
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Mohammadi, Fatemeh; Shokrieh, Farbod
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUGE
Date:Jan 1, 2013
Words:6356
Previous Article:Periodic patterns of signed shifts.
Next Article:Counting strings over [Z2.sup.d] with given elementary symmetric function evaluations.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters