Adrien Boussicault
email: adrien.boussicault@univ-mlv.fr

Valentin F Éray

Alain Lascoux
email: alain.lascoux@univ-mlv.fr

Victor Reiner
email: reiner@math.umn.edu

LINEAR EXTENSION SUMS AS VALUATIONS ON CONES

Keywords: 1991 Mathematics Subject Classification. 06A11 52B45, 52B20, poset, rational function identities, valuation of cones, lattice points, affine semigroup ring, Hilbert series, total residue, root system, weight lattice

The geometric and algebraic theory of valuations on cones is applied to understand identities involving summing certain rational functions over the set of linear extensions of a poset.

Introduction

This paper presents a different viewpoint on the following two classes of rational function summations, which are both summations over the set L(P ) of all linear extensions of a partial order P on the set {1, 2, . . . , n}:

Ψ P (x) := w∈L(P ) w 1 (x 1 -x 2 )(x 2 -x 3 ) • • • (x n-1 -x n ) ; Φ P (x) := w∈L(P ) w 1 x 1 (x 1 + x 2 )(x 1 + x 2 + x 3 ) • • • (x 1 + • • • + x n ) .
Recall that a linear extension is a permutation w = (w(1), . . . , w(n)) in the symmetric group S n for which the linear order P w defined by w(1) < Pw • • • < Pw w(n) satisfies i < Pw j whenever i < P j.

Several known results express these sums explicitly for particular posets P as rational functions in lowest terms. In the past, these results have most often been proven by induction, sometimes in combination with techniques such as divided differences and more general operators on multivariate polynomials. We first explain three of these results that motivated us. 1.1. Strongly planar posets. The rational function Ψ P (x) was introduced by C. Greene [START_REF] Greene | A rational-function identity related to the Murnaghan-Nakayama formula for the characters of Sn[END_REF] in his work on the Murnaghan-Nakayama formula. There he evaluated Ψ P (x) when P is a strongly planar poset in the sense that the poset P ⊔ { 0, 1} with an extra bottom and top element has a planar embedding for its Hasse diagram, with all edges directed upward in the plane. To state his evaluation, note that in this situation, the edges of the Hasse diagram for P dissect the plane into bounded regions ρ, and the set of vertices lying on the boundary of ρ will consist of two chains, having a common minimum element min(ρ) and maximum max(ρ) element in the partial order P .

Theorem A. (Greene [START_REF] Greene | A rational-function identity related to the Murnaghan-Nakayama formula for the characters of Sn[END_REF]Theorem 3.3]) For any strongly planar poset P , Ψ P (x) = ρ (x min(ρ)x max(ρ) )

i⋖P j (x ix j ) where the product in the denominator runs over all covering relations i ⋖ P j, or over the edges of the Hasse diagram for P , while the product in the numerator runs over all bounded regions ρ for the Hasse diagram for ρ.

1.2. Skew diagram posets. Further work on Ψ P (x) appeared in [START_REF] Boussicault | Operations on Posets and Rational Identities of Type A[END_REF][START_REF] Boussicault | Action du groupe symétrique sur certaines fractions rationnelles suivi de Puissances paires du Vandermonde[END_REF][START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF][START_REF]Ilyuta Calculus of linear extensions and Newton interpolation[END_REF]. For example, we will prove in Section 4 the following generalization of a result of the first author. Consider a skew (Ferrers) diagrams D = λ/µ, in English notation as a collection of points (i, j) in the plane, where rows are numbered 1, 2, . . . , r from top to bottom (the usual English convention), and the columns numbered 1, 2, . . . , c from right to left (not the usual English convention). Thus the northeasternmost and southwesternmost points of D are labelled [START_REF] Barvinok | Computing the volume, counting integral points, and exponential sums[END_REF][START_REF] Barvinok | Computing the volume, counting integral points, and exponential sums[END_REF] and (r, c), respectively; see Example 4.3. Define the bipartite poset P D on the set {x 1 , . . . , x r , y 1 , . . . , y c } having an order relation x i < PD y j whenever (i, j) is a point of D.

Theorem B. For any skew diagram D,

Ψ PD (x) = π (i,j)∈D\π (x i -y j ) (i,j)∈D (x i -y j )
.

where the product in the numerator runs over all lattice paths π from (1, 1) to (r, c) inside D that take steps either one unit south or west.

In particular (Boussicault [8,Prop. 4.7.2]), when µ = ∅, so that D is the Ferrers diagram for a partition 1 λ, this can be rewritten

Ψ PD (x) =
S ŵ (x, y) S w (x, y)

where S w (x, y), S ŵ (x, y) are the double Schubert polynomials for the dominant permutation w having Lehmer code λ = (λ 1 , . . . , λ r ), and the vexillary permutation ŵ having Lehmer code λ := (0, λ 2 -1, . . . , λ r -1).

1.3. Forests. In his treatment of the character table for the symmetric group S n , D.E. Littlewood [20, p. 85] used the fact that the antichain poset P = ∅, having no order relations on {1, 2, . . . , n} and whose set of linear extensions L(∅) is equal to all of S n , satisfies

(1.1) Φ ∅ (x) = 1 x 1 x 2 • • • x n .
The following generalization appeared more recently in [START_REF] Chapoton | An operational calculus for the Mould operad[END_REF]. Say that a poset P is a forest if every element is covered by at most one other element.

Theorem C. (Chapoton, Hivert, Novelli, and Thibon [START_REF] Chapoton | An operational calculus for the Mould operad[END_REF]Lemma 5.3]) For any forest poset P ,

Φ P (x) = 1 n i=1 j≤P i x j
.

1 Such bipartite graphs were called λ-complete in [START_REF] Boussicault | Action du groupe symétrique sur certaines fractions rationnelles suivi de Puissances paires du Vandermonde[END_REF], and sometimes appear in the literature under the name Ferrers graphs.

1.4. The geometric perspective of cones. Our first new perspective on these results views Ψ P (x), Φ P (x) as instances of a well-known valuation on convex polyhedral cones K in a Euclidean space V with inner product •, • s(K; x) := K e -x,v dv.

One can think of s(K; x) as the multivariable Laplace transform applied to the {0, 1}-valued characteristic function of the cone K. After reviewing the properties of this valuation in Section 2, we use these to establish that Ψ P (x) = s(K root P ; x)

Φ P (x) = s(K wt P ; x) where K root P , K wt P are two cones naturally associated to the poset P as follows: K root P = R + {e ie j : i < P j} K wt P = {x ∈ R n + : x i ≥ x j for i < P j}, R + denotes the nonnegative real numbers. In Sections 4 and 5, this identification is used, together with the properties of s(K; x) from Section 2, to give simple geometric proofs underlying Theorems B and C above.

1.5. The algebraic perspective of Hilbert series. One gains another useful perspective when the cone K is rational with respect to some lattice L inside V , which holds for both K root P , K wt P . This allows one to compute a more refined valuation, the multigraded Hilbert series

Hilb(K ∩ L; x) := v∈K∩L e x,v
for the affine semigroup ring k[K ∩ L] with coefficients in any field k. As discussed in Section 2.4 below, it turns out that Hilb(K ∩ L; x) is a meromorphic function of x 1 , . . . , x n , whose Laurent expansion begins in total degree -d, where d is the dimension of the cone K, with this lowest term of total degree -d equal to s(K; x), up to a predictable sign. This allows one to algebraically analyze the ring k[K ∩ L], compute its Hilbert series, and thereby recover s(K; x).

For example, in Section 8.3, it will be shown that Theorem A by Greene is the reflection of a complete intersection presentation for the affine semigroup ring of K root P when P is a strongly planar poset, having generators indexed by the edges in the Hasse diagram of P , and relations among the generators indexed by the bounded regions ρ.

As another example, in Section 6, it will be shown that Theorem C, along with the "maj" hook formula for forests due to Björner and Wachs [5, Theorem 1.2] are both consequences of an easy Hilbert series formula (Proposition 6.2 below) related to K wt P when P is a forest.

Cones and valuations

2.1.

A review of cones. We review some facts and terminology about polyhedral cones; see, e.g., [START_REF] Miller | Combinatorial commutative algebra[END_REF]Chapter 7], [23, §4.6] for background. Let V be an n-dimensional vector space over R. A linear function ℓ in V * has as zero set a hyperplane H containing the origin, and defines a closed halfspace H + consisting of the points v in V with ℓ(v) ≥ 0. A polyhedral cone K (containing the origin 0) in V is the intersection K = i H + i of finitely many linear halfspaces H + i , or alternatively the nonnegative span K = R + {u 1 , . . . , u N } of finitely many generating vectors u i in V . Its dimension, denoted dim R K, is the dimension of the smallest linear subspace that contains it. One says

K is full-dimensional if dim R K = n = dim R V .
Say that K is pointed if it contains no lines. In this case, if {u 1 , . . . , u N } are a minimal set of vectors for which K = R + {u 1 , . . . , u N }, then the u i are said to span the extreme rays R + u i of K; these rays are unique, although the choice of vectors u i are unique only up to positive scalings.

Say that K is simplicial if its extreme rays are spanned by a linearly independent set of vectors {u 1 , . . . , u N }, so that N = dim R K ≤ n.

In the dual space V * one has the dual or polar cone

K * := {x ∈ V * : x, v ≥ 0 for all v ∈ K}.
The following facts about duality of cones are well-known:

• Under the identification (V * ) * = V , one has (K * ) * = K. • A cone K is pointed (resp. full-dimensional) if and only if its dual cone K * is full-dimensional (resp. pointed). • A cone K is simplicial if and only if its dual cone K * is simplicial.
2.2. The Laplace transform valuation. Choose a basis v 1 , . . . , v n for V and dual basis x 1 , . . . , x n for V * . Then the polynomial functions Q[V ] on V are identified with the symmetric/polynomial algebras Sym(V * ) ∼ = R[x 1 , . . . , x n ] and the rational functions Q(V ) on V with the field of fractions Q(x 1 , . . . , x n ).

In order to consider integrals on V , let dv = dv 1 • • • dv n denote Lebesgue measure on R n ∼ = V using the basis v 1 , . . . , v n for this identification.

The following proposition defining our first valuation is well-known; see ,e.g., [1, Proposition 2.4], [START_REF] Berline | Local Euler-Maclaurin formula for polytopes[END_REF]Proposition 5].

Proposition 2.1. There exists a unique assignment of a rational function s(K; x) lying in Q(V ) = Q(x 1 , . . . , x n ) to each polyhedral cone K, having the following properties:

(i) s(K; x) = 0 when K is not pointed. (ii) s(K; x) = 0 when K is not full-dimensional.
(iii) When K is pointed and full-dimensional, for each x in the dual cone K * the improper integral K e -x,v dv converges, to the value given by the rational function s(K; x). (iv) When K is pointed and full-dimensional, with extreme rays spanned by {u 1 , . . . , u N }, the rational function s(K; x) can be written with smallest denominator N i=1 x, u i . (v) In particular, when K is full-dimensional and simplicial, with extreme rays spanned by {u 1 , . . . , u n }, then

s(K; x) = | det[u 1 , . . . , u n ]| n i=1 x, u i .
(vi) The map s(-; x) is a solid valuation, that is, if there is a linear relation t i=1 c i χ Ki = 0 among the characteristic functions χ Ki of the cones K i , there will be a linear relation

i:dim R Ki=n c i s(K i ; x) = 0.
2.3. The semigroup ring and its Hilbert series. Now endow the n-dimensional real vector space V with a distinguished lattice L of rank n, and assume that the chosen basis v 1 , . . . , v n for V is also a Z-basis for L. Say that the polyhedral cone K is rational with respect to L if one can express K = R + {u 1 , . . . , u N } for some elements u i in L. The subset K ∩ L together with its additive structure inherited from addition of vectors in V is then called an affine semigroup. Our goal here is to describe how one can approach the computation of the previous valuation s(K; x) for pointed cones K through the calculation of the finely graded Hilbert series for this affine semigroup:

Hilb(K ∩ L; x) := v∈K∩L e x,v .
One should clarify how to interpret this infinite series, as it lives in several ambient algebraic objects. Firstly, it lies in the abelian group Z{{L}} of all formal combinations v∈L c v e x,v with c v in Z, in which there are no restrictions on vanishing of the coefficients c v . This set Z{{L}} forms an abelian group under addition, but is not a ring. However it contains the Laurent polynomial ring

Z[L] ∼ = Z[X ±1
1 , . . . , X ±n n ] as the subgroup where only finitely many of the c v are allowed to be nonzero, using the identification via the exponential change of variables (2.1)

X i = e x,vi , so that X c1 1 • • • X cn n = X v = e x,v if v := n i=1 c i v i .
Furthermore, Z{{L}} forms a module over this subring Z[L]. One can also define the Z[L]-submodule of summable elements (see [START_REF] Miller | Combinatorial commutative algebra[END_REF]Definition 8.3.9]), namely those f in Z{{L}} for which there exists p, q in Z[L] with q = 0 and q • f = p. In this situation, say that f sums to p q as an element of the fraction field

Q(L) ∼ = Q(X 1 , . . . , X n ).
General theory of affine semigroups (see, e.g., [START_REF] Miller | Combinatorial commutative algebra[END_REF]Chapter 8]) says that for a rational polyhedral cone K and the semigroup K ∩ L, the Hilbert series Hilb(K ∩ L; x) is always summable. More precisely,

• when K is not pointed, Hilb(K ∩ L; x) sums to zero. This is because K will not only contain a line, but also an L-rational line, and then any nonzero vector v of L lying on this line will have (1e x,v ) • Hilb(K ∩ L; x) = 0. • when K is pointed and {u 1 , . . . , u N } are vectors in L that span its extreme rays, then one can show that Proposition 2.2. Let V be an n-dimensional vector space V . Let L be the sublattice in V with Z-basis v 1 , . . . , v n , and V * the dual space, with dual basis x 1 , . . . , x n .

Then there exists a well-defined and unique assignment of a rational function H(K; X) lying in Q(X 1 , . . . , X n ) to each L-rational polyhedral cone K, having the following properties:

(i) H(K; X) = 0 when K is not pointed.

(ii) When K is pointed, the Hilbert series Hilb(K ∩ L; x) sums to the element p q = H(K; X), considered as a rational function lying in Q(L). (iii) When K is pointed and full-dimensional, for each x in the dual cone K * the infinite sum v∈K∩L e x,v converges, to the value given by the exponential substitution (2.1) into the rational function H(K; X) (iv) When K is pointed and full-dimensional, with u = {u 1 , . . . , u N } the unique primitive vectors (that is, those lying in L nearest the origin) that span its extreme rays, the rational function H(K; X) can be written with smallest denominator N i=1 (1 -X ui ). (v) In particular, if K is simplicial and u := {u 1 , . . . , u d } its set of primitive vectors that span its extreme rays, define the semi-open parallelepiped

Π u := n i=1 c i u i : 0 ≤ c i < 1 ⊂ V.
Then one has

(2.2) H(K; X) = u∈Πu∩L X u d i=1 (1 -X ui )
.

(vi) The map H(-; X) is a valuation: if there is a linear relation t i=1 c i χ Ki = 0 among the characteristic functions χ Ki of a collection of (L-rational) cones K i , there will be a linear relation

t i=1 c i H(K i ; X) = 0.
2.4. Why H(K; X) is finer than s(K; x). When K is an L-rational cone, there is a well-known way (see, e.g., [START_REF] Brion | Arrangements of hyperplanes I. Rational functions and Jeffrey-Kirwan residue[END_REF]) to compute the Laplace transform valuation s(K; x) from the Hilbert series valuation H(K; X) by a certain linear residue operation, which we now explain. Proposition 2.3. Let K be an L-rational pointed cone, with {u 1 , . . . , u N } vectors in L that span its extreme rays. Regard H(K; X) as a function of the variables x = (x 1 , . . . , x n ) via the exponential substitution (2.1).

Then H(K; X) is meromorphic in x, of the form

H(K; X) = h(K; x) N i=1 x, u i where h(K; x) is analytic in x.
Furthermore, if d := dim R K, then the multivariate Taylor expansion for h(K; x) starts in degree Nd, that is,

h(K; x) = h N -d (K; x) + h N -d+1 (K; x) + • • • .
where h i (K; x) are homogeneous polynomials of degree i, and the multivariate Laurent expansion for H(K; X) starts in degree -d, that is,

H(K; X) = H -d (x) + H -d+1 (x) + H -d+2 (x) + • • • . Lastly, when K is full-dimensional (so d = n), then s(K; x) = (-1) n h N -n (K; x) N i=1 x, u i ) = (-1) n H -n (x)
so that h N -n (K; x) is (-1) n times the numerator for s(K; x) accompanying the smallest denominator described in Proposition 2.1(iv).

Proof. We first check all of the assertions when K is simplicial, say with extreme rays spanned by the vectors u 1 , . . . , u d in L. In this case, N = d and the exponential substitution of variables (2.1) into (2.2) gives

(2.3) H(K; X) = u∈Πu e x,u d i=1 (1 -e x,ui ) = (-1) d u∈Πu e x,u d i=1 x, u i d i=1
x, u i e x,ui -1 .

We wish to be somewhat explicit about the Taylor expansion of each factor in the last product within (2.3). To this end, recall that the function ) that one can triangulate K as a complex of simplicial subcones K 1 , . . . , K t whose extreme rays are all among the extreme rays u 1 , . . . , u N for K. This triangulation lets one express the characteristic function χ K in the form (cf. [START_REF] Stanley | Enumerative Combinatorics[END_REF]Lemma 4.6.4]) χ K = j c j χ Kj where the c j are integers, and c j = +1 whenever the cone K j has the same dimension as K. Thus by Proposition2.1(vi), one has

x e x -1 = n≥0 B n x n n! = 1 - 1 2 x + 1 12 x 2 - 1 720 x 4 + • • • is analytic in the variable x,
H(K; X) = j c i H(K j ; X),
which shows that h(K; x) := N i=1 x, u i H(K; X) is analytic in x. Furthermore after clearing denominators, it gives the expansion

h(K; x) = j c j     i:ui a ray of K, but not of Kj x, u i     h(K j ; x).
Since the simplicial cones K j have at most n extreme rays, this shows h i (K; x) = 0 for i < Nn, and that

h N -n (K; x) = j:dim R Kj=n     i:ui a ray of K, but not of Kj x, u i     h 0 (K j ; x),
using the fact that c j = +1 whenever dim R K j = dim R K. Dividing through by N i=1 x, u i , and multiplying by (-1) n gives

(-1) n h N -n (K; x) N i=1 x, u i = j:dim R Kj=n s(K j ; x) = s(K; x)
where the first equality uses the simplicial case already proven, and the last equality uses Proposition 2.1(v).

The linear operator passing from the meromorphic function H(K; X) of x to the rational function H -n (K; x) = (-1) n s(K; x) has been called taking the total residue in [START_REF] Brion | Arrangements of hyperplanes I. Rational functions and Jeffrey-Kirwan residue[END_REF], where other methods for computing it are also developed.

Complete intersections.

For a pointed L-rational polyhedral cone K, one approach to computing H(K; x) (and hence s(K; x)) is through an algebraic analysis of the affine semigroup K ∩ L and its affine semigroup ring

R := k[K ∩ L] = k{e u } u∈(K∩L)
over some coefficient field k. We discuss this here, with the case where R is a complete intersection being particularly simple.

For any semigroup elements u 1 , . . . , u m in K ∩L, one can introduce a polynomial ring S := k[U 1 , . . . , U m ], and a ring homomorphism S -→ R sending U i -→ e ui . This map makes R into an S-module. One also has a fine L-multigrading on R and S for which deg(U i ) = deg(e ui ) = u i . This makes R an L-graded module over the L-graded ring S. It is not hard to see that R is a finitely-generated S-module if and only if {u 1 , . . . , u m } contain at least one vector spanning each extreme ray of K.

When u 1 , . . . , u m generate (not necessarily minimally) the semigroup K ∩ L, the map S → R is surjective, and its kernel I is often called the toric ideal for u 1 , . . . , u m . As R = S/I, and because S has Krull dimension m while R has Krull dimension d := dim R K, the number of generators for the ideal I is at least md. The theory of Cohen-Macaulay rings says that, since the polynomial algebra S is Cohen-Macaulay, whenever the ideal I in S can be generated by exactly md elements f 1 , . . . , f m-d then these elements must form an S-regular sequence: for each i ≥ 1, the image of f i forms a nonzero divisor in the quotient S/(f 1 , . . . , f i-1 ). In this case, the presentation R = S/I = S/(f 1 , . . . , f m-d ) is said to present R as a complete intersection. A simple particular case of this occurs when the toric ideal I is principal, as in Example 2.6 and in Corollary 8.2. By a standard calculation using the nonzero divisor condition (see, e.g., [21, §13.4, p. 264]) one concludes the following factorization for H(K; X) and s(K; x). Proposition 2.5. Let K be a pointed L-rational cone for which the associated affine semigroup ring R = k[K ∩ L] can be presented as a complete intersection

R = S/I = k[U 1 , . . . , U m ]/(f 1 , . . . , f m-d )
where U i = e ui for some generators u 1 , . . . , u m of K ∩ L, and where f 1 , . . . , f m-d are L-homogeneous elements of S with degrees δ 1 , . . . , δ m-d . Then

H(K; X) = m-d i=1 (1 -X δi ) m j=1 (1 -X uj ) and if d = n then s(K; x) = m-n i=1 x, δ i m j=1 x, u j .
Example 2.6. Let V = R 3 with standard basis e 1 , e 2 , e 3 and let K be the fulldimensional, pointed cone whose extreme rays are generated by the four vectors

u 1 = e 1 u 2 = e 1 +e 2 u 3 = e 1 +e 3 u 4 = e 1 +e 2 +e 3 . u 1 u 4 3 u u 2 K K K 1 2
Note that K is not simplicial, but it can be expressed as K = K 1 ∪ K 2 where K 1 , K 2 are the full-dimensional unimodular simplicial cones generated by the two bases for the lattice

L = Z 3 given by {u 1 , u 2 , u 4 }, {u 1 , u 3 , u 4 } respectively. Their intersection K 1 ∩ K 2 is the 2-dimensional simplicial cone generated by {u 1 , u 4 }.
Therefore, applying properties (vi) and then (v) from Proposition 2.1, one can compute s(K; x)

(vi) = s(K 1 ; x) + s(K 2 ; x) (v) = 1 x 1 (x 1 + x 2 )(x 1 + x 2 + x 3 ) + 1 x 1 (x 1 + x 3 )(x 1 + x 2 + x 3 ) = 2x 1 + x 2 + x 3 x 1 (x 1 + x 2 )(x 1 + x 3 )(x 1 + x 2 + x 3 )
.

Alternatively, one could first compute H(K, X) via Proposition 2.2 (vi) and (v):

(2.4)

H(K; X) (vi) = H(K 1 ; X) + H(K 2 ; X) -H(K 1 ∩ K 2 ; X) (v) = 1 (1 -X 1 )(1 -X 1 X 2 )(1 -X 1 X 2 X 3 ) + 1 (1 -X 1 )(1 -X 1 X 3 )(1 -X 1 X 2 X 3 ) - 1 (1 -X 1 )(1 -X 1 X 2 X 3 ) = 1 -X 2 1 X 2 X 3 (1 -X 1 )(1 -X 1 X 2 )(1 -X 1 X 3 )(1 -X 1 X 2 X 3 )
.

Then one could recover s(K; x) by first making the exponential substitution (2.1), then expanding the analytic part H(K; X) as a power series in x, and using this to extract the homogeneous component H -3 (x) of degree -3 = -n:

H(K; X) = 1 -e 2x1+x2+x3 (1 -e x1 )(1 -e x1+x2 )(1 -e x1+x3 )(1 -e x1+x2+x3 ) = 1 x 1 (x 1 + x 2 )(x 1 + x 3 )(x 1 + x 2 + x 3 ) • 1 -e 2x1+x2+x3 x 1 1 -e x1 x 1 + x 2 1 -e x1+x2 x 1 + x 3 1 -e x1+x3 x 1 + x 2 + x 3 1 -e x1+x2+x3 = -(2x 1 + x 2 + x 3 ) + (terms of degree at least 2) x 1 (x 1 + x 2 )(x 1 + x 3 )(x 1 + x 2 + x 3 ) • (1 + o(x 1 )) (1 + o(x 1 + x 2 )) (1 + o(x 1 + x 3 )) (1 + o(x 1 + x 2 + x 3 )) = (-1) 3 2x 1 + x 2 + x 3 x 1 (x 1 + x 2 )(x 1 + x 3 )(x 1 + x 2 + x 3 ) s(K;x) + (terms of degree at least -2)
in agreement with our previous computation.

Alternatively, one can obtain H(K; X) and s(K; x) from Proposition 2.5, since we claim that R = k[K ∩ L] has this complete intersection presentation:

R ∼ = S/I = k[U 1 , U 2 , U 3 , U 4 ]/(U 1 U 4 -U 2 U 3 ).
To see this, start by observing that the map

S = k[U 1 , U 2 , U 3 , U 4 ] ϕ -→ R U i -→ e ui
is surjective, since K was covered by the two unimodular cones K 1 and K 2 . Note that there is a unique (up to scaling) linear dependence (2.5)

u 1 + u 4 = u 2 + u 3 (= 2e 1 + e 2 + e 3 )
among {u 1 , u 2 , u 3 , u 4 }. Hence I = ker ϕ contains the principal ideal (U 1 U 4 -U 2 U 3 ). Furthermore, Proposition 2.4 implies that I is generated by binomials of the form U α -U β where

4 i=1 α i u i = 4 j=1 β j u j .
Due to the uniqueness of the dependence (2.5), one must have

α 1 = α 4 = β 2 = β 3 > 0 and α 2 = α 3 = β 1 = β 4 = 0. Thus U α -U β = (U 1 U 4 ) α1 -(U 2 U 3 ) α1 , which lies in the ideal (U 1 U 4 -U 2 U 3 ). Thus I = ker ϕ = (U 1 U 4 -U 2 U 3 ).
3. Identifying Ψ P and Φ P Recall from the introduction that for a poset P on {1, 2, . . . , n} we wish to associate two polyhedral cones. The first is

K wt P := {x ∈ R n + :
x i ≥ x j for i < P j} inside the vector space R n with standard basis e 1 , . . . , e n spanning the appropriate lattice L wt = Z n . The second is

K root P = R + {e i -e j : i < P j} inside the codimension one subspace V root ∼ = R n-1 of R n where the sum of coor- dinates x 1 + • • • + x n = 0.
We consider this subspace to have Lebesgue measure normalized to make the basis {e 1e 2 , e 2e 3 , . . . , e n-1e n } for the appropriate lattice L root ∼ = Z n-1 span a parallelepiped of volume 1. Proposition 3.1. For any poset P on {1, 2, . . . , n}, one has

Ψ P (x) := w∈L(P ) w 1 (x1-x2)(x2-x3)•••(xn-1-xn) = s(K root P ; x) Φ P (x) := w∈L(P ) w 1 x1(x1+x2)(x1+x2+x3)•••(x1+•••+xn) = s(K wt P ; x) Proof. (cf.
+ • • • + e w(n) ).
Thus Proposition 2.1(v) gives the desired equalities in this case.

In the inductive step, if i, j are incomparable in P then either order relation i < j or the reverse j < i may be added to P (followed by taking the transitive closure), to obtain two posets P i<j , P j<i . Note that

L(P ) = L(P i<j ) ⊔ L(P j<i ) and hence (3.1) Ψ P (x) = Ψ Pi<j (x) + Ψ Pj<i (x), Φ P (x) = Φ Pi<j (x) + Φ Pj<i (x).
It only remains to show that s(K root P ; x) and s(K wt P ; x) satisfy this same recurrence. If one introduces into the binary relation P both relations i ≤ j and j ≤ i before taking the transitive closure, then one obtains a quasiorder or preorder that we denote P i=j . It is natural to also introduce the (non-full-dimensional) cone K wt Pi=j lying inside the hyperplane where x i = x j , and the (non-pointed) cone K root Pi=j containing the line R(e ie j ). One then has these decompositions

K wt P = K wt Pi<j ∪ K wt Pj<i with K wt Pi<j ∩ K wt Pj<i = K wt Pi=j , K root Pi=j = K root Pi<j ∪ K root Pj<i with K root Pi<j ∩ K root Pj<i = K root P
leading to these relations among characteristic functions of cones:

(3.2) χ K wt P + χ K wt P i=j = χ K wt P i<j + χ K wt P j<i , χ K root P + χ K root P i=j = χ K root P i<j + χ K root P j<i
.

From this one concludes using Proposition 2.1(vi) that

s(K wt P ; x) = s(K wt Pi<j ; x) + s(K wt Pj<i ; x), s(K root P ; x) = s(K root Pi<j ; x) + s(K root Pj<i ; x) since Proposition 2.1(i) implies s(K wt Pi=j ; x) = s(K root Pi=j ; x) = 0.
Comparing with (3.1), the result follows by induction.

Remark 3.2. The parallel between the relations in (3.2) is not a coincidence. It reflects a general duality [2, Corollary 2.8] relating identities among characteristic functions of cones K i and their polar dual cones K * i :

(3.3) i c i χ Ki = 0 if and only if i c i χ K * i = 0.
While it is not true that the cones K wt P and K root P are polar dual to each other, this is almost true, as we now explain.

The dual space to the hyperplane x 1 + • • • + x n = 0, which is the ambient space for K root P is the quotient space R n /ℓ where ℓ is the line R(e

1 + • • • + e n ).
Thus identities among characteristic functions of cones K root P give rise via (3.3), to identities among the characteristic functions of their dual cones (K root P ) * inside this quotient space. The cone K wt P maps via the quotient mapping R n → R n /ℓ to the dual cone (K root P ) * . Moreover, one can check that the intersection K wt P ∩ ℓ is exactly the half-line/ray

ℓ + := R + (e 1 + • • • + e n ).
Therefore, identities among characteristic functions of the cones (K root P ) * "lift" to the same identity among characteristic functions of the cones K wt P . We are still lying slightly here, since just as in (3.2), one must not only consider the cones K wt P , K root P for posets on {1, 2, . . . , n}, but also for preposets. See [22, §3.3] for more on this preposet-cone dictionary for the cones K wt P . We remark also that this duality is the source of our terminology K root , K wt for these cones, as the hyperplane x 1 + • • • + x n = 0 is the ambient space for the root lattice of type A n-1 , while the dual space R n /ℓ is the ambient space for its dual lattice, the weight lattice of type A n-1 .

Application: skew diagram posets and Theorem B

Recall from the introduction that to a skew (Ferrers) diagrams D = λ/µ, thought of as a collection of points (i, j) in the plane occupying rows 1, 2, . . . , r numbered top to bottom, and columns 1, 2, . . . , c numbered right to left, we associate a bipartite poset P D on the set {x 1 , . . . , x r , y 1 , . . . , y c } having an order relation x i < PD y j whenever (i, j) is a point of D.

We wish to prove Theorem B from the introduction, evaluating Ψ PD (x) for every skew diagram D. Without loss of generality, we will assume for the remainder of this section that the skew diagram D is connected in the sense that its poset P D is connected; otherwise both sides of Theorem B vanish (for the left side, via Corollary 5.2, and for the right side because the sum is empty).

We exhibit a known triangulation for the cone K root PD . The cone K root PD lives in the codimension one subspace V root of the product space R r+c = R r × R c with standard basis vectors e 1 , . . . , e r and f 1 , . . . , f c , and dual coordinates x 1 , . . . , x r and y 1 , . . . , y c . Here K root PD is the nonnegative span of the vectors {e if j : (i, j) ∈ D}. Note that each of these vectors lies in the following affine hyperplane H of V root : (4.1)

H := {(x, y) ∈ R r × R c : x 1 + • • • + x r = 1 and y 1 + • • • + y c = -1}.
Thus it suffices to triangulate the polytope P D , which is the convex hull of these vectors inside this affine hyperplane H.

Consider the skew diagram D as the componentwise partial order on its elements (i, j). One finds that D is a distributive lattice, in which the meet ∧ and join ∨ of two elements (i, j), (i ′ , j ′ ) are their componentwise minimums and maximums:

(i, j) ∧ (i ′ , j ′ ) = (min(i, i ′ ), min(j, j ′ )) (i, j) ∨ (i ′ , j ′ ) = (max(i, i ′ ), max(j, j ′ )).
Consequently, by Birkhoff's Theorem on the structure of finite distributive lattices [START_REF] Stanley | Enumerative Combinatorics[END_REF]Theorem 3.4.1], the lattice D is isomorphic to the lattice of order ideals for the subposet Irr(D) of join-irreducible elements of D.

For any finite poset Q, Stanley [START_REF] Stanley | Two poset polytopes[END_REF] considered a convex polytope called the order polytope of O(Q), which one can think of as the convex hull within R Q of the characteristic vectors of order ideals of Q; see [START_REF] Stanley | Two poset polytopes[END_REF]Corollary 1.3].

Proposition 4.1. The convex hull P D of the vectors {e i -f j : (i, j) ∈ D} is affinely isomorphic to the order polytope O(Irr(D)) for the poset Irr(D).

Proof. Identify the join-irreducibles (i, j) in Irr(D) with basis vectors

ǫ 1 , . . . , ǫ r-1 , φ 1 , . . . , φ c-1 in R r-1 × R c-1 as follows: • if (i, j) covers (i -1, j), identify (i, j) with ǫ i-1 , • if (i, j) covers (i, j -1), identify (i, j) with φ j-1 .
One can then check that a general element (i, j) of D corresponds to an order ideal in Irr(D) whose elements are identified with {ǫ 1 , . . . , ǫ i-1 , φ 1 , . . . , φ j-1 }. Thus the order polytope O(Irr(D)) is simply the convex hull of vectors

{ǫ 1 + • • • + ǫ i-1 + φ 1 + • • • + φ j-1 : (i, j) ∈ D}.
The linear morphism

ψ : R r × R c -→ R r-1 × R c-1 e i -→ ǫ 1 + • • • + ǫ i-1 f j -→ φ 1 + • • • + φ j-1
restricts to an affine isomorphism H → R r-1 × R c-1 sending e if j to

ǫ 1 + • • • + ǫ i-1 + φ 1 + • • • + φ j-1 .
Therefore, ψ restricts further to an isomorphism between P D and O(Irr(D)).

Corollary 4.2. For any skew diagram D, the cone K root PD has a triangulation into unimodular cones K π indexed by lattice paths π from (1, 1) to (r, c). Furthermore, the extreme rays of K π are spanned by the vectors {e if j } (i,j)∈π .

Consequently, as asserted in Theorem B, one has

Ψ PD (x) = π 1 (i,j)∈π (x i -y j ) = π (i,j)∈D\π (x i -y j ) (i,j)∈D (x i -y j )
.

In particular, when D is the Ferrers diagram D of a partition λ, one has

Ψ PD (x) = S ŵ (x, y) S w (x, y)
where S w (x, y), S ŵ (x, y) are the double Schubert polynomials for the dominant permutation w having Lehmer code λ = (λ 1 , . . . , λ r ), and the vexillary permutation ŵ having Lehmer code λ := (0, λ 2 -1, . . . , λ r -1).

Proof. Stanley [24, §5] describes a triangulation of the order polytope O(Q) whose maximal simplices correspond to linear extensions π of Q, or to maximal chains π in the distributive lattice of order ideals J(Q). For Q = Irr(D), so that J(Q) = D, these linear extensions π correspond to lattice paths from (1, 1) to (r, c) in the diagram D. Here the vertices spanning the maximal simplex in the triangulation corresponding to π are the characteristic vectors of the order ideals on the chain π.

Thus one obtains a corresponding triangulation for the polytope, which is the intersection of K root PD with the affine hyperplane in (4.1), in which the vertices of the maximal simplex corresponding to π are {e if j : (i, j) ∈ π}. Looking instead at the positive cone K π := {e if j : (i, j) ∈ π} spanned by these vectors therefore gives a triangulation of the cone K root PD . The cones K π are unimodular: one can easily check, via induction on r + c, that for any lattice path π from (1, 1) to (r, c), the Z-linear span of the vectors {e if j } (i,j)∈π contains all vectors of the form

e i -e j for 1 ≤ i = j ≤ r, f i -f j for 1 ≤ i = j ≤ c, e i -f j for 1 ≤ i ≤ r and 1 ≤ j ≤ c.
Therefore by Proposition 3.1 and Proposition 2.1(vi), one has

Ψ PD = s(K root PD ; x) = π s(K π ; x) = π 1 (i,j)∈π (x i -y j ) = π (i,j)∈D\π (x i -y j ) (i,j)∈D (x i -y j )
.

When D is the Ferrers diagram of a partition λ, this denominator product (i,j)∈D (x iy j ) is the double Schubert polynomial S w (x, y) for the dominant permutation w that has Lehmer code λ; see, e.g., [18, §9.4], [19, eqn. (6.14)], or one can argue similarly to the argument for the numerator sum given in the next paragraph.

There are various ways to identify the numerator sum π (i,j)∈D\π (x iy j ) as S ŵ(x, y). One way is to check that each lattice path π in D gives rise as follows to a reduced pipe dream for ŵ in the terminology of Knutson and Miller [21,§16.1]: the +'s occur with the (row,column) indices (i, j) given by the lattice points not visited by π. Thus the numerator sum is the expansion of S ŵ(x, y) as a sum over reduced pipe dreams for ŵ; see Fomin

D = (4, 4, 2)/(1, 1, 0) = • • • • • • • • • •
whose rows and columns we index as follows.

y 4 y 3 y 2 y 1 x 1 • (1, 3) (1, 2) (1, 1) x 2 • (2, 3) (2, 2) (2, 1) x 3 (3, 4) (3, 3)
Thinking of D as a distributive lattice via the componentwise order on the labels (i, j), one can label its 5 join-irreducibles Irr(D) by the basis vectors ǫ 1 , ǫ 2 , ǫ 3 , φ 1 , φ 2 as in the above proof.

•

ǫ 2 ǫ 1 • • • • φ 1 ǫ 3 φ 2
The poset Q of join-irreducible elements of D has the following Hasse diagram.

ǫ 3 ǫ 2 ǫ 1 φ 2 φ 1
In this way, the elements of D correspond to the order ideals of Q and to the vertices of the order polytope O(Irr(D)) as follows.

• ǫ1+ǫ2 ǫ1 0 • ǫ1+ǫ2 +φ1 ǫ1 +φ1 φ1 ǫ1+ǫ2+ǫ3 +φ1+φ2 ǫ1+ǫ2 +φ1+φ2
There are three paths π from (1, 1) to (r, c) = (4, 3), giving rise to the three terms in Ψ PD (x):

• (1, 3) (1, 2) (1, 1) • (2, 3) (3, 4) (3, 3) 1 (x1-y1)(x1-y2)(x1-y3)(x2-y3)(x3-y3)(x3-y4) • • (1, 2) (1, 1) • (2, 3) (2, 2) (3, 4) (3, 3) + 1 (x1-y1)(x1-y2)(x2-y2)(x2-y3)(x3-y3)(x3-y4) • • • (1, 1) • (2, 3) (2, 2) (2, 1) (3, 4) (3, 3) + 1 (x1-y1)(x2-y1)(x2-y2)(x2-y3)(x3-y3)(x3-y4)

Extreme rays and Theorem C

Our goal here is to identify the extreme rays of the cones K wt P , K root P . Once achieved, this gives the denominators of Ψ P (x), Φ P (x), allows one to decide when the cones are simplicial, leading to Theorem C.

Recall that an order ideal of a poset P is a subset J of its elements such that, for any pair i, j of comparable elements (i ≤ P j), if j ∈ J then i ∈ J. for the connected nonempty order ideals J in P .

Proof. For (i), note K root P is the cone nonnegatively spanned by {e ie j : i < P j}, and since i < P j < P k implies e ie k = (e ie j ) + (e je k ) ∈ R + {e ie j , e j -k}, its extreme rays must be spanned by some subset of {e ie j : i ⋖ P j}. On the other hand, for each covering relation i ⋖ P j, one can exhibit a linear functional f that vanishes on e ie j and is strictly negative on the rest of the vectors spanning K root P as follows. Choose a linear extension w = (w(1), . . . , w(n)) in L(P ) such that i, j appear adjacent in the linear order, say w(k) = i and w(k + 1) = j and define the functional f : R n → R by the values

f (e w(m) ) = m for m = 1, 2, . . . , k -1; f (e w(k) ) = f (e i ) = k = f (e j ) = f (e w(k+1) ); f (e w(m) ) = m -1 for m = k + 2, k + 3, . . . , n.
For (ii), note that K wt P is described by the system of inequalities

x i ≥ 0 for all i; x i ≥ x j for i < P j.

We first claim that K wt P is the nonnegative span of characteristic vectors e J for order ideals J of P : if x = (x 1 , . . . , x n ) lies in K wt P , and its coordinates x i take on the distinct positive values c 1 < c 2 < • • • < c t then (setting c 0 := 0), one has

x = t r=1 (c r -c r-1 )e Jr
where J r is the order ideal of P defined by J r := {j ∈ {1, 2, . . . , n} : x j ≥ c r }.

Furthermore, if an order ideal J of P decomposes into connected components as J = ⊔ i J (i) , then each J (i) is itself a (connected) order ideal, and e J = i e J (i) .

Therefore the extreme rays of the cone must be spanned by some subset of the vectors e J for connected order ideals J. On the other hand, for any connected order ideal J, one can exhibit the line Re J spanned by e J as the intersection of n -1 linearly independent hyperplanes that come from inequalities valid on K wt P as follows. Consider the Hasse diagram for J as a connected graph, and pick a spanning tree T among its edges. Then the line Re J is the set of solutions to the system x i = 0 for i / ∈ J; x i = x j for i ⋖ P j or i ⋗ P j with {i, j} ∈ T. Proposition 2.1 then immediately implies the following.

Corollary 5.2. Let P be a poset on {1, 2, . . . , n}.

(i) If P is disconnected, then the cone K root P is not full-dimensional, and Ψ P (x) = 0. If P is connected, the cone K root P is full-dimensional, and the smallest denominator for Ψ P (x) is i⋖P j (x ix j ). (ii) The cone K wt P is always full-dimensional, and the smallest denominator for Φ P (x) is J j∈J x j where the product runs over all connected order ideals J in P .

Theorem C is now simply a consequence of the analysis of the simplicial cases.

Corollary 5.3. The cone K root P is simplicial if and only if the Hasse diagram for P contains no cycles. In this case it is also unimodular. Hence the Hasse diagram for P is a spanning tree on {1, 2, . . . , n}, if and only if

Ψ P (x) = 1 i⋖P j (x i -x j )
.

The cone K wt P is simplicial if and only if P is a forest in the sense that every element is covered by at most one other element. In this case it is also unimodular. Hence P is a forest if and only if

Φ P (x) = 1 n i=1 j≤P i x j .
Proof. According to Proposition 5.1, the extreme rays of the cone K root P are the vectors {e ie j : i ⋖ P j}, which are linearly independent if and only if there are no cycles in the Hasse diagram for P . Furthermore, when there are no such cycles, an easy leaf induction shows that the cone is unimodular. The rest of the assertions follow.

To analyze K wt P , first note that when P is a forest, the connected order ideals of P are exactly the principal order ideals P ≤i := {j : j ≤ P i} for i = 1, 2, . . . , n. Not only are their characteristic vectors e P ≤i linearly independent, but if one orders the labels i according to any linear extension of P , one finds that these vectors e P ≤i form the columns of a unitriangular matrix, which is therefore unimodular.

When P is not a forest, it remains to show that the cone K wt P cannot be simplicial. There must exist two elements i, j incomparable in P whose principal order ideals have nonempty intersection P ≤i ∩ P ≤j . Decompose P ≤i ∩ P ≤j = ⊔ t ℓ=1 J (ℓ) into its connected components J (ℓ) . Then each of these components J (ℓ) will be a nonempty connected ideal, as will be P ≤i , P ≤j and their union P ≤i ∪ P ≤j . This leads to the following linear relation:

e P ≤i + e P ≤j = e P ≤i ∪P ≤j + t i=1 e J (ℓ) .
Since Proposition 5.1 implies the vectors involved in this relation all span extreme rays of the cone K wt P , the cone is not simplicial in this case. An interesting special case of the preceding result leads to a special role played by dominant or 132-avoiding permutations when considering posets of order dimension two, that is, the subposets of the componentwise order on R 2 . Björner and Wachs [5, Theorems 6.8, 6.9] showed that P has order dimension two if and only if one can relabel the elements i in [n] so that L(P ) forms a principal order ideal [e, w] in the weak Bruhat order on S n . Corollary 5.4. When L(P ) = [e, w] for some permutation w, the cone K wt P is simplicial if and only if w is 132-avoiding.

Proof. When L(P ) = [e, w], one can check that P has the following order relations: i < P j exactly when i < Z j and (i, j) are noninversion values for w, that is, w -1 (i) < w -1 (j), or i appears earlier than j in the list notation (w(1), . . . , w(n)).

By Corollary 5.3, the cone P is not simplicial if and only if P is not a forest, that is, if and only if there exist i, j which are incomparable in P and have a common lower bound h < P i, j. Hence by the previous paragraph, one must have h < Z i and h < Z j, with h appearing earlier than both i, j in the list notation for w. Without loss of generality i < Z j by reindexing, and then the incomparability of i, j in P forces j to appear earlier than i in the list notation. That is h < Z i < Z j occur in the order (h, j, i) within w, forming an occurrence of the pattern (1, 3, 2).

; x) = 2x 1 + x 2 + x 3 x 1 (x 1 + x 2 )(x 1 + x 3 )(x 1 + x 2 + x 3 ) .
6. P -partitions, forests, and the Hilbert series for K wt

P

We digress here to discuss the Hilbert series for the affine semigroup K ∩ L for the cone K = K wt P inside the lattice L = L wt . Analyzing this when P is a forest leads to a common generalization of both Theorem C and the "maj" hook formula for forests of Björner and Wachs. One can think of as K ∩ L as the semigroup of weak P -partitions in the sense of Stanley [23,§4.5], namely functions f : P → N which are order-reversing: f (i) ≥ f (j) for i < P j. Within this semigroup K ∩L, Stanley also considers the semigroup ideal A(P ) of P -partitions (in the strong sense), that is, those order-reversing functions f : P → N which in addition satisfy the strict inequality f (i) > f (j) whenever (i, j) is in the descent set Des(P ) := {(i, j) : i ⋖ P j and i > Z j}.

The main lemma of P -partition theory [START_REF] Stanley | Enumerative Combinatorics[END_REF]Theorem 7.19.4] asserts the disjoint decomposition2

A(P ) = w∈L(P ) A(w).
Equivalently, in terms of the Hilbert series of the semigroup ideal A(P ) defined by

H(A(P ); X) := f ∈A(P ) X f where X f := n i=1 X f (i) i
, this says that (6.1) H(A(P ); X) = w∈L(P )

H(A(P w ), X).
This simple equation is more powerful than it looks at first glance. Define the notation X A := j∈A X j for subsets A ⊂ {1, 2, . . . , n}.

Proposition 6.1. For any forest poset P on {1, 2, . . . , n}, one has (6.2) H(A(P ); X) = (i,j)∈Des(P ) X P ≤i n i=1 (1 -X P ≤i ) .

In particular, (6.1) becomes

(6.3) i∈Des(P ) X P ≤i n i=1 (1 -X P ≤i ) = w∈L(P )
i:wi>wi+1 X {w1,w2,...,wi} n i=1 (1 -X {w1,w2,...,wi} )

.

Proof. When P is a forest, we claim that A(P ) is actually a principal ideal within K ∩ L, generated by the P -partition f 0 for which f 0 (i) is the number of descent edges encountered along the unique path in the Hasse diagram from i to a maximal element of P . Alternatively f 0 is the sum of characteristic functions of the subtrees P ≤i for which one has (i, j) in Des(P ) (here j is the unique element covering i in P ). In other words, A(P ) = f 0 + K ∩ L, and consequently,

H(A(P ); X) = X f0 • H(K; X) =   (i,j)∈Des(P ) X P ≤i   • H(K; X).
But then Corollary 5.3 implies that K ∩ L is a unimodular cone having extreme rays spanned by the characteristic vectors of the subtrees P ≤i , and hence

(6.4) H(K; X) = n i=1
(1 -X P ≤i ).

The rest follows from the observation that when one considers a permutation w as a linearly ordered poset P w having w(1) < Pw • • • < Pw w(n), it is an example of a forest, in which P ≤i = {w(1), w(2), . . . , w(i)}.

This has two interesting corollaries. The first is that by applying the total residue operator discussed in Section 2.4 to (6.4), one obtains a second derivation of Theorem C.

The second is that by setting X j = q for all j in equation ( 6.3), one immediately deduces the major index q-hook formula for forests of Björner and Wachs [5, Theorem 1.2]: Corollary 6.2. When P is a forest, w∈L(P ) q maj(w) = q maj(P )

[n]! q n i=1 [h(i)] q where maj(P ) := (i,j)∈Des(P )

|P ≤i |, h(i) := |P ≤i |, [n] q := 1 -q n 1 -q = 1 + q + q 2 + • • • + q n-1 , [n]! q := [n] q [n -1] q • • • [2] q [1] q .

Generators for the affine semigroups

The two families of cones K root P , K wt P share a pleasant property: the generating sets for their affine semigroups are as small as possible. This will be used in Section 8.

Proposition 7.1. For P any poset on {1, 2, . . . , n}, both cones K = K root P , K wt P , and the appropriate lattices L = L root , L wt have the affine semigroup K ∩ L generated by the primitive lattice vectors (the vectors nearest the origin) lying on the extreme rays of K.

Proof. It suffices to produce a triangulation of K into unimodular cones, each of whose extreme rays is a subset of these extreme rays of K.

For K root P , this essentially follows from the fact that the root system of type A n-1 is totally unimodular-every simplicial cone generated by a subset of roots e ie j is a unimodular cone. Thus one can pick such a triangulation of K root P into simplicial subcones K introducing no new extreme rays arbitrarily, as in [START_REF] Stanley | Enumerative Combinatorics[END_REF]Lemma 4.6.1].

For K wt P , one must be more careful in producing a triangulation of K wt P into unimodular cones introducing no new extreme rays 3 . Proceed as in the proof of Proposition 3.1 via induction on the number |L(P )| of linear extensions, but using 3 It is not clear, a priori, that every simplicial cone spanned by a subset of the extreme rays of K wt P is unimodular, e.g. consider the cone spanned by these three rays: e 1 + e 2 , e 1 + e 3 , e 2 + e 3 .

as base cases the situation where P is a forest, so that K wt P is a unimodular cone by Corollary 5.3.

In this inductive step, assuming P is not a forest, there exist two elements i, j which are incomparable in P with a common lower bound h < P i, j. As in the proof of Proposition 3.1, one has

L(P ) = L(P i<j ) ⊔ L(P j<i )
and hence a decomposition (7.1)

K L(P ) = K L(Pi<j) ∪ K L(Pj<i) .
Note that induction applies to both P i<j and P j>i since they have fewer linear extensions. By the symmetry between i and j, it only remains to show that the extreme rays of K L(Pi<j ) are a subset of those for K L(P ) , or equivalently, that any subset J ⊆ [n] which induces a connected order ideal of P i<j will also induce a connected order ideal of P . First note that J will also be an order ideal in P , since P has fewer order relations than P i<j . Given any two elements a, b in J, there will be a path (7.2) a = a 0 , a 1 , . . . , a m = b in J where each pair a ℓ , a ℓ+1 are comparable in P i<j . If any pair a ℓ , a ℓ+1 are incomparable in P , this means either a ℓ ≤ i and j ≤ a ℓ+1 , or the same holds swapping the indices ℓ, ℓ + 1. In either case, j must also lie in the ideal J of P i<j , and hence h and i lie in J too. Thus one can replace the single step (a ℓ , a ℓ+1 ) in the path (7.2) with the longer sequence (a ℓ , i, h, j, a ℓ+1 ) of steps, or the same swapping the indices ℓ, ℓ + 1.

Analysis of the semigroup for K root

P

In the following subsections, we focus on the cone K = K root P with lattice L = L root , and attempt to analyze the structure of the affine semigroup K ∩ L, and its semigroup ring R = k[K ∩ L] over a field k. Ultimately this leads to Corollary 8.10, giving a complete intersection presentation for R when the poset P is strongly planar, lifting Greene's Theorem A from the introduction to a statement about affine semigroup structure.

Generating the toric ideal. The affine semigroup

R = k[K ∩ L] is naturally a subalgebra of a Laurent polynomial algebra R = k[t i t -1 j ] i<P j ⊂ k[t 1 , t -1 1 , . . . , t n , t -1 n ].
On the other hand, recall from Proposition 7.1 that the affine semigroup K ∩ L is generated by the primitive vectors {e ie j : i ⋖ P j} on its extreme rays. Therefore one can present R as a quotient via the surjection

S := k[U ij ] i⋖P j -→ R U ij -→ t i t -1 j .
Defining as in Section 2.5 the toric ideal I := ker(S → R), one has R ∼ = S/I.

It therefore helps to know generators for I in analyzing R, and trying to compute its Hilbert series. As in Proposition 2.4, I is always generated by certain binomials. However, there is a smaller generating set of binomials available in this situation.

Say that a set of edges C in the (undirected) Hasse diagram for P form a circuit 4 if they can be directed to form a cycle, and they are minimal with respect to inclusion having this property. Having fixed a circuit C, and having fixed one of the two ways to orient C as a directed cycle, say that an edge {i, j} of C having i ⋖ P j goes with C if {i, j} is directed toward j in C, and goes against C otherwise. Define two monomials W (C) :=

i⋖P j with C U ij A(C) := i⋖P j against C U ij
and define the circuit binomial

U (C) := W (C) -A(C).
i⋖P j U aij ij - i⋖P j U bij ij
where a ij , b ij are nonnegative integers such that

i⋖P j a ij (e i -e j ) = i⋖P j b ij (e j -e i )
or equivalently i⋖P j a ij (e ie j )b ij (e je i ) = 0.

In looking for a smaller set of generators for I, note that one may assume that if a ij = 0 then b ij = 0, else one could cancel factors of U ij from the binomial in (8.1). This means that the nonnegative integers a ij , b i,j can be thought of as the multiplicities on a collection C of directed arcs that either go up or down along edges in P , with the C-indegree equalling the C-outdegree at every vertex. Thus C can be decomposed into collections supported on various circuits C 1 , . . . , C t of edges (allowing multiplicity among the C i ). One then finds that the binomial (8.1) lies in the ideal generated by the circuit binomials {U (C i )} t i=1 using the following calculation and induction on t:

i⋖P j U aij ij - i⋖P j U bij ij = t i=1 W (C i ) - t i=1 A(C i ) = (W (C 1 ) -A(C 1 )) U(C1) t i=2 W (C i ) + A(C 1 ) t i=2 W (C i ) - t i=2 A(C i ) .
For example, using this (together with Proposition 2.5) allows one to immediately compute H(K root P ; X) and Ψ P (x) = s(K root P ; x) in the case where the Hasse diagram of P has only one circuit, as done for Ψ P by other means in [START_REF] Boussicault | Operations on Posets and Rational Identities of Type A[END_REF] and [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF]. Then the complete intersection presentation

R = k[K ∩ L] ∼ = S/(U (C)) implies H(K P ; X) =   1 - i∈min(C) X i • j∈max(C) X -1 j   1 i⋖P j (1 -X i X -1 j ) Ψ P (x) =   i∈min(C) x i - j∈max(C) x j   1 i⋖P j (x i -x j )
, assuming P is connected for the latter formula. First we recall the notion of biconnected components in an undirected graph G = (V, E). Say that two edges are circuit-equivalent if there is a circuit C of edges that passes through both. Consider the equivalence classes E i of the transitive closure of this relation 5 . If V i is the set of vertices which are at least the extremity of one edge in E i let the biconnected components of G be the subgraphs G i = (V i , E i ) Corollary 8.3. If the Hasse diagram for P has biconnected components P 1 , . . . , P t (regarding each as the Hasse diagram for a poset P ℓ ), then one can express the semigroup ring R P for P as a tensor product of graded k-algebras:

R P ∼ = R P1 ⊗ k • • • ⊗ k R Pt
and therefore

H(K root P ; X) = t ℓ=1
H(K P ℓ ; X);

Ψ P (x) = t ℓ=1 Ψ P ℓ (x).
Proof. Express R P as S/I. Since every edge of the Hasse diagram lies in a unique biconnected component P i (1 ≤ i ≤ t), one has S ∼ = ⊗ t ℓ=1 S P ℓ with S P ℓ := k[U ij ] i⋖P ℓ j . Since each circuit C is supported on a set of edges that lies within a single biconnected component P ℓ , Proposition 8.1 implies I = t ℓ=1 I P ℓ where I P ℓ is the toric ideal ker(S P ℓ → R P ℓ The first assertion follows, and the remaining assertions follow from the first.

Remark 8.4. The argument above works in a more general context. Namely, if the ambient vector space V , lattice L, and cone K have compatible direct sum decompositions

V = V 1 ⊕ • • • ⊕ V ℓ , L = L 1 ⊕ • • • ⊕ L ℓ , K = K 1 ⊕ • • • ⊕ K ℓ , then the semigroup ring R := k[K ∩ L] has a tensor product decomposition R ∼ = R 1 ⊗ k • • • ⊗ k R ℓ , where R i = k[K i ∩ L i ] for i = 1, • • • , ℓ.
8.3. Notches and disconnecting chains. Note that Corollary 8.3 provides a somewhat trivial sufficient condition for Ψ P (x) to factor. Our goal here is a less trivial such condition on P , including a ring-theoretic explanation of the factorization due to disconnecting chains from [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF]Theorem 7.1]. This is provided by the following operation which sometimes applies to the Hasse diagram for P . Definition 8.5. In a finite poset P , say that a triple of elements (a, b, c) forms a notch of ∨-shape (dually, a notch of ∧-shape) if a ⋖ P b, c (dually, a ⋗ P b, c), and in addition, b, c lie in different connected components of the poset P \ P ≤a (dually, P \ P ≥a ).

When (a, b, c) forms a notch of either shape in a poset P , say that the quotient poset P := P/{b ≡ c}, having one fewer element and one fewer Hasse diagam edge, is obtained from P by closing the notch, and that P is obtained from P by opening a notch.

It should be noted that when (a, b, c) forms a ∨-shaped notch, the two elements b, c have no common upper bounds in P . This eliminates several pathologies which could occur in the formation of the quotient poset P = P/{b ≡ c}; e.g., double edges other than the edge {a, b}, {a, c}, oriented cycles, creation of a new edge in the quotient that is the transitive closure of other edges.

For example, in Figure 1, the poset P 2 contains a notch of ∨-shape (3, 5, 5 ′ ), and the poset P 1 is obtained from P 2 by closing this notch.

We state the following result relating K root P , K root P in the case when the notch is ∨-shaped; the result for a ∧-shaped notch is analogous. Theorem 8.6. When P is obtained from P closing a ∨-shaped notch (a, b, c), the affine semigroup ring R P is obtained from the ring R P by modding out the nonzero divisor t a t -1 bt a t -1 c : (8.2)

R P ∼ = R P /(t a t -1 b -t a t -1 c ). In particular, H(K root P ; X) = (1 -X a X -1 b ) H(K root P ; X) X b =Xc Ψ P (x) = (x a -x b ) [Ψ P (x)] x b =xc
so that Ψ P (x) and [Ψ P (x)] x b =xc have exactly the same numerator polynomials when written over the denominator i⋖ P j (x ix j ), and a complete intersection presentation for R P leads to such a presentation for R P .

Example 8.7. Before delving into the proof, we illustrate how Theorem 8.6, together with some of the foregoing results, helps to analyze the ring R P , as well as the Hilbert series H(K root P ; X), and hence Ψ P (x).

Consider the posets shown in Figure 1. As mentioned earlier, P 1 is obtained from P 2 by closing the ∨-shaped notch 3 < 5, 5 ′ . In addition, P 2 is obtained from P 3 by closing the ∨-shaped notch 1 < 3, 3 ′ . Lastly, note that P 4 , P 5 are the two biconnected components of P 3 . In analyzing R P1 , therefore, one can start with P 4 , P 5 , which each have a unique circuit, and apply Corollary 8.2 to write down these simple (complete intersection) presentations:

R P4 ∼ = k[U 12 , U 25 , U 13 , U 35 ]/(U 12 U 25 -U 13 U 35 ) R P5 ∼ = k[U 13 ′ , U 16 , U 3 ′ 5 ′ , U 45 ′ , U 46 ]/(U 13 ′ U 3 ′ 5 ′ U 46 -U 16 U 45 ′ )
Applying Corollary 8.3 yields the following tensor product (complete intersection) presentation for R P3 :

R P3 ∼ = R P4 ⊗ R P5 ∼ = k[U 12 , U 25 , U 13 , U 35 , U 13 ′ , U 16 , U 3 ′ 5 ′ , U 45 ′ , U 46 ] /(U 12 U 25 -U 13 U 35 , U 13 ′ U 3 ′ 5 ′ U 46 -U 16 U 45 ′ ).
Applying Theorem 8.6 to close the notch at 1 < 3, 3 ′ yields the following complete intersection presentation for R P2 :

R P2 ∼ = k[U 12 , U 25 , U 13 , U 35 , U 16 , U 35 ′ , U 45 ′ , U 46 ] /(U 12 U 25 -U 13 U 35 , U 13 U 35 ′ U 46 -U 16 U 45 ′ ).
Applying Theorem 8.6 once more to close the notch at 3 < 5, 5 ′ yields the following complete intersection presentation for R P1 :

R P1 ∼ = k[U 12 , U 25 , U 13 , U 35 , U 16 , U 45 , U 46 ] /(U 12 U 25 -U 13 U 35 , U 13 U 35 U 46 -U 16 U 45 ).
Consequently, from Theorem 2.5, one has

H(K root P1 ; X) = (1 -X 1 X -1 5 )(1 -X 1 X 4 X -1 5 X -1 6 ) i⋖P 1 j (1 -X i X -1 j ) Ψ P1 (x) = (x 1 -x 5 )(x 1 + x 4 -x 5 -x 6 ) i⋖P 1 j (x i -x -1 j )
.

Proof of Theorem 8.6. Define S P := k[U ij ] i⋖P j , so that

R P := k[K root P ∩ L root ] ∼ = S P /I P
where I P is the kernel of the map S P → R P sending U ij to t i t -1 j . Define a map S P φ → R P sending most variables U ij to t i t -1 j , except that both U ab , U ac get sent to t a t -1 b . We wish to describe the ideal J := ker(S P → R P ), and in particular to show that (8.3)

J = I P + (U ab -U ac ).
This would imply (8.2): the map φ is surjective since it hits a set of generators for R P , and hence R P ∼ = S P /J = S P /(I P + (U ab -U ac )) ∼ = (S P /I P ) /( Ūab -Ūbc )

∼ = R P /(t a t -1 b -t a t -1 c
). To prove the equality of ideals asserted in (8.3), one checks that the two ideals are included in each other. The inclusion I P + (U ab -U ac ) ⊆ J is not hard: both U ab , U ac are sent by φ to t a t -1 b , so the binomial U ab -U ac is in the kernel J, and since circuits C in the directed graph P remain circuits in the quotient directed graph P , Proposition 8.1 implies the inclusion I P ⊆ J.

For the reverse inclusion J ⊆ I P +(U ab -U ac ), first note that one can re-interpret the ideal J: it is the toric ideal for the presentation of the semigroup R P in which the Hasse diagram edge a ⋖ P bc has been "doubled" into two parallel directed edges associated with the same monomial t a t -1 b , but hit by two variables U ab , U ac from S P . Denote by P + this directed graph obtained from the Hasse diagram for P by doubling this edge. The analysis from Proposition 8.1 then shows that J is generated by the circuit binomials U (C) as C runs through the circuits of P + .

It remains to show that for every circuit C in the directed graph P + , the circuit binomial U (C) lies in I P + (U ab -U ac ).

If this circuit C in P + does not pass through the collapsed vertex bc in P + , then C is also a circuit in P , and hence U (C) already lies in I P .

If this circuit C does pass through vertex bc, we distinguish two cases. Consider the partition of the set E bc = E b ⊔ E c of edges incident to bc in P + , where E b (resp. E c ) is the subset of edges whose preimage in P is incident to b (resp. c). If the two edges of C incident to bc lie in the same set of this partition, then, as before, C is also a circuit in P , and hence U (C) already lies in I P .

Consider now the last case where C does pass through vertex bc, but the two edges of C incident to bc lie respectively in E b and E c . Since b, c lie in different connected components of P \ P ≤a , the circuit C must pass through at least one vertex d ≤ P a. Use this to create two directed cycles C b , C c in P :

U (C) = U (C b ) • W (π dc ) + U (C c ) • A(π bd ) + (U ab -U ac ) • W (π dc ) • A(π bd ) • W (π da )
where for a path π of edges in the Hasse diagram one defines monomials

W (π) := i⋖P j: i→j appears in π U ij A(π) := i⋖P j: i←j appears in π U ij .
The relation (8.4) shows that U (C) lies in I P + (U ab -U ac ), as desired.

For the remaining assertions, note that since R P is a subalgebra of the Laurent polynomial ring, it is an integral domain, and therefore t a t -1 bt a t -1 c is a nonzero-divisor of R P . After identifying the grading variables

x b = x c , this element t a t -1 b -t a t -1 c becomes homogeneous of degree e a -e b .
Opening notches in a poset P provides a flexible way to understand some previously observed factorizations of the numerator of Ψ P (x), while at the same time giving information about the semigroup ring k[K root P ∩ L root P ] and its Hilbert series. where the last equality assumes that P is connected.

Proof. Use induction on the number of bounded regions ρ. In the base cases where there are no such regions or one such region, apply Corollary 5.3 or 8.2, respectively. In the inductive step, find a disconnecting chain for P that separates at least two bounded regions, as in [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF]Proposition 7.4]. Use Proposition 8.6 repeatedly to open notches down this chain, until the resulting poset has two biconnected components attached at one vertex of the chain, and apply Corollary 8.3, as in Example 8.9.

Reinterpreting the main transformation

Our goal in this final section is to reinterpret geometrically a very flexible identity that was used to deduce most of the results on Ψ P (x) in [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF], and called there the main transformation: Remark 9.2. In [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF], the identity (9.1) was used to prove some statements on Ψ by induction on the number of independent cycles (the cyclomatic number) in the Hasse diagram for P : terms indexed by non-empty subsets E correspond to posets P \ E with fewer independent cycles. In the base case for such inductive proofs, the Hasse diagram is acyclic, and possibly disconnected, so that either Ψ P (x) = 0, or Corollary 5.3 applies. Furthermore, in [9, section 6], it was shown how the choice of an embedding of the Hasse diagram of P onto a surface, together with a rooting at one of its half-edges, leads to a good a choice of circuits C in the induction. This expresses Ψ P (x) = i Ψ Pi (x) for various posets P i with tree Hasse diagrams that can be described explicitly in terms of the embedding and rooting. Using (9.3), one can show that this corresponds to an explicit triangulation for the cone K root P into subcones K root Pi , in which each subcone uses no new extreme rays. Unfortunately, iterating (9.2) does not in general lead to proofs for results on Φ P (x) via induction on cyclomatic number, as the base cases with no cycles correspond to cones K wt P which are not necessarily simplicial; see Corollary 5.3. Remark 9.3. Unlike equation (3.1), this identity (9.3) involves only pointed cones.

Our goal here is to point out how the geometric statement (9.3) generalizes to other families of cones and vectors. We begin with a geometric generalization of the notion of a circuit C in the Hasse diagram for P and its subset of upward edges W ⊂ C. Definition 9.4. Given two subsets of W, V of vectors in R d , say that W is cyclic6 with respect to V if there exists a positive linear combination of W lying in R + V , that is, w∈W a w w = v∈V b v v for some real numbers a w > 0, b v ≥ 0.

Example 9.5. Let C be one of the two possible orientations of a directed circuit in the Hasse diagram for a poset P . Let W ⊂ C be the edges of C which are directed upward in P . Then {e ie j : (i, j) ∈ W } is cyclic with respect to the set V := {e ie j : i ⋖ P j, (i, j) / ∈ W }, due to the relation i⋖P j: (i,j)∈W e ie j = i⋖P j: (j,i)∈C\W e ie j .

Bearing this example in mind, the following proposition gives the desired generalization of (9.1) and (9.3). Proposition 9.6. For subsets W, V of vectors in R d where W is cyclic with respect to V , one has the identity among characteristic vectors of cones The sum of (-1) |B| over these sets B vanishes, as predicted by the proposition. However, note that this does not hold for trivial reasons, e.g., these sets B do not form an interval in the boolean lattice.

Proof of Proposition 9.6. Up to a rescaling of the vectors in W , one can assume that u := w∈W w lies in R + V .

One must show that for every point p ∈ R d , one has These sets X p (w 0 ) are also convex polyhedral subsets, although possibly empty. The nerve of this covering of X p is the abstract simplicial complex consisting of all subsets A ⊂ W for which w0∈A X p (w 0 ) is nonempty. A standard nerve lemma (e.g., [START_REF] Björner | Topological methods[END_REF]Theorem 10.7]) implies that the geometric realization of this nerve is homotopy equivalent to the contractible space X p , and hence its (reduced) Euler characteristic A (-1) |A|-1 vanishes, where here the sum runs over subsets A with w0∈A X p (w 0 ) nonempty. Thus equation (9.4) will follow from this claim: Claim. The set w0∈A X p (w 0 ) is nonempty if and only if p lies in R + (V ∪ (W \ A)). For the "if" assertion of the claim, note that if p lies in R + (V ∪ (W \ A)), then any expression p =

( 1 -

 1 e x,ui ) • Hilb(K ∩ L; x) always lies in Z[L]. In fact, one has the following analogue of Proposition 2.1; see, e.g., [1, Proposition 4.4], [2, Theorem 3.1], [3, Proposition 7].

Proposition 2 . 4 .

 24 ( [21, Theorem 7.3], [25, Lemma 4.1] ) One can generate the toric ideal I = ker(S → R) by finitely many L-homogeneous elements chosen among the binomials U α -U β for which α, β ∈ N m and m i=1 α i u i = m j=1 β j u j .

Proposition 5 . 1 .

 51 Let P be a poset on {1, 2, . . . , n}. (i) The cone K root P has extreme rays spanned by {e ie j } i⋖P j . (ii) The cone K wt P has extreme rays spanned by the characteristic vectors e J := χ J = j∈J e j

Example 5 . 5 .

 55 Among the permutations w in S 3 , five out of the six are dominant or 132-avoiding; only w = (1, 3, 2) is not. It has [e, w] = L(P ) = {(1, 2, 3), (1, 3, 2)}, and K wt P is the non-simplicial cone considered in Example 2.6, having extreme rays spanned by {e 1 , e 1 + e 2 , e 1 + e 3 , e 1 + e 2 + e 3 }, and s(K

Proposition 8 . 1 .

 81 For any poset P on [n], the toric ideal I = ker(S → R) where S = k[U ij ] i⋖P j is generated by the circuit binomials {U (C)} as C runs through all circuits of the undirected Hasse diagram of P . Proof. Proposition 2.4 says I is generated by binomials of the form (8.1)

Corollary 8 . 2 .

 82 Let P be a poset whose Hasse diagram has only one circuit C. Considering the elements on C as a subposet, let max(C) and min(C) denote its maximal and minimal elements.

8. 2 .

 2 The biconnected component reduction. Since the ideal I = ker(S → R) is generated by the circuits within the undirected Hasse diagram for P , decomposing the Hasse diagram into its biconnected components provides a reduction in understanding the structure of R, which we explain next.

Figure 1 .

 1 Figure 1. Examples of opening and closing notches.

Figure 2 .

 2 Figure 2. An example of P, P , P + .

•

  C b follows b to d along the same path π bd chosen by C, then follows d to a along any saturated chain π da in P between them, and finally from a to b. • C c follows a to d reversing the same saturated chain π da , then follows d to c along the same path π dc chosen by C, and finally goes from c to a.One then has the following relation in S P(8.4)

Example 8 . 8 .

 88 One way to explain the factorization of the numerator of Ψ P (x) for the example from [9, Figure2], is to successively "open two notches", as shown

Theorem.([ 9 , 1 )

 91 Theorem 4.1]) Let C be one of the two possible orientations of a circuit in the Hasse diagram for a poset P . Let W ⊂ C be the edges of C which are directed upward in P . Then (9.1) E⊂W (-1) |E| Ψ P \E (x) = 0 where P \E is the poset whose Hasse diagram is obtained from that of P by removing the edges in E. Remark 9.1. In fact, (9.1) was deduced in [9, Theorem 4.1] from a geometric identity equivalent to the following: (9.2) E⊂W (-1) |E| χ K wt P \E = 0.Using the duality discussed in Remark 3.2, identity (9.2) implies the following geometric identity underlying (9|E| χ K root P \E = 0.

B⊂W(- 1 )Example 9 . 7 .4

 197 |B| χ R+(V ∪B) = 0 and therefore B⊂W (-1) |B| s(R + (V ∪ B); x) = 0. Consider the set of vectors W = {w 1 , w 2 , w 3 , w 4 } in R 2 shown below, and let V be the empty set. The set W is easily seen to be cyclic with respect to V . Consider the point p depicted. The subsets B ⊂ W for which p lies in the cone R + (V ∪ B), so that χ R+(V ∪B) (p) = 1, are {w 1 , w 4 }, {w 3 , w 4 }, {w 1 , w 2 , w 4 }, {w 1 , w 3 , w 4 }, {w 2 , w 3 , w 4 }, {w 1 , w 2 , w 3 , w 4 }

(- 1 )

 1 |B| = 0.If p does not lie in the cone R + (V ∪ W ), this holds because the left side is an empty sum. So without loss of generality p lies in R + (V ∪ W ), meaning that the setX p := (a, b) ∈ R W + × R V + : p = w∈W a w w + v∈V b v v is a non-empty convex polyhedral cone inside R W × R V . Cover X pby the family of subsets {X p (w 0 )} w0∈W defined by X p (w 0 ) := {(a, b) ∈ X p : a w0 = min(a)}.

  by defining a w0 := 0 for all w 0 in A. Furthermore, the coefficients in the latter expression give an element (a, b) lying in w0∈A X p (w 0 ).For the "only if" assertion, assuming that w0∈A X p (w 0 ) is nonempty, pick (a, b) lying in this set. Thus p = w∈W a w w + v∈V b v v and one has µ := min(a) = a w0 for all w 0 in A. Rewriting this asp = w0∈A µ • w 0 + w∈W \A a w w + v∈V b v vand using the fact that u = w∈W w lies in R + V , one can rewritep = w∈W \A (a wµ)w ∈R+(W \A) + µ • u + v∈V b v v ∈R+V .Therefore p lies in R + (V ∪ (W \ A)).

  having power series coefficients described by the Bernoulli numbers B n . Consequently, for each i = 1, 2, . . . , d the factor x,ui

								e x,u i -1
	appearing in (2.3) is analytic in the variables x = (x 1 , . . . , x n ), and has power series
	expansion that begins with constant term +1. Note that the sum
	u∈Πu	e x,u	u∈Πu	1 + x, u +	1 2	x, u	2 + • • •
	is also analytic in x, having power series expansion that begins with the constant
	term |Π u |. Thus the expansion in (2.3) begins in degree -d with
			(-1) d	|Π u | i=1 x, u i d	.
	Whenever K is full-dimensional, so that d = n, expressing the u i in coordinates
	with respect to a Z-basis e 1 , . . . , e n for L, one has |Π u | = | det(u 1 , . . . , u n )|. Com-
	parison with Proposition 2.1(v) then shows that the proposition is correct when K
	is simplicial.
	When K is pointed but not simplicial, it is well-known (see, e.g., [23, Lemma
	4.6.1]

  and Kirillov [12, Proposition 6.2], or Miller and Sturmfels [21, Corollary 16.30].

	Example 4.3. Consider the skew diagram

This disjoint decomposition is closely related to the triangulation of K wt P that appeared implicitly in the proof of

Proposition 3.1, modelled on Gessel's proof of the main P -partition lemma in[START_REF] Gessel | Multipartite P -partitions and inner products of skew Schur functions[END_REF] Theorem 1]).

Actually, this relation is already transitive, although we will not need this here.

In the special case where V is empty, this is the notion of W being a totally cyclic collection of vectors from oriented matroid theory; see[START_REF] Björner | Oriented matroids, 2nd edition[END_REF] Definition 3.4.7].

Acknowledgements

This work began during a sabbatical visit of V.R. to the Institut Gaspard Monge at the Université Paris-Est, and he thanks them for their hospitality. He is also grateful to Prof. Michelle Vergne for an enlightening explanation of total residues. This work was finished during a visit of the second author to the University of Minnesota and he thanks them for the invitation and the welcoming environment.

The authors also would like to thank an anonymous referee for helpful comments.

Fourth author supported by NSF grant DMS-0601010.

here and then apply Corollary 8.3 to the poset on the right, which has two biconnected components.

Example 8.9. In [9, §7] it was explained how a disconnecting chain

in P , that is, one for which P \ σ has several connected components, leads to a factorization of the numerator of Ψ P (x) into factors indexed by each such component. After fixing one of the connected components Q of P \ σ, one can use several operations of opening notches, beginning with one that creates two elements p t , p ′ t covering p t-1 , and continuing down the chain σ, to "peel off" a copy of Q ⊔ σ until it is attached to P \ Q only at the vertex p 1 . At this stage use Corollary 8.3, to recover the factorization of [START_REF] Boussicault | Application of graph combinatorics to rational identities of type A[END_REF]Theorem 7.1].

We omit a detailed discussion to avoid the use of heavy notation. However, Example 8.7 illustrates the principle.

Lastly, one can use this to deduce a stronger form of Theorem A from the introduction. For a strongly planar poset P , and a bounded region ρ of the plane enclosed by its Hasse diagram, recall that min(ρ), max(ρ) denote the P -minimum, P -maximum elements among the elements of P lying on ρ. Name the elements on the unique two maximal chains from min(ρ) to max(ρ) that bound ρ as follows: (8.5) min(ρ) =:

Lastly, let f ρ be the following binomial in the polynomial algebra S := k[U ij ] i⋖P j :

In other words f ρ is the circuit binomial U (C) for the directed circuit C that goes and down the two maximal chains in (8.5) bounding ρ. Consequently,

i⋖P j (1 -X i X -1 j )

Ψ P (x) = ρ (x min(ρ)x max(ρ) )

i⋖P j (x ix j )


V A Traag

A Browet

F Calabrese
email: fcalabre@ie.ibm.com

F Morlot

Social Event Detection in Massive Mobile Phone Data Using Probabilistic Location Inference

The unprecedented amount of data from mobile phones creates new possibilities to analyze various aspects of human behavior. Over the last few years, much effort has been devoted to studying the mobility patterns of humans. In this paper we will focus on unusually large gatherings of people, i.e. unusual social events. We introduce the methodology of detecting such social events in massive mobile phone data, based on a Bayesian location inference framework. More specifically, we also develop a framework for deciding who is attending an event. We demonstrate the method on a few examples. Finally, we discuss some possible future approaches for event detection, and some possible analyses of the detected social events.

I. INTRODUCTION

Over the last decade many new data sources have arisen that can be used in the social sciences, ranging from online social networks, such as Facebook or Twitter, to huge mobile phone data, promising a completely new approach in the social sciences [START_REF] Watts | A twenty-first century science[END_REF], [START_REF] Lazer | Life in the network: the coming age of computational social science[END_REF]. This unprecedented amount of data on social behavior can be, and has been used to study the behavior of human beings. Data from mobile phones have been used to analyze many dynamics [START_REF] Onnela | Analysis of a large-scale weighted network of one-to-one human communication[END_REF] such as mobility behavior of people [START_REF] González | Understanding individual human mobility patterns[END_REF]- [START_REF] Song | Limits of predictability in human mobility[END_REF], uncovering highly regular workoffice patterns [START_REF] Song | Limits of predictability in human mobility[END_REF], [START_REF] Eagle | Eigenbehaviors: identifying structure in routine[END_REF], communities in mobile phone networks [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], [START_REF] Palla | Quantifying social group evolution[END_REF], the geography of calling behavior [START_REF] Blondel | Regions and borders of mobile telephone in Belgium and in the Brussels metropolitan zone[END_REF], showing a (gravitational like) effect of distance on the probability of a link [START_REF] Lambiotte | Geographical dispersal of mobile communication networks[END_REF], and the so-called strength of weak ties [START_REF] Onnela | Structure and tie strengths in mobile communication networks[END_REF].

In this paper we will focus on detecting social events in a massive mobile phone data set. One can think of events such as rock concerts and sports finals, but also of events such as protests or emergencies. The idea here is to focus on the non-routine behavior of people, unlike earlier approaches [START_REF] Calabrese | The geography of taste: Analyzing cell-phone mobility and social events[END_REF], [START_REF] Candia | Uncovering individual and collective human dynamics from mobile phone records[END_REF]. For example, in an office district, many people will be in a single place around the same time, but this does not constitute any social event.

Earlier analysis of events showed common geographical profiles for certain types of events, and suggested a proximity effect [START_REF] Calabrese | The geography of taste: Analyzing cell-phone mobility and social events[END_REF]. Such events will presumably have a significant impact on urban transit, so are important for urban planning [START_REF] Ratti | Mobile landscapes: using location data from cell phones for urban analysis[END_REF], [START_REF] Reades | Eigenplaces: analysing cities using the space-time structure of the mobile phone network[END_REF]. Another approach focused on anomalies to detect emergency events [START_REF] Candia | Uncovering individual and collective human dynamics from mobile phone records[END_REF]. Moreover, people seem to behave differently at social events [START_REF] Bagrow | Collective response of human populations to large-scale emergencies[END_REF]. This highlights the importance of detecting social events, in order to analyze them.

II. DATA

Because the methodology we will develop here is partly motivated by the type of data available, we will first briefly introduce them. The original data set we propose to analyze consists of all the calls of a large mobile phone company in a European country. For each call, we have an identifier (properly anonymized) for the person making the call (caller) and for the person receiving the call (callee). For both caller and callee we also have available the cell tower identifier at the time the call started. Coupled with the location of all the antennas of the company, we can infer some position of the users. We included both text messages and actual calls in our analysis. The relevant data cover 14 months for about 5.75 million users and around 900 million calls and text messages.

We perform a selection of the users based on their calling behavior. In order to be able to correctly identify users' locations, we need sufficiently regular connections to the network, which can be expressed in terms of the time between two calls [START_REF] Barabási | The origin of bursts and heavy tails in human dynamics[END_REF]. We impose that 80% of the time, a user will be involved in a new call less than one day after his last one. Based on this selection, we keep around 55% of the users, while keeping around 87% of the total number of calls and text messages.

III. LOCATION INFERENCE

To be able to extract accurate and meaningful information from this raw data, we use a simplified probabilistic framework, based on the work of [START_REF] Zang | Bayesian inference for localization in cellular networks[END_REF]. The most important reason for taking a probabilistic modeling approach is the somewhat erratic antenna jumps. It frequently happens that a user switches from neighbouring antennas while making several calls, although it is unrealistic the user is actually moving (because he would move too fast to be realistic). Furthermore, since we expect usage to be more intense than usual when events take place, multiple antennas will probably serve customers at the event location due to load balancing. Finally, our method can be seen as a smoothened Voronoi tessellation, thereby dealing automatically with these type of phenomena.

We denote by x the position of the user and by X i the position of antenna i. We will denote the probability to be Fig. 1. Probability density ψ i (x) (represented by the level curves) for a particular antenna i (the central black 'X'), showing neighboring antennas (the red 'X's) and the local Voronoi tessellation (in dark lines). The density can be seen as a smoothened Voronoi tessellation, where there is also some (small) probability to be connected to antenna i when the user is in another Voronoi cell.

connected to antenna i given position x with

φ i (x) = Pr(a = i|x) = ∞ 0 e -r j =i 1 -exp -r x -X j β x -X i β dr, ( 1
)
where β is a parameter representing how quickly the signal decays [START_REF] Zang | Bayesian inference for localization in cellular networks[END_REF]. As stated, this can be seen as a smooth approximation of the Voronoi tessellation, in which a user will always connect to the closest antenna. To see this, assume that the distance

d i = x -X i < d j =
x -X j is smaller for i than for j. Then the fraction d i /d j < 1, and the probability φ j (x) → 0 for β → ∞. Hence, the probability to connect to any antenna j, while there is another antenna i closer, goes to 0 for β → ∞, congruent with the Voronoi tessellation. An example of this probability density is shown in Fig. 1. Since we are interested in the probability ψ i (x) to be present at x upon connecting to antenna i, using Bayes' rule (without prior information), we obtain

ψ i (x) = φ i (x) D φ i (x)dx . (2)

IV. EVENT DETECTION

In this section we will introduce the methodology to detect social events based on the calling patterns of users. We define social events as exceptionally large gatherings of people who are ordinarily not present at a specific location. There are a few key ingredients in this definition that need to be made clear: (1) presence at a location; (2) ordinary presence at a location; and (3) exceptionally large gatherings. We will define these concepts more clearly and formally in the following subsections.

We will first explain how we define the probability to be present at a certain location. Then we will define the ordinary probability of a user to be present at a certain location, and use both these probabilities to define a measure of attending a (possible) event. Finally, we will specify how we decide whether there is an event taking place or not at a certain location at a certain time.

A. Presence Probability

We will be looking for an event in region A, at some starting time t s and ending time t e during a specific week w. Let us denote by X A those antennas who cover the region A. Furthermore, let τ be the time window [t s , t e ] of the potential event and τ v be the same time window during week v = 1, . . . , W . We can then select all calls that took place within the time window τ w at antennas in X A . Furthermore, a user u has made calls at antennas i 1 , . . . , i Cu ∈ X A at time t 1 , . . . , t Cu in τ w . We are interested in the probability Pr p a user u was present at A during time τ w .

For the exact time t c , for a specific call c, the probability a user was in A is clear from the previous section, and we denote it by Ψ A,c (t c ) = A ψ ic (x)dx. We now have to infer somehow the probability to be present at A at some time t = t c . Keeping it simple, we assume a person leaves a particular location at a constant rate γ for t > t c , without any probability of returning. Similarly, we assume a person to arrive at a constant rate γ for t < t c . This constant rate assumption then yields

Ψ A,c (t) = e -γ|t-tc| A ψ ic (x)dx. (3)
We have chosen γ such that there remains only 1% of the original probability 15 minutes after and before the call c. Taking all calls into account, and normalizing by the theoretical maximum, it follows that

Pr p (u, A, τ w ) = 1 t e -t s te ts max c Ψ A,c (t)dt max i∈XA ψ i (A) . (4)

B. Ordinary Probability and Probability of Attending

Based on the same idea we used to compute the presence probability Pr p (u, A, τ w ), we derive the average probability a user u was in A within a certain time window τ for all weeks different from w. This probability will be called ordinary probability Pr o to reflect the fact that it concerns ordinary behavior, i.e. regular mobility pattern independent of the event that may occur at week w. This can be defined as

Pr o (u, A, τ w ) = 1 W -1 W v=1 v =w Pr p (u, A, τ v ), (5)
This probability captures how regularly this particular user was in the area of interest A during the time window specified by τ , at other weeks than w. We then define the probability the user was attending the event as

Pr a (u, A, τ w ) = Pr p (u, A, τ w ) (1 -Pr o (u, A, T )) , (6)
where higher values indicate a higher degree of certainty the user was attending an event on week w compared to its ordinary behavior during all other weeks.

May Jun Jul AugSep

Nov Dec Jan Feb Mar Apr May Jun Jul -2

C. Event Detection

In order to classify wether a user is attending an event or not, we select a cut-off value Pr * a such that only 1% of the users have such a high attendance probability on average over all weeks. We then say a user has attended a social event on week w whenever Pr a (u, A, τ w ) > Pr * a . Let us denote by n w the number of users that according to this decision rule have attended for a week w. Then, let µ denote the average number of attendees, and by σ the standard deviation of the number of attendees. We then state that an event has taken place, whenever

n w -µ σ = z > 3, (7)
which is known as a z-score. Since n w seems to be normally distributed, when one removes the outliers (which will most likely be our events), the above condition simply states that the probability to see so many possible attendees given the normal distribution of n w is only about 1% with z > 3, hence they really represent unusually large gatherings of people. We will use this threshold of z > 3 in the remainder of the paper.

V. RESULTS

We will now demonstrate the method on a number of different examples: (1) the national football stadium; (2) a city park; (3) a rural area; (4) a touristic area. For the first location we know what matches were being played, in particular the finals of the national football cups. We know that (at least) one big music festival took place in the large city park. We included a remote rural area, for which we expected to find no events. The popular tourist destination is included to see how the method is affected by a strong seasonal trend.

The results of the z-scores for the football stadium are displayed in Fig. 2(a). The two peaks represent exactly the two finals played, and our method then seems to detect these two finals correctly. Both finals were played at a Sunday between 17-19h, and we used the data between 15-21h to detect the event. A more detailed analysis of the first final shows that the number of calls drop during the hours 17-19h, as shown in Fig. 3(a), but more stronger for those who are attending the event according to our method. The results for the second final are similar.

We can also compare the number of calls to the average on this weekday, which is represented by the thin dark line. The number of calls of the non-attendees is larger than usual just before and just after the match. So, this suggests that some people could be incorrectly classified as non-attendees.

The z-scores for the large city park are displayed in Fig. 2(b). We observe only one clear peak, which corresponds to the date of the music festival. We again consider the difference between the calls of those who attended (according to our method) and those who do not, as displayed in Fig. 3(b). The most striking feature is that the calls of attendees does not really seem to be increasing or decreasing throughout the day. More specifically, those who attend the music festival seem to be mainly the ones who call during the night. Given the nature of the festival, probably many young people continue to party into the night.

For the rural area we unexpectedly found one event. Upon closer examination, this specific day surprisingly turned out to be Christmas evening. Probably many family members gather, who would normally be elsewhere in the country. Indeed for the other locations this week also shows a somewhat higher z-score (although not very high). The tourist destination shows signs of two events during the summer, and it is clear what is the high season and what the low season. For the tourist destination it is quite normal there are relatively many people during the summer who are not there often, namely to spend their holidays.

These four examples suggest our method is capable of detecting events, although one should take care in interpreting the results. Looking into the calling dynamics for specific days of the event suggests that our classification of attending and not attending may work well, although it remains difficult to assess the performance exactly.

VI. CONCLUSION & DISCUSSION

This method gives a probabilistic framework to detect events, and determine which users participated in the event.

Based on a simple Bayesian location inference framework, we have suggested how we can indicate which users are likely to have attended the event, and when and where any events happened. We have demonstrated this method on a few examples, using limited data, namely only positions of the antennas. Still, it remains difficult to validate the method without additional information.

However, considering a simple Voronoi method, not using such a probabilistic framework, already seems to provide some indication whether there is an event or not. However, it can easily misinterpret which people are actually attending. Therefore, we might consider the following improvement. We first detect social events using a simple Voronoi method, but use the more refined method suggested here to decide which people actually participated in the event. So using the Voronoi approach we obtain a coarse-grained view of which events happened, while our method gives a more fine-grained view of who is attending, and could provide a more accurate estimate of the exact location. This would speed up the algorithm, making it more feasible to detect events across the whole country with reasonable accuracy.

Once we have detected a number of events, we can analyze them more closely. Since we are able to (re)trace the steps of attendees, we can analyze their mobility behavior and their calling behavior. People attending any events are showing, by definition, mobility behavior that is different from their routine. So the non-routine mobility behavior of people seems to be correlated with each other. Furthermore, we can analyze whether this correlation is different for people that call each other. It can be expected for example, that most people will not go to social events on their own, but rather meet with friends. It might also be possible to investigate any possible wordof-mouth effect. Finally, the methodology might be useful in situations of crowd management or emergency detection. One of the more interesting directions of research will be that although people are behaving differently from ordinary, they tend to do so together.

Fig. 2 .

 2 Fig. 2. Z-scores of number of attendees for four different areas of interest: (a) the national football stadium; (b) a large city park; (c) a rural area; and (d) a tourist destination.For the national football stadium, the two finals clearly stand out, and for the park the music festival stands out. The rural area shows only one event, namely Christmas evening, while the tourist destination shows two events during the summer.

Fig. 3 .

 3 Fig. 3.Figure(a) shows the number of calls made by those who have attended the first final according to our method and those who haven't. At the time of the match (between 17-19h), the drop is most visible for those who attend, as expected. Figure (b) shows the number of calls for those attending and those not attending the music festival. The festival lasted several days, with music continuing late into the night (or early in the morning).

ACKNOWLEDGMENT

The authors acknowledge support from a grant "Actions de recherche concertées -Large Graphs and Networks" of the "Communauté Franc ¸aise de Belgique" and from the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The authors would like to thank Paul van Dooren, Vincent Blondel and Gautier Krings for some helpful comments and discussion.