Discrete Comput Geom 2:297-317 (1987)

GWSia6-t t98~ Sprinser-Verla8 New York

Balanced Subdivision and Enumeration in Balanced Spheres Louis J. Billera 1. a n d K a t h e r i n e E. M a g u r n 2.

t Department of Mathematics and School of Operations Research, Coruell University, Ithaca, NY 14853, USA, and Department of Mathematics and Cemer for Operations Research, Rutgers University, New Brunswick, NJ 08903, USA 2 Department of Mathematics and Statistics, Miami University, Oxford, OH 45056, USA

Abstract. We study here the affine space generated by the extended f-vectors of simplicial homology ( d - 1)-spheres which are balanced of a given type. This space is determined, and its dimension is computed, by deriving a balanced version of the Dehn-Sommerville equations and exhibiting a set of balanced polytopes whose extended f-vectors span it. To this end, a unique minimal complex of a given type is defined, along with a balanced version of stellar subdivision, and such a subdivision of a face in a minimal complex is realized as the boundary complex of a balanced polytope. For these complexes, we obtain an explicit computation of their extended h-vectors, and, implicitly, f.vectors.

1.

Introduction

In general terms, this paper investigates balanced simplicial complexes. These are complexes whose vertices are labeled by 1, 2 , . . . , m in such a w a y that each maximal face has ai vertices with label i, 1 -< i-< m. Such complexes are said to be balanced of type a, where a = ( a l , . . . , am). In particular, we generalize to the balanced case some results o f [3], [4], and [5] for completely balanced complexes, i.e., balanced complexes o f type ( 1 , . . . , 1). For a balanced simplicial complex A, let fb(A) denote the n u m b e r o f faces o f A having b~ vertices with label i, where b = (bl . . . . , bin). The vector f ( A ) = (g~(A))b~a is called the extendedfivector o f A. We determine here the affine space generated by the extended f-vectors o f simplicial h o m o l o g y ( d - 1)-spheres which are balanced o f a given type, thus determining all possible affine relations satisfied by their components. * Supported in part by NSF Grant DMS-8403225.

298

L.J. Billera and K. E, Magurn

We now present the definitions and basic facts to be used throughout the paper. Let 0. e A, a simplicial complex. Then the link of 0. in A is defined to be lka0.={~'~A: 0 . n ~ ' = O , 0 . u z ~ A } . I f 0 . ~ O , the deletion of 0. in A is A\0.-= {¢ ~ A: 0. ¢ z}. If A1 and A2 are simplicial complexes with no vertices in common, then their join is defined to be A~ * A2 = {0.~ u 0,2:0.1 ~ A1,0"2 c A2}. Note that each of these operations yields a simplicial complex. For 0. ~ A and v a vertex not in A, the stellar subdivision o f 0. in A is the complex sta(0., v) - ~ A \ c r ) u ~ * 0 ~ * lkacr. Here ~ is the complex consisting of all subsets of 0.; ~ - { v } . Of historical interest is Alexander's "arithmetic" describing stellar subdivision on which a whole theory of stellar equivalence is based [1]. Whether such a theory can be developed for balanced complexes is a question of some interest, but beyond the scope of this paper (see [15].) Stellar subdivision may also be defined for polytopes. For a discussion in the most general (nonsimplicial) case, see [9]. A ( d - 1)-dimensional simplicial complex is said to be a homology ( d - 1)sphere if for each k-face 0.eA, lka0. is a ( d - k - 2 ) - d i m e n s i o n a l complex having the rational homology of a (d - k - 2 ) - s p h e r e , - 1 -< k ~ d - 1. We denote by C~ the set of all type a balanced complexes that are homology (d - 1)-spheres. If A is a ( d - 1)-dimensional simplicial complex, then for - 1 _i_< d - 1, we denote the number of faces of A having dimension i by f~ =f~(A). The f-vector and h-vector of A are defined by

f=(f-~,fo,...,fd-~)

and

h=(ho, hl . . . . ,ha),

where j=o We can define an extended h-vector h(A) = (hb(A))b~a of a balanced complex (of type a) by

hb(A)

~, fc(A) ~

b-c/ai--C'~

An alternative definition, more useful for our purposes, is the following. See [21] for details. Let t represent the multivariable ( h , . - - , tin), and if b = (bl, • • •, bin) INm, let t b denote t~1 . . . . . b,~ and define the polynomial f(A, t)-= Y.b~, fb(A) t~tin, For w = ( w l , . • •, Wm) ~ N m, define h(W)(A, t) --- (1 - t)Wf(A, t/1 - t ) where the notation ( l - t ) w means I-I7'=1( 1 - t i ) w'. When w = a, the balanced type of A, we distinguish h~°)(A, t) = (1 - t)af(A, t/1 - t) as h(A, t), defining the coefficient of t b in h(A, t) to be hb(A). Both the extended f - v e c t o r and the extended h-vector are refinements of the usual f - v e c t o r and h-vector. Two useful interpretations of the number hb(A) have been supplied by Stanley. See [21] for details of both. First, hb(A) is the vector space dimension of the bth summand in the usual Nm-grading on the Stanley-Reisner ring of A rood a homogeneous system of parameters. Secondly, if A is balanced of type a and o q , . . . , o's is a shelling of A, then hb(A) counts the number of times it happens in the shelling process that the unique minimal face of o'~ (1 - i <- s) which is not contained in 0.1 u . • • w 0 . H is type b.

Balanced Subdivisionand Enumerationin Balanced Spheres

299

The linear relation defining the (extended) h-vector from the (extended) f-vector is invertible, so a description of the affine span of all h-vectors will implicitly give a description of the span of all f-vectors. It is the main result of this paper that the affine span of the extended h-vectors of balanced homology spheres (of type a) is given by the equations hb(A)= ha-b(A) for all b - a . This description reduces to that given by the classical Dehn-Sommerville equations for the usual f-vectors (hi = ha-i, 0 <- i <- d, in the h-vector form) of simplicial homology spheres (in particular, simpliciat convex polytopes) [ 11], [ 13], [ 19], [4], and to that obtained for the completely balanced case in [4] (hs = h~ for S c_ { 1 , . . . , d}, where hs---hb, b the characteristic vector of the set S). In the former case, a = (d) (all vertices receive the same label) and in the latter, a = (1, 1 , . . . , 1).

2. Symmetry of the Extended h-vector This section specifies certain linear equations which the coordinates of every extended h-vector satisfy. In addition to these, each h-vector satisfies the balanced version of Euler's relation, and this collection of equations will later be shown to characterize the space aff(hb(C~a)). The symmetric nature of the extended h-vector is displayed in the following theorem, whose proof is a straightforward generalization of a proof of Bayer and Billera [4, p. 235], which in turn is based on one of Stanley's [22]. For details, see [15]. We remark that in the case of shellable spheres (e.g., polytopes), a purely combinatorial proof is possible, using Proposition 3.6 o f [21 ]. See Proposition 5.1 of [4] for such a proof in the completely balanced case.

Theorem 1.

Let A ¢ Ca~, a = (al . . . . , am). Then hb(A) = ho_b(A) for all b<-- a.

This theorem is enough to determine an upper bound on the dimension of aff(hb(Cd)). In what follows, let K = I-Ii~l (ai+ 1).

Corollary 2.

dim aff(hb(fdo)) <-- [(K - 1)/2].

Proof. For all A c C d we have ho = I and hb(A) = h~_b(A) for al! b-< a. These are independent linear equations and there are [K/2J + 1 of them, so they determine an affine subspace of dimension K - ( I K / 2 J + I ) = [ ( K - I ) / 2 J . Finally, aff(hb(C~)) is contained in this subspace, and so dim aff(hb(Ca,)) <[ ( K - 1)/2]. []

3.

The Minimal Type a Complex

It is known that if S is an unlabeled d-simplex, h(OS) consists of d + 1 l's followed by the appropriate number of O's [4]. This section offers a description of certain polytopes whose boundary complexes, in the balanced case, act as analogues to aS. The extended h-vectors of these complexes are computed, and are shown to consist of l's.

300

L J. Billera and K. E. Magurn

First, we describe a basic construction. Suppose P~ is a d,-polytope in R d, with 0 ~ int P,, i = 1, 2. L e t / 3 = P1 x {0} and 132= {0} x P2 be embeddings of P~ in R d, d = d, + d2, and define P, # P2--- cony(/31 ~/~2). In the case in which P1 and P2 are simplicial polytopes, it is straightforward to verify that

o(P, #

P2) = oP, • oP2.

Suppose a = ( a l , . . . , a,,) and let d--=~m=la~. For l<-i<-m, let S~ be an a;simplex in R ~' with 0 in its interior, and with vertices labeled i. Assume $1 . . . . ,Sm are embedded in R e, as above, and define A-=o(S~#S2#...#Sm)= aS~*0S2*. •'*OSm. It follows that A is type a, for a maximal simplex of aS~ has exactly a~ vertices. We call A the minimal type a complex.

Examples (1) a = ( 2 , 1 ) = 0S1 * 052, where S, is a 2-simplex labeled 1, and 5:2 is a l-simplex labeled 2.

]

]

2 ~2) a = (1, 1, 1) A = 0S, *aS2.0S3, where, for 1-< i---3, Si is a 1-simplex labeled £ 1

3

3

Remark 1. ~, is minimal in the sense that it has the smallest n u m b e r of vertices of any homology sphere of type a. For, if A is a homology sphere o f type a, the number o f vertices of A with label i must be at least ai, by definition o f "type a". Suppose for some i that the number o f vertices with label i is exactly a~.

Balanced Subdivision and Enumeration in Balanced Spheres

301

Then each facet of A contains all the vertices with label i, that is, a vertex v with label i is contained in all the facets of A. But then for any facet F of A, F \ { v } is a subfacet included in a unique facet, which is impossible. Thus A is minimal among type a homology spheres in terms of number of vertices. For a given type, how man), vertices is this? I f a = ( a ~ , . . . , am) and a~ ~ 0 for all 1---i_< m, then clearly fo(A)=~7'=~ (a~+ 1). An adjustment must be made if a; = 0 for some i. (This situation occurs in the next section.) In the construction of 3,, a~ = 0 indicates a 0-simplex v, labeled i. v is placed on the origin in the embedding, so when the convex hull of all the simplices is taken to make A, v disappears into the interior of the polytope. Thus a~ = 0 contributes no vertices to A. So, in general,

foi?~) = ~. (a,+ l ) - [ { i : a , = 0 } I. i=1

Remark 2. It is also true that A is unique among the homology spheres of type a = ( a l . . . . . a~) having a ~ + l vertices labeled i, l<-i<-m. For if there exists another such complex F, it can be embedded as a full-dimensional subcomplex of A. Then since F itself has 0 boundary, F must be all of A. (Alternatively, one can use "invariance of domain." See [16] and [12].) The rest of this section is devoted to the computation of hb(A) for b - a.

Proposition 3.

Let A1 and A2 be balanced complexes. Then A1 * A2 is balanced, and hb(A,* A2)=Z~+~=b ho(A,) " hw(A2).

Proof. Choose an order for the set of distinct labels appearing in A~ or A2, and write the vectors describing the type of each complex according to this order, using O's where necessary. Suppose A~ is type a = ( a l , • • . , am) and A2 is type a'= ( a ~ , . . . , a ' ) . A maximal simplex in AI* A2 is the union o f a maximal simplex in A1 with a maximal simplex in A2, and it is clear that A~*A2 is balanced of type a+a'. In what follows, let t denote the multivariable ( t l , . . . , tin) and let ( l - t ) ~ denote the product ( l - t 1 ) ~ . . . . . ( 1 - t , , ) ~ for v = ( v l . . . . . vm). Since fb(A~ * A2) = ~ o+w= b fv(A~)" fw(A2), we have f(A~ * A2, t) =f(A~, t ) . f(A2, t). Then h (A 1* A2, t) = (1 -- t) o+o'f(A~ * A2, t/1 - t) = (1 - t ) o f ( A ~ , t/1 - t ) . (1 -t)~'f(A2, t/1 - t ) = h(A,, t ) . h(A2, t). Equating coefficients of these polynomials gives hb(A~*A2)=

E

h~(A,)- h~(A2).

[]

V+w=b

Corollary 4.

I f A~ . . . . . A n are balanced complexes, then A1 *- • • *A~ is balanced, and hb(A1 *" " * An) = ~.v,+...+vn=b hv~(A1) . . . . . hv,(A,), where v~ is a vector, 1
302

L.J. Billera and K. E. Magurn

Let At . . . . , A , be balanced complexes with disjoint labeling sets; say Ai is type a i = ( a i l , . . . , a i m , ) for l<_i<_n. Then A ~ * . . '*An is balanced of type a = ( a l , . . . , an) and for all b <- a, hb(Al *" • ' *A,) = hb~(A1) . . . . . hb.(A,), where

Corollary 5.

bi = ( b , l , . . . , bim). Proposition 6. I f A is the minimal complex of type a = ( a l , . . . , b <- a, hb(A) = 1.

am), then for all

Proof. Recall A = OSt*'"*OSm, where Si is an ai-simplex, and the vertices in Si are labeled i. Let b=(bl . . . . ,b,,). Then hb(A)=hb(OSl*'"*OSm)= hb~(aS~) . . . . . hb~(OS,,) by Corollary 5. Since

h(aS,) = ( ~ ,

0,... ,o),

ai+l

and b~ -< a~ for all i,

hb,(CgSi)

=

1 for 1 <- i - m. Thus hb(A) = 1.

[]

4. A Balanced Stellar Subdivision One technique often used in generating new complexes from existing ones is stellar subdivision. In this section we introduce a balanced version o f the concept, and examine h o w such an operation affects the extended h-vector. S u p p o s e A is a balancedsimplicial complex o f type a = ( a l , . • •, am), and o- e A is a f a c e o f t y p e x - a. Let A denote the minimal type x complex, a n d ~ a maximal face in A. T h e n define the balanced stellar subdivision of cr in A to be stba,(A, or) -- (A\tr) w [lkatr* ( A \ ~ ) ] , where tr and ~ are identified by a label-preserving bijection o f their vertices.

Examples (1) a = (2, 1), x = (1, 1) 2

5

1

2

= w

2

w

1

Balanced Subdivision and Enumeration in Balanced Spheres

303

~ '\0

q

--

2

Stbal(~,o) : l

l

2

(2) a = ( I , I), x = (I, I ) o

EkAo = ~\o =

S Z~\a= I Stbal(a,a ) =

,.__~

•

0

304

L.J. Billera and K. E. Magurn

To show that Stbal(A, tr) is balanced o f type a, we examine its maximal faces and see they are of two types: (1) maximal faces of A not containing tr, and (2) faces which are obtained by the union of a maximal face in lkatr with a maximal face in A\~. Faces of the first kind are dearly type a. Suppose r is a face of the second kind, that is, r = y u 8 where y is a maximal face in Ikacr and ~ is maximal in A\~. Then 8 is type x; 3' u tr is a face in A, and is maximal since y is, so 3' u o- is type a. Since o- is type x, 3" must be type a - x . Hence ~'= 3'u t~ is type (a - x ) + x = a, showing stbal(A, o-) is balanced of type a. Another useful fact emerges from the foregoing discussion, which we record here for future reference.

I f A is a balanced complex of type a, and cr ~ A is a face of type x <--a, then Ikacr is a balanced complex of type a - x .

Lemma7.

We now consider how, for A minimal and o- c A, as the boundary complex of a simplicial polytope.

Stbal(A, O') may be realized

Suppose A is the minimal type a = ( a l , . . . , am) complex, and ere A is a face of type x. Then there exists a simplicial d-polytope P~ ( d =--Y.~'=I ai) and a labeling of the vertices of P ~ such that OP x= stba~(A, ~r).

Theorem 8.

Proof We give here the basic idea o f the proof, which generalizes that of Theorem 3.1 of [5]. See [15] for details in the general case. Let Q be the minimal polytope of type a; let x = (x~ . . . . . xm). For x =0, the theorem is satisfied by letting px be Q. So we may assume that x ~ , . . . , xr > 0, xr+t . . . . . xm=O, for some r > 0 . Starting with any face Ft of type x, form the polytope Q~ = sto(F~, t~), where t~ is a new vertex labeled 1. Unless r = 1, Q1 is no longer balanced, as it has a face F2 with a~+ 1 vertices of label 1. Form Q2= sto,(F2, t2) where t2 has label 2. If r > 2, then Q2 will have a face F3 with a2+ 1 vertices of label 2. Continue until defining Qr which can be taken to be the polytope P~. [] Example

2

a=(2,1),x=(1,1)

~

i

2

Q

" t

1

F

2

Q (solid)

1

2

Q1

Balanced Subdivision and Enumeration in Balanced Spheres

305

2 tl

t2

l

l

Q2 In fact, the construction in the proof shows that if A is a n y balanced simplicial type a = ( a ~ , . . . , a m ) complex and o . e A is a type x face involving r labels, 1 - r_< m, then stb,l(A, o.) is obtained by a sequence of r ordinary stellar subdivisions. A similar procedure can be followed to show that any pure labeled complex can be stellar subdivided into a type a balanced complex (maintaining existing labels) for any vector a not obviously excluded by the existing labels (i.e., the type allows for at least as many labels as have already been assigned). See Proposition 3.3. of [15]. There remains the computation of the extended h-vector of Stbal(A, or).

Lemma 9.

I f A is the m i n i m a l type a = ( a l , . . . , am) complex, and o . ~ A is a f a c e o f type x <--a, then lkao. is the m i n i m a l type a - x complex.

Proof. By L e m m a 7, Ikao is a balanced (simplicial) complex o f type a - - x . We first show that f o ( I k a o . ) = f o ( A ' ) , where A' is the minimal type a - x complex. Remark 1 preceding Proposition 3 established that f0(A')= Y.i%t (a~ - x~+ 1) -1{i: a~ = x~} I. Without loss of generality, assume that a~ # 0 for each i, since otherwise ai = x~ = 0 and there would be no vertices labeled i in either A or A'. Now, suppose o.1 = oq * o'2*. • • * o.m, where o'i consists of all the vertices of o. having label i. Then Ikao. = lkas o. I * . . . ,

lkos o.,n,

where the Si are as in Section 3. Thus

fo(lkao.)= ~ fo(lkos, o.i). i=l

If ai = xi then lkos, cri = ~ and if ai > x~ then fo( lkas, o.~) = a~ + 1 - x , . So fo(Ikzo.) = fo(A') and thus lkzo. is combinatorially equivalent to A' by the uniqueness of h'. []

306

L.J. Billera and K. E. Magurn

Theorem 10. I f A is a minimal type a = ( al . . . . , am) complex, and cr ~ A is a face of type x <- a, then for all b <- a hb(stb~l(A, o')) = 1 + I{(Y, z): y, z ~N m, y + z = b, O<- y <- a - x , O ~ z ~ x} I.

Proof. First, if hi and A2 are balanced complexes of type a, then f(A~ u A2, t) = f ( A , , t) +f(A2, t) - f ( A , ca A2, t). So h(A, u A2, t) = (1 - t)~f(a~ u A2, t/1 - t ) = (1 - t)af(A,, t/1 - t) + (1 - t)af(A2, t/1 - t) - (1 - t ) ° f ( a ~ c~ A2, t / 1 - t )

= h(A1, t) + h(a2, t) - h(~)(A~ c~ A2, t). Now apply this to stb,~(A, or) -- AI • A2, where A1 = A\cr, and A2 = Ikacr* ( A \ d ) . Recall that o- and ~ are identified by a bijection between vertex sets which preserves labeling; thus A~ c~ A2 = (A\cr) c~ [lkacr* (A\~)] = Ikao'.aa-. Note also that the complexes A~ and A2 are type a. So h(Stb,~(A, cr),t)= h(A\cr, t) + h(Ikacr* (A\~), t) - h(")(lk,,cr* a~, t). Since A is the union of the type a complexes A\~, and a-*lkao', and ( A \ o ' ) n ( ~ , * l k a o ' ) = l k a c r * a ~ , we also have h(A, t) = h(A\cr, t) + h ( ~ * lkacr, t) - h(a)(lkao'*O~", t). Combining these two equations gives h(Stba~(A, ~,), t) = h(A, t) - h ( ~ * lkao, t ) + h(")(lkao-.aa -, t) + h(lkMr* (A\~), t) - h(~)(lkacr* 0~, t) = h(A, t) + h(Ik,,~r, t)[h(A\o,, t) - h(0, t)], the last equality using the fact that the h-polynomial o f a join is the product of the h-polynomials of the complexes joined, established in the proof of Proposition 3. By shelling the single simplex ~ and appealing to Proposition 3.6 of [21], we see that h(#, t) = 1. Similarly, shell A so that ~ is the last simplex in the shelling order. (See [7].) Since A is minimal, Proposition 6 (this paper) and Proposition 3.6 o f [21] yield ~ ^ {; h~(A\cr) =

f o r a l l b<--x, else.

So * ~ {10 f o r a l l b < x , b ~ O , hb(A\o') - hb(t~) = else. Recalling that A is minimal of type a, and lkAtr is minimal of type a - x gives {~ hb(A) =

for all b-
Balanced Subdivision and Enumeration in Balanced Spheres

307

and

hb(Ikacr)=~ l

[0

for all b < - a - x , else.

Hence for fixed b -< a the equation o f h-polynomials yields hb(Stba~(A, or))= 1 + (the n u m b e r o f ways b may be written as y + z with 0 <- y -< a - x and 0 ~ z x ) = 1 +l{(y, z): y, z ~ N", y + z = b, O<-y <- a - x , O;~z~x}t. []

5. An Afline Spanning Set for Balanced Spheres We now turn our attention back to the problem o f determining the dimension o f att(hb(C~)). For convenience, the notation is reviewed here. C~ denotes the set o f all type a = ( a l , . . . , am) balanced h o m o l o g y (d - 1)-spheres and (hb(C~)) the set o f all vectors ( h b ( A ) ) b ~ e N r for A ~ Cad, where K = I-I?=~ (a~ + 1). It was shown in Corollary 2 that dim aff(hb(C~a)) <- [(K - 1 ) / 2 1 , and the aim here is to demonstrate equality. This is accomplished by obtaining [ ( K - 1)/2J + 1 affinely i n d e p e n d e n t vectors in aff(hb(C,a)). At the same time, by using ideas developed in the two previous sections, we exhibit a set o f balanced simplicial polytopes whose extended h-vectors span aff(hb(C~a)). For x-< a let P~ be the minimal type a complex subdivided over a face o f type x. Define a lexicographic order on all x-< a as follows: x < y if xi < yi for some i, 1 -< i-----m and xj = yj for all j < i. Define a K x K matrix M whose columns are indexed by b-< a, written in this lexicographic order, and whose rows are indexed b y x -< a, same order. The (x, b)-entry o f M is

hb(P ~) = 1 + I{(y, z): y, z~Nm, y + z = b, O<-y < - a - x , O ~ z ~ x } l . We will show that M has r a n k [ ( K - 1)/2J + 1. First, note that hb(P o) = 1 for all b, since x = 0 precludes the possibility o f any z. So subtract this row from all others to get the matrix M ' whose (x, b)-entry is hb(P x) - 1 for all x--< a, x ~ 0, and whose 0 row is all l's; this operation does not change rank. Next, consider the related matrix M " - MI - M2, all matrices indexed by row and c o l u m n as before, where M" is an adjustment o f M ' which allows z = 0 and z = x, M1 corrects for the adjustment z = 0, and M2 for z = x. Then the (x, b)-entry o f M" is 1{(Y, z): y, z e N m, y + z = b, 0 -< y -< a - x, 0 --- z -< x}l, the (x, b)-entry o f M1 is 1 if 0--< b -< a - x, 0 else, and the (x, b)-entry o f M2 is 1 if x <- b --- a, 0 else. M ' differs f r o m M " - M ~ - M2 only in the 0 row, which in M " - M I - M2 is all - l ' s , so rank is the same. Further examination o f the matrices M", M1, and M2 reveals that each has an underlying structure which turns out to be the key to the determination o f the rank o f M. This structure is uncovered in the following series o f lernmas.

308

L.J. Billera and K. E. Magurn

Lemma 11. Let a>-O bean integer. Then for integers O<-x<-a/2 and O<-b<-a, the function N ( x , b)=-I{y, z): y , z ~ Z , y + z = b , O < - y < - a - x , 0 - z - x } I takes on values b+l if O<-b<-x, N(x,b)=~x+l if x + l < - b < - a - x , [a-b+l if a - x + l < - b ~ a .

f

Proof. Set up a matrix of size ( a - x + 1 ) x (x + 1), where the rows are indexed by y = 0 , 1 , 2 , . . . , a - x , and the columns by z = 0 , 1 , 2 , . . . , x . Note that since x <- a/2 there are at least as m a n y rows as columns. Define the (y, z)-entry to be y + z. Then the entries on a given reverse diagonal are all the same, and if b is the entry, N ( x , b) is the n u m b e r o f entries on that diagonal. So, if 0 - b -- x, the entries on the " b " diagonal are b + 0, (b - 1) + 1 , . . . , 1 + (b - 1), 0 + b, amounting to b + 1 entries in all. Similarly, looking at the lower right corner o f the matrix, /f a - x + 1 --- b -< a, the entries on the " b " diagonal are x + (b - x), (x - 1) + (b - x + 1 ) , . . . , (x - ( a - b)) + (a - x), totaling a - b + 1 entries. In between, that is if x + 1 -< b -< a - x , the n u m b e r o f entries on the " b " diagonal remains constant at x + 1. Specifically the entries are b + 0 , ( b - 1 ) + 1 , . . . , (b - x ) + x . []

Example a=7, x=2

y•

0

1

N(x, b)

2

1

2 4

5

2 3

b+l

3 3

x+l

2}1 a - b + l Next let ni = ai + 1, 1 --- i -< m. We define n t x n~ matrices A~, for i = 1. . . . , m. Index the rows and columns o f At b y x~ = O, 1 , . . . , at, and b~ = O, 1 , . . . , ai, respectively, and let the (xt, b~)-entry be

N(x,, b,)--I{(Y, z): y, z'e Z, y + z = b,, O<- y < - a , - x,, 0 < - z<- xt}l. Despite its complicated definition, A~ has a remarkably simple form.

Examples

(I) For ai=4, ni=5

11111 [

A i -u-

2

2

2

2 2

3 2

2 2

1

1

1

Balanced Subdivision and Enumeration in Balanced Spheres

309

(2) F o r a i = 5 , n~=6

Ai

Lemma 12.

1

1

1

1

1

1

1

2

2

2

2

1

1

2

3

3

2

1

1

2

3

3

2

1

1

2

2

2

2

1

1

1

1

1

1

1

Ai has the following symmetries: N ( x , b~) = N ( a , - x , b,)= N ( x , a,-b,).

In addition, row x~ of the ( ta~/2J + 1) x ( [aJ2J + 1) subrnatrix in the upper left corner of Ai is 1

2

...

x~

xi+l

x~+l

-..

x;+l.

[]

Proof. The proof is a routine verification using Lemma 11.

Let AI@A2 denote the tensor product of the matrices A1 and A2. That is, AI®A2 is the nln2 x nln2 matrix consisting of rows (and columns) of nl square blocks of size n2; the block in the kth row and Ith column is A2 multiplied by the scalar in the kth row and lth column of A1, 1--
I~=

0

-.

,

.'.=

0 1

i[lo..:] I1 Lemma 13.

In the setting described above,

(i) M f t _-_( ~ =m1 A . (ii) M~ =(~"=~ C . (iii) M2=Q'r=l E~.

.

.-

,

310

L.J. Billera and K. E. Magurn

/'roof (i) The (x, b)-entry of M" is [{(Y, z):y, zeN m,y+z= b,O<-y <-a-x, O<-z<-x}l

= [IT~ N(x,, b~)=[I,%~[(x,, b,)-entry of A,] = (x, b)-entry of ~)i%1 Ai. (ii) The (x~, b~)-entry of C~ is

{I0 ifx,+b,<-a,, else, so the (x, b)-entry of @~%1C~ is

{10 ifx'+b'<-a'f°rall l<-i<-m'else. But the (x, b)-entry of M1 is

{ I if O<-b <-a - x= {

ifelseX+b<-a=(x,b).entryof@~=l C,.

(iii) The (x~, b~)-entry of E~ is {~ ifb,>-x,, else, m

so the (x, b)-entry of @~=1 El is

{~ lifb,>x, <-i<-.m forall ,else. Finally, the (x, b)-entry of M2 is {~ else.if x<-b<-a=(x, b).entry of @,%~E,.

[]

Hence the problem of establishing equality in Corollary 2 is reduced to that of showing the matrix (~i%i At)-(~t%l Ci)-(~i%l Ei) to have rank >-/(K1)/2J + 1 = [K/2], where K = I'[m=l(ai + 1) = I'I~=l ni. Theorem 14. ( ~ 7 ' : 1 A , ) - ( ~ ' = , C t ) - ( ~ = l E~) has rank"> - [KI2].

Proof. rank[~7'=l Ai-~7'=1 C ~ - ~ = l E~] = rank[(~7'.~ Ei)-l(~7'=l A,-~7'=1 Ci-~m=l E~)] = rank[(~7'=l E~-~)(~7'=~As)- (~7'=~ ET~)(~m=l C~)-Ix] = rank[~7'~l (EFIAi)-~n.l (E~-IG)- I~c] =

rank[~7'~l (E71A,) - J r

-

It]

Balanced Subdivision and Enumeration in Balanced Spheres

311

since

Qi%l E-tCi

i -,,~,~=1-~¢:~"*J,C7,1Ci,

=(~'~=l- J.., =Jrl7 .... =JK.

If K is even, - JK -- IK is ---1

-1 *°•

0

.''

-1

-1

-1

-1

0

0

.'•

0

*o,

-1

-1

and if K is odd, - J K - I K is -1

-1" *o

•

0

,°

-2

0

0

"

-1

--1

K

Whatever the case, denote this "correction" matrix by T. The p r o o f is completed by showing that the [ K / 2 ] x [ K / 2 ] submatrix in the upper left c o m e r of ~)7=~ (E~,IA~)+ T has r a n k [ K / 2 ] . Recall that E, is upper triangular with l's, so (E~) -1 is obtained from I,, by replacing row j by [row j row(j + 1)] for 1 -<-j - ni - 1. Thus for each 1 -< i -< m, E~-IAs has the following form: for 1 <-j-< [ ( n , - 1)/2], r o w j is j O's, followed by ( n , - 2 j ) - l ' s , followed by j O's; for [ ( n t - 1 ) / 2 ] < j < - n ~ - l , r o w j is - ( r o w ( r ~ - j ) ) ; row n~ consists of l's. [] Examples

(1) For as = 4, ni = 5

At =

1

1

1

1

1

2

2

2

1 1 1

2 2 1

3 2 1

2 2 1

1 1 1 1 1

,

E~IAi =

0 0 0 0

-1 0 0 1

-1 -1 1 1

1

1

1

_1!]o 0 1 1

(2) For ai = 5, ni = 6

Ai=

"1 1

1 2

1 2

1 2

1

2 2 2 1

3

3 3 2 1

1 1 .1

3 2 1

0 0 0

-1 0 0

-1 -1 0

1

0

1

I

1

I

I

1

'1 1 1 1

'

E~,1At =

-1 -1 0 1 1 1

-1 0 0 0 1 1

0 0 0 0 0 1

312

So the

L.J. Billera and K. E. Magum

[nJ2l x

In//2] submatrix in the upper left comer of

°

if ni is even, and

'.

1

0 0

°,.

0

0

-1 0

1 1

if ni is odd. Denote the [ K / 2 ] x [ K / 2 ] upper left submatrix in ~7'=~

[o

ET~A~ is

ET~Ai by S.

)

Claim. S is strictly upper triangular if K is even, and of the form "..

0

0 1

if K is odd. Recall K = 117'=~ n~, and induct on m. If m = 1, the assertion is true, as previously noted. So suppose for all m < k the result holds and let m = k The induction hypothesis says that @~=2 E71A~ is strictly upper triangular if H~=2 n~ is even, and of the form

[o

1 [0 1 0

if I]~=2 n~ is odd. Also form

0

1

E-fIA1 is strictly upper triangular if n~ is even, and of the

0

0

1

if n~ is odd. Now suppose K is even; then either nl is even, or nl is odd and Hk=2 ni is even. In the first instance, S has the form r ....

"3

L°- -

0

0""

®R=

o r

.

.

.

.

"~

LO" R I

°

e- . . . .

-t

IO.R~

Balanced Subdivision and' Enumeration

in Balanced Spheres

313

where R denotes Qk=2 EC,tA~, and the broken lines show the blocks on the diagonal and below the diagonal in S. In the second instance, S has the form

[o. ]

I. . . . .

'O'R] t. . . . . .

t

t

.J

I

".

I 1

•

• °

0

0

@R=

L ....

.1

1

L ....

P

J.f.

~0

I

where the blocks in region P consist of 0. (the upper ½(Ilk=, n,) rows of R), hence P is all O's; and Q is 1 • (the upper left comer of R, size ½(H~=2n~)). Since 1]k=2 n~ is even, Q is strictly upper triangular. Thus if K is even, S is strictly upper triangular. On the other hand, if K is odd, then nl must be odd and Nk=2 n~ must be odd. S has the form

[o

]

° . °

0

I

0

'O'R'

t" . . . .

"l

I....

,.J

t I •

I

".

r6-

®R=

]

I

r6-k] I

L--_ ~J L _ _ _ _ . . . . . . . . . . . . .

1

e

I I

.p___

,,Q I

where the blocks in P consist of 0. (the upper ½(l'Ik=2 n~+ 1) rows of R), hence P is all O's; and Q is 1. (the upper left comer of R, size ½(ilk=2 n~+ 1)). Since l-I/k=2n~ is odd, Q has the form

I 0

Thus for K odd, S has the form

"°.

0

0

1

o

] 0

0 1

and this proves the claim. Finally, let T' be the upper left submatrix of the "correction" matrix T. Recall that

[ 0] 0

'"

-1

314

L.J. Billera and K. E. Magurn

if K is even, and -1

0

... 0

-1

] -2

if K is odd. So if K is even, S + T' has the form

f0 it0 0

0

-1

j

and if K is odd, it has form

10001+10 In either event S + T' is triangular; therefore its rank is [ K / 2 ] .

6. Some Habitats of Balanced Complexes Here we look at two settings in which balanced and completely balanced complexes arise naturally. One involves stellar subdivision of geometric cellular (not necessarily simplicial) complexes, so we offer a brief description of this based on discussions in Ewald and Shephard [9] and Bayer [3]. A few definitions are called for. The cell P is a d-pyramid if P = conv(B u {v}) where B (the base of P ) is a ( d - D-cell and v (the apex of P ) is a point not contained in aff B. For r a positive integer, P is an r.fold d-pyramid with base B of dimension d - r if P is a d-pyramid with base P' where P' is an ( r - 1 ) - f o l d ( d - 1)-pyramid with base B. Ewald and Shephard's generalization differs from the subdivision of simplicial polytopes mainly in its requirement that if the cell F to be subdivided in a complex P is contained in a cell H of higher dimension, H must be a (dim H dim F)-fold pyramid with base F. The notion of link of F in P carries over intact so if a cell F meets the criterion above, lkj,F is simplicial. Since the definition of the join * of simpticial complexes applies also to cellular complexes whose affine hulls are independent affine subspaces, F may be subdivided as F' * {t} * G where F' is a proper cell of F, G is a face in IkpF, and t is a point in the relative interior of F. The d-cells in a d-complex can always be subdivided, and the following fact from [9] sets the stage for subdivisions of lower-dimensional cells. Say F is an ( r - D-cell in a complex P for some r, 1 --- r_< d - I; if all r-cells in P which contain F have been subdivided, yielding a complex P', then all the cells o f P' containing F are pyramids with base F. Thus F itself may be subdivided. So in some sense, the order of subdivision in a nonsimplicial complex proceeds by decreasing dimension. We now go on to the examples. Griinbaum [11] defines a d-polytope to be k.simplicial if every k-face of P is a simplex. When k = d - 2 , P is also called

Balanced Subdivision and Enumeration in Balanced Spheres

315

quasi-simplicial; in this case the facets of P are simplicial. For example, every 3-polytope is quasi-simplicial. If a stellar subdivision is performed on each facet of a quasi-simplicial d-polytope P, the resulting d-polytope P' is simplicial. This suggests a natural way to label the vertices of P ' so that it is balanced of type ( d - 1, 1). Give the vertices of P the label A, and assign each vertex introduced by a subdivision of a facet the label B. Then each facet of P ' will have d - 1 vertices labeled A, and 1 vertex labeled B.

Example

p

=

///

A

p, =

A

A

A

This idea generalizes to the k-simplicial case. If P is k-simplicial, its nonsimplicial faces can be subdivided to yield a simplicial polytope P'. Give the vertices of P the label 0. First subdivide all facets (simplices or not) using vertices labeled 1. Continue to subdivide all faces of a given dimension d - i, 1-< i - - - d - k - 1 , proceeding in order of decreasing dimension. The new vertices introduced in the subdivision of faces of dimension d - i are labeled i. The polytope P ' then has type (ao, a l , . . . , a a - k - 1 ) where a o = k + l and a i = l for l < - i < - d - k - 1 . The label on each vertex conveniently keeps track of the stage in the subdivisions at which the vertex appeared in the polytope. Example. Consider the 3-cube as a 1-simplicial facet of a 4-cube. The illustration shows the polytope obtained after the subdivision of the 3-face and two of the .2-faces. Note that the facets emerging are type (2, 1, 1). 0

0

2

0

0

0

316

L.J. Billera and K. E. Magurn

Since every d - p o l y t o p e is 0-simplicial, if all faces o f dimension 1 or more in P are subdivided as described above, the resulting simpticial polytope is completely balanced. In this way we can achieve a simplicial p o l y t o p e P ' which is balanced o f any type a = ( a l , . . . , a,), r_< d, where a~ is a positive integer and ~7=1 a~ = d, just by identifying labels. The question o f whether certain complexes can be completely balanced m a y be c o u c h e d in the language o f graph colorability. A simplicial complex is ncolorable if each vertex can be labeled with some integer i, 1 - i - n, so that the vertices o f any simplex have distinct labels. Thus if A is a pure simplicial d-complex, saying A is (d + 1)-colorable is the same as saying A is completely balanced. It is well k n o w n (see [2], for example) that a graph which can be e m b e d d e d in the 2-sphere S 2 is 3-colorable if and only if it is a subcomplex o f the 1-skeleton o f a triangulation o f S 2 in which every vertex has even degree. A n analog o f this result to higher dimensions was proved by G o o d m a n and Onishi [10], and independently b y Deligne, Edwards, MacPherson, and M o r g a n ( a n n o u n c e d in [8]). The general result asserts that a closed, simply connected triangulated P L n-manifold is (n + 1)-colorable if a n d only if each (n - 2 ) - s i m p l e x is a face o f an even n u m b e r o f (n - 1)-simplices. ( I n [10], only the case d = 4 is considered, but the p r o o f applies to any dimension.)

Acknowledgment We acknowledge many helpful discussions with Gil Kalai over the course of this work.

References 1. J. W. Alexander, The combinatorial theory of complexes, Ann. of Math. (2) 31 (1930), 292-320. 2. D. Barnette,. Map Coloring, Polyhedra, and the Four-Color Problem, Dolciani Mathematical Expositions No. 8, Mathematical Association of America, Washington, DC, 1983. 3. M. M. Bayer, Facial Enumeration in Polytopes, Spheres and Other Complexes, Ph.D. thesis, Cornell University, Ithaca, NY, 1983. 4. M. M. Bayer and L. J. Billera, Counting faces and chains in polytopes and posets, Contemp. Math. 34 (1984), 207-252. 5. M. M. Bayer and L. J. Biilera, Generalized Dehn-Sommerville relations for polytopes, spheres and Euledan partially ordered sets, Invent. Math. 79 (1985), 143-157. 6. L. J. Billera, Polyhedral theory and commutative algebra, in Mathematical Programming--Born, 1982, The State of the Art, (A. Bachem, M. Grftschel, and B. Korte, eds.), 57-77, Springer-Verlag, Berlin, 1983. 7. H. Bruggesser and P. Mani, Shellable decompositions of cells and spheres, Math. Scand. 29 (1971), 197-205. 8. R. D. Edwards, An amusing reformulation of the four-color problem, Notices Amer. Math. Soc. 24 (1977), A-257. 9. G. Ewald and G. C. Shephard, Stellar subdivisions of boundary complexes of convex polytopes, Math. Ann. 210 (1974), 7-16.

Balanced Subdivision and Enumeration in Balanced Spheres

317

10. J. E. Goodman and H. Onishi, Even triangulations of S 3 and the coloring of graphs, Trans. Amer. Math. Soc. 246 (1978), 501-510. 11. B. Griibaum, Convex Polytopes, Wiley-Interscience, New York, 1967. 12. D. W. Henderson, Simplicial complexes homeomorphic to proper self-subsets have free faces, in Continua, Decompositions, Manifolds, 240-242, University of Texas Press, Austin, TX, 1983. 13. V. Klee, A combinatorial analogue of Poincar6's duality theorem, Canad. J. Math. 16 (1964), 517-531. 14. C. C. MacDuffee, The Theory of Matrices, Verlag von Julius Springer, Berlin, 1933. 15. K. E. Magurn, Subdivision and Enumeration in Balanced Complexes, Ph.D. thesis, Cornell University, 1985. 16. W. S. Massey, Singular Homology Theory, Springer-Verlag, New York, 1980. 17. C. R. F. Maunder, Algebraic Topology, Van Nostrand Reinhold, London, 1970. 18. P. McMullen and G. C. Shephard, Convex Polytopes and the Upper Bound Conjecture, Cambridge University Press, Cambridge, 1971. 19. D. M. Y. Sommerville, The relations connecting the angle-sums and volume of a polytope in space of n dimensions, Proc. Roy. Soc. London Ser. A 115 (1927), 103-119. 20. R. Stanley, Cohen-Macaulay complexes in Higher Combinatorics (M. Aigner, ed.), 51-62, Reidel, Dordrecht and Boston, 1977. 21. R. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc. 249 (1979), 139-157. 22. R. Stanley, An introduction to combinatorial commutative algebra, in Enumeration and Design (D. A. Jackson and S. A. Vanstone, eds.), 3-18, Academic Press Canada, Toronto, 1984.

Received September 4, 1985, and in revised form August 14, 1986.