Kalai's squeezed three-spheres are polytopal

arXiv:math/0110240v1 [math.CO] 22 Oct 2001 Kalai’s squeezed 3-spheres are polytopal Julian Pfeifle∗ Dept. of Mathematics, MA 6-2 TU Berlin, D-10623 Berlin, Germany [email protected] October 19, 2001 Abstract In 1988, Kalai [5] extended a construction of Billera and Lee to produce many triangulated (d−1)-spheres. In fact, in view of upper bounds on the number of simplicial d-polytopes by Goodman and Pollack [2, 3], he derived that for every dimension d≥5, most of these (d−1)-spheres are not polytopal. However, for d= 4, this reasoning fails. We can now show that, as already conjectured by Kalai, all of his 3-spheres are in fact polytopal. We also give a shorter proof for Hebble and Lee’s result [4] that the dual graphs of these 4-polytopes are Hamiltonian. 1 Introduction This paper is about triangulated spheres and the question whether or not the members of a certain family of them are realizable, that is, if they arise as boundary complexes of simplicial polytopes. While for all two-dimensional spheres this is true by Steinitz’ Theorem, already one dimension higher there exist simplicial spheres that cannot be realized in a convex way. The first example for this—the so-called Br¨uckner sphere—was found by Gr¨ unbaum & Sreedharan in 1967, who realized that a certain simplicial 3-sphere on 8 vertices does not represent the combinatorial type of any 4-polytope, contrary to what Br¨ uckner originally thought. (See [11, Chapter 5] for a more thorough discussion and references.) In 1988, Kalai extended a construction by Billera and Lee, and showed that starting with d= 5, there exist many more simplicial (d−1)-spheres than simplicial d-polytopes, and that therefore, in a very strong sense, most simplicial spheres are not realizable. In contrast, it is the main goal of this paper to show that all of Kalai’s 3-spheres do arise as boundary complexes of simplicial 4-polytopes. In the remainder of this introduction, we present the context of these constructions, including the known upper resp. lower bounds for the numbers of simplicial polytopes resp. spheres. The most important invariant of a (d−1)-dimensional simplicial sphere Sis its f-vector f(S) = (f−1, f0, f1,...,fd−1), where fi=fi(S) counts the number of i-dimensional faces of S, and f−1= 1. In 1971, McMullen [7] conjectured a characterization of the f-vectors of boundary complexes of simplicial d-polytopes in terms of an encoding of f(S), the so-called g-vector. First define the h-vector h(S) = (h0, h1,...,hd) of Sby hk= k X i=0 (−1)k−id−i d−kfi−1,for k= 0,1,...,d. ∗Graduate student at the European graduate school ‘Combinatorics, Geometry, and Computation’, supported by the Deutsche Forschungsgemeinschaft, grant GRK 588/1 1 The h-vector of any simplicial sphere satisfies the Dehn-Sommerville equations hk=hd−kfor k= 0,1,...,⌊d/2⌋. Now the g-vector of Sis g(S) = (g0, g1,...,g⌊d/2⌋),where g0:= h0= 1 and gk:= hk−hk−1for k= 1,2,...,⌊d/2⌋. We say that g(S) forms an M-sequence if g0= 1 and gk−1≥∂k(gk) for k= 1,...,⌊d/2⌋, where ∂k(gk) = ak−1 k−1+ak−1−1 k−2+···+a2−1 1+a1−1 0, and the integers ak> ak−1>···> a2> a1≥0 are determined by the binomial expansion gk−1 = ak k+ak−1 k−1+···+a2 2+a1 1 of gk−1 w.r.t. k. See [11, Chapter 8] for more details. We can now state McMullen’s conjecture: Theorem 1. (g-conjecture/theorem) An integer vector g= (g0, g1, . . . , g⌊d/2⌋)is the g-vector of the boundary complex of a simplicial d-polytope Pif and only if it is an M-sequence. In the same year, 1979, Stanley [9] proved the necessity and Billera and Lee [1] the sufficiency of McMullen’s conditions. Stanley’s proof that the g-vector of any simplicial polytope is an M-sequence used the Hard Lefschetz Theorem for the cohomology of projective toric varieties, but in the meantime a simpler proof by McMullen using his polytope algebra is available. Billera and Lee invented an ingenious construction to produce, for every M-sequence g, a simplicial d-polytope with this g-vector. Very briefly, they first find a shellable ball Bas a collection of facets of a cyclic polytope C, such that the g-vector of ∂B is the given M-sequence. Then they construct a realization of Cand a point zthat sees exactly the facets in B, and obtain a realization of ∂B as a simplicial polytope by taking the vertex figure at zof conv({z} ∪ C). We next discuss Kalai’s 1988 extension of their construction, by which he built so many simplicial spheres that most of them (in a sense to be made precise below) fail to be polytopal. He achieved this by giving a rule to produce many lists Iof (d+ 1)-tuples of vertices, which span pure simplicial complexes B(I). The underlying space of every such complex turns out to be a simplicial, shellable d-ball, which he called a squeezed ball, and therefore the boundary S(I) of B(I) is a simplicial (d−1)-sphere, a squeezed sphere.Lee shows in [6] that Kalai’s squeezed spheres are shellable. Let s(d, n) denote the number of simplicial (d−1)-spheres, sq(d, n) the number of squeezed (d−1)-spheres, and c(d, n) the number of combinatorial types of simplicial d-polytopes with n labeled vertices. Goodman and Pollack [2, 3] derive the upper bound log c(d, n)≤d(d+ 1)nlog n(1) using a theorem of Milnor that bounds the sum of the Betti numbers of real algebraic varieties, while Kalai’s squeezed spheres provide the following lower bound for s(d, n): log s(d, n)≥log sq(d, n)≥1 (n−d)(d+ 1)n− ⌊(d+ 2)/2⌋ ⌊(d+ 1)/2⌋ = Ω(n⌊(d+1)/2⌋−1) for fixed d. These bounds reveal that limn→∞ c(d, n)/sq(d, n) = 0 for d≥5, which means that for d≥5 most of Kalai’s spheres are not polytopal—there are simply too many of them. However, we learn nothing for d≤4: We will prove in Proposition 1 below that sq(4, n)≤2n−5n! for n≥5, which is strictly less than the bound from (1) for all n≥5. The rest of the paper is organized as follows: In Section 2, we collect some facts about cyclic polytopes, an essential ingredient of our proof. In Section 3, we first present the details of Kalai’s construction, and then show how to realize any of his 3-spheres as boundary complexes of simplicial 4-polytopes (Theorem 2). Finally, Section 4 uses the pictures constructed in Section 3 to give a shorter proof of Hebble and Lee’s result that the dual graphs of squeezed 3-spheres are Hamiltonian. 2 2 Some facts on cyclic polytopes The convex hull of ndistinct points on the moment curve µd:t7→ (t, t2,...,td) in Rdis called a d-dimensional cyclic polytope with nvertices. The combinatorial type of this polytope is independent of the choice of the npoints on the moment curve, and so one can talk about the cyclic polytope Cd(n). In fact, any d-dimensional order dcurve also gives rise to the same combinatorial types of polytopes. We switch from dand nto d+1 and n+1, and consider a set X={x0=µ(t0),...,xn=µ(tn)} of n+ 1 distinct points on the moment curve µd+1 =: µ, ordered by their first coordinates. For any f⊂ {0,1,...,n}, write Fffor the subset of Xindexed by f, and i(F) for the indices of a subset Fof X. The supporting hyperplane H(F) of a (d+ 1)-subset F⊂Xis given by H(F) = {x∈Rd+1 :γ(F)·x=−γ0(F)},where γ(F) = (γ1(F),...,γd+1(F)) ∈Rd+1 and γ0(F)∈Rare defined by 0 = Y i∈i(F) (t−ti) = d+1 X j=0 γj(F)tj=γ0(F) + γ(F)·µ(t).(2) Observe that γd+1(F) = 1; we say that γ(F)points upwards. Gale’s evenness criterion tells us which (d+ 1)-subsets Fof Xare vertex sets of facets of the cyclic polytope C= conv(X): For any i, j ∈ {0,1,...,n} \ i(F), the number of elements of i(F) between iand jmust be even. Define the end set Wend of Ff⊂Xto be the right-most contiguous block {rf+1,...,max f} of the indices fof F, where rf= max{i∈N:i < max f, i /∈f}. Let Fbe a facet of Cand take xj=µ(tj)∈X\F. If the cardinality of the end set of Fis odd, we get Qi∈i(F)(tj−ti)<0 because j /∈i(F), and therefore γ(F)·xj<−γ0(F). Since γd+1(F) = 1, we conclude that the whole cyclic polytope Cis below F, and call Fan upper facet of C. If #Wend is even, we analogously call Falower facet of C. Finally, define an outer normal vector α(F) of any facet Fof Cby α(F) = γ(F) resp. α(F) = −γ(F) if Fis an upper resp. lower facet of C, and set α0(F) = −γ0(F) resp. α0(F) = γ0(F). By this, we obtain C⊂ {x∈Rd+1 :α(F)·x≤α0(F)} for all facets Fof C. 3 Realizing Kalai’s 3-spheres 3.1 Kalai’s idea First define a partial order on N d+1by {i1, i2,...,id+1}< {j1, j2, . . . , jd+1}<if ik≤jkfor every k= 1,...,d+ 1. Here the notation A={a1,...,ar}<means that the elements of the set A are listed in increasing order. For the standard poset terminology used in the following, see [10]. For an odd integer d > 0 and n∈N, let Fd(n) be the collection of (d+ 1)-subsets of [n] := {1,2,...,n}of the form {i1, i1+ 1} ∪ {i2, i2+ 1} ∪ · · · ∪ {ie, ie+ 1}, where e= (d+ 1)/2, i1≥1, ie< n, and ij+1 ≥ij+ 2 for all relevant j. Let I′be an initial set (order ideal) of Fd(n) with respect to the partial order on N d+1. Informally, f′g′for f′, g′∈ Fd(n) if f′arises from g′ by pushing some elements in g′to the left. For even d > 0, put Fd(n) = {{0} ∪ f′:f′∈ Fd−1(n)}=: 0 ∗ Fd−1(n) with the induced partial order, and set I:= 0 ∗I′. Finally, let B(I) be the simplicial complex (the squeezed d-ball) spanned by I, denote the boundary complex of B(I) by S(I) (the squeezed (d−1)-sphere), and do the same for I′. 3.2 The structure of 3-balls To specialize Kalai’s construction to d= 4, we first study squeezed 3-balls. Take n≥4 in N, write (i, j) for an element {i, i + 1, j, j + 1} ⊂ [n] of F3(n), and define the gap of (i, j)∈ F3(n) 3 to be the number j−i−2 of integers between i+ 1 and j. From the fact that any two elements of F3(n) with the same gap are translates of each other and therefore -comparable, we conclude that any -antichain in F3(n) can be linearly ordered by increasing gap, and denote this order by <. We remark that the difference between the gaps of any two elements in a -antichain must be at least 2, as otherwise the two elements would be -comparable. In particular, the maximal number of elements of a -antichain in F3(n) is ⌈(n−3)/2⌉. Any order ideal I′⊂ F3(n) for n∈Nis generated by the set G′={g′ 1, g′ 2,...,g′ r}<of its maximal elements, for some r≤ ⌈(n−3)/2⌉. By our discussion, the g′ k= (ik, jk) satisfy (1) jk≥ik+ 2 for k= 1,...,r, and (2) ik> ik+1 and jk< jk+1 for k= 1,...,r−1. As an example, let I′be the ideal generated by G′={(9,11),(8,12),(5,14),(2,17)}<: 1 12 11109 82 31514 17 185 6 13 Note that if g′<h′∈G′, then g′is nested inside h′(possibly with overlap). From Figure 1 below, we will read off the structure of the 3-ball B(I′) generated by G′, and its boundary S(I′). Now put F4(n) = 0 ∗ F3(n) with the induced partial order, and I= 0 ∗I′. The 4-ball B(I) spanned by Iis a cone over the 3-ball B(I′), whose boundary complex is the squeezed 3-sphere S(I). Proposition 1. There are at most 2n−4(n+1)! squeezed 3-spheres with n+1 ≥5labeled vertices. In particular, log sq(4, n) = Θ(nlog n). Proof. By [5, Prop. 3.3], distinct 4-balls B(I) whose vertices are labeled according to their construction give rise to distinct 3-spheres S(I) labeled in this way, and distinct initial sets I⊂ F4(n) obviously induce distinct such 4-balls. Every initial set Iis of the form 0 ∗I′for a unique order ideal I′⊂ F3(n). Therefore, by relabeling vertices, sq(4, n + 1) is at most (n+ 1)! times the number of distinct order ideals in F3(n), depending on the combinatorial symmetries of S(I). By Figure 1, every such order ideal can be represented by a lattice path of length n−4 taking steps only in the positive ior negative j-directions, and starting at (i, j) = (1, n −1). There are 2n−4 of these, and they all give rise to distinct ideals. 2 3.3 A bird’s-eye view of the realization construction Observe that by Gale’s Evenness Criterion, every f∈Icorresponds to a lower facet Ffof a cyclic polytope. By adapting the ideas of Billera and Lee, we will now realize any S(I) as the boundary complex of a 4-polytope Pby appropriately realizing a cyclic 5-polytope C, and choosing a viewpoint vclose to the negative e5-axis that sees exactly the facets of Cin B(I). The convex 4-polytope Pis then the vertex figure at vof conv(C∪ {v}), and S(I) its boundary. Specifically, let µ=µ5:R→R5,t7→ (t, t2,...,t5) be the moment curve in dimension 5. Given an order ideal I= 0 ∗I′in F4(n) where n= max SI, we will execute the following steps: 1. Choose N′>0 and place 0 = t0< t1<···< tn∈R≥0such that Y i∈f\{0} ti< N′for all f∈I, and Y i∈f\{0} ti> N′for all f∈ F4(n)\I(S1) Solutions for (S1) exist with t1>0 arbitrarily small. We will find a solution for this system of inequalities by processing the elements of E′=G′∪H′in <-order, where G′is the set of -maximal elements of I′, and H′is the set of -minimal elements of F3(n)\I′. 4 1 2 3 4 1 2 3 4 5 6 2 3 4 5 1 2 4 5 2 3 5 6 1 2 5 6 3 4 5 6 4 5 i 3 1 2 3 5 8 9 n= 18 14 17 j 12 11 345 234 123 256 3456 1256 2345 1245 1234 125 134 2356 235 356 245 145 124 156 Figure 1: The Kalai poset F3(18). The shaded circles are the facets of the 3-ball B(I′) with generators G′={(9,11),(8,12),(5,14),(2,17)}<. The minimal elements H′of F3(18)\I′are marked by ∇’s, and <orders the elements of E′=G′∪H′from left to right (see Observation 1). Straight lines between facets correspond to ≺-covering relations between elements of I′, and straight and curved lines together to inner ridges of B(I′). The small circles are the facets of S(I′) = ∂B(I′). The set of facets of the Kalai sphere S(I) is the union of B(I′) and 0 ∗S(I′). 5 2. Make sure that the viewpoint to be defined will not see any upper facets of C=C5(n+1) = conv{0, µ(t1), µ(t2), . . . , µ(tn)}that contain 0, by choosing t1>0 so small that t1tn−2tn−1tn< N′.(S2) 3. Choose ε, with 0 < ε < t1, so small that for all e, f ∈ F4(n), e≺f=⇒γ(Fe)·µ(ε)< γ(Ff)·µ(ε).(S3) 4. Choose ε > 0 even smaller, if necessary, such that the viewpoint v:= µ(ε)−εN′e5satisfies α(F)·v > α0(F) for fF∈I, α(F)·v < α0(F) for all lower facets Fof Csuch that fF/∈I, (S4) α(F)·v < α0(F) for all upper facets Fof C, where α(F) is the outer normal vector of Fwe defined at the end of Section 2. We conclude that vsees exactly the facets of Cin B(I), and obtain S(I) as above. 3.4 How to realize Kalai’s 3-spheres We will now give the details of the construction and prove the following theorem. Theorem 2. Every squeezed 3-sphere S(I)given by an order ideal Iin the poset (F4(n),)with n≥max SIcan be realized as the boundary complex of a simplicial, convex 4-polytope. Remark 1. The construction shows the stronger result that every squeezed 4-ball B(I) can be realized as a regular triangulation of a convex 4-polytope. To prove Theorem 2, given an ideal I⊂ F4(n), we may assume that n= max SIsince F4(n)⊆ F4(n′) for n≤n′. By definition, every order ideal I⊂ F4(n) has the form I= 0∗I′, where I′=hG′i ⊂ F3(n) is generated by its maximal elements G′={g′ 1, g′ 2, . . . , g′ r}with g′ k= (ik, jk). Choose N′>0, introduce nvariable points 0 < t1< t2<···< tnin R>0, and consider the set H′ of -minimal elements of F3(n)\I′. Observation 1. Consider any two consecutive elements e′= (i, j)<·f′= (k, ℓ)of a <-ordered -antichain G′of F3(n). Then the unique ≺-minimal element m′in F3(n)\ hG′iwith gap(e′)< gap(m′)<gap(f′)exists and is m′= (k+ 1, j + 1). In particular, the number of ≺-minimal elements in F3(n)\ hG′iis no greater than ⌊(n−3)/2⌋.2 Sketch of proof. The first statement follows by inspection of Figure 1. For the second assertion, note that the set H′has maximal cardinality if G′={(i, n −i) : i= 1,2, . . . , ⌈(n−3)/2⌉}.2 Using Observation 1, we linearly order E′=G′∪H′by <, see Figure 1. To carry out Step 1 of our program, first choose some small δ > 0. Our goal is to place the t’s in R>0such that Y i∈g′ ti=N′−δfor g′∈G′and Y i∈h′ ti=N′+δfor h′∈H′.(S1′) Observation 2. The cardinality of E′=G′∪ ·H′is at most n−3. In particular, there are fewer equalities in (S1′)than there are variables. 6 Proof. Because n= max SI, the largest element of (E′,<) is in G′. Using Observation 1 again, #E′= #G′+ #H′≤n−3 2+n−3 2=n−3, which proves Observation 2. 2 We now begin the construction by placing the t’s corresponding to the <-smallest element of E′in such a way in R>0that (S1′) is satisfied. This is clearly possible. The general step of constructing a solution to (S1′) is based on the following lemma. Lemma 1. Let e′= (i, j)<·f′= (k, ℓ)be two consecutive elements of E′. (a) If e′∈G′and f′∈H′, then 0< k ≤iand ℓ=j+ 1. If e′∈H′and f′∈G′, then k=i−1 and j≤ℓ < n. (See Figure 1.) (b) Suppose that the {ti}i∈e′have been placed already, but not all {tj}j∈f′. Then these latter t’s may be placed in such a way in R>0that 0< tk< tk+1 < tℓ< tℓ+1, and the equality tktk+1tℓtℓ+1 =M(3) is satisfied, where M:= N′−δif f′∈G′and M:= N′+δif f′∈H′. Sketch of proof for (b). Suppose that e′∈G′and f′∈H′. We then have the following situation: tkti tk+1 ti+1 tjtj+1 =tℓtℓ+1 cc0 b0 ba It is straightforward to verify that for any 0 < k ≤i, the points a, b, c may be placed in such a way that 0 < a < b < b0< c0< c and abc0c=N′+δ. Similarly, if e′∈H′and f′∈G′, a0bb0 tℓ tj ca tktk+1 =titi+1 tj+1 tℓ+1 for any j≤ℓ < n we may place a, b, c such that 0 < a < a0< b0< b < c and aa0bc =N′−δ.2 We now complete Step 1 by applying Lemma 1 to all members of E′in <-order. The definition of tells us that because the f′∈E′satisfy (S1′), in fact all f∈ F4(n) satisfy the system (S1). If in Step 1 we encountered some e′∈E′with 1 ∈e′, then necessarily e′={1,2, n−1, n} ∈ G′, which imposed the inequality t1t2tn−1tn< N′. This inequality in turn remains satisfied if we choose t1even small enough to verify (S2). If 1 /∈e′for all e′∈E′, we are free to do the same. We have completed Step 2, and place any remaining unassigned t’s such that 0 = t0< t1<···< tn. Observation 3. (a) γ0(Ff) = 0 for any 5-element subset f⊂ {0,1, . . . , n}that contains 0. (b) For all choices of t1<··· < tn, one can find ε > 0small enough such that the implication (S3) holds for all f, g ∈ F4(n). Proof of (b). The definition (2) of the γ’s implies that for f={0, s1,...,s4}, γ(Ff)·µ(ε) = ε(ε−s1)···(ε−s4) = εs1s2s3s4±o(ε).(4) This means that γ(Ff)·µ(ε)< γ(Fg)·µ(ε) by definition of ≺, for εsmall enough. 2 7 Take 0 < ε < t1as in Observation 3(b), tentatively set z:= µ(ε), and let f∈ F4(n). If f∈I, there exists some g∈G:= 0 ∗G′with fg, and by (4), we have γ(Ff)·z≤γ(Fg)·z=εY i∈g\{0} ti+O(ε2) = ε(N′−δ)±o(ε). If f /∈I, then there is some h∈H:= 0 ∗H′with fh, and we obtain in a similar way that γ(Ff)·z≥ε(N′+δ)±o(ε). Thus, we finally choose 0 < ε < t1so small that with z:= µ(ε) and N:= εN′, we have γ(Ff)·z < N for f∈I, and γ(Ff)·z > N for f /∈I. Step 3 is now complete. We proceed to verify that v:= µ(ε)−εN′e5=z−Ne5satisfies the inequalities (S4). For this, recall that all Ffwith f∈ F4(n) satisfy Gale’s Evenness Criterion, which means that F4(n) is exactly the set of lower facets of the cyclic polytope C= conv(X) that contain x0= 0. However, any F⊂Xof odd cardinality satisfying Gale’s Evenness Criterion with even end-set must contain 0, and we conclude that F4(n) is in fact the set of all lower facets of C. Recall from Section 2 that α(F) = γ(F) and α0(F) = −γ0(F) if Fis an upper facet of C, and that α(F) = −γ(F) and α0(F) = γ0(F) if Fis a lower facet of C. We and discuss all facets Ffof Cin turn: Lower facets of C: •If f∈I⊂ F4(n), then by construction γ(Ff)·z < N, and this implies γ(Ff)·v < 0 (remember that γ5(F) = 1 for all F) and α(Ff)·v > 0 = α0(Ff), which means that Ffis visible from v. •If f∈ F4(n)\I, we conclude from γ(Ff)·z > N that α(Ff)·v < 0 = α0(Ff), which says that Ffis not visible from v. Upper facets of C: •If 0 6∈ f={s1,...,s5}, then (2) and ε < t1imply γ(Ff)·z+γ0(Ff) = Q5 i=1(ε−si)<0, and α(Ff)·v=γ(Ff)·v=γ(Ff)·z−N < −γ0(Ff)−N < −γ0(Ff) = α0(Ff). •If 0 ∈f, then γ0(Ff) = 0 and f={0,1} ∪ {i, i + 1} ∪ {n}with 2 ≤i≤n−2. By inequality (S2) and the definition of ≺, we conclude that necessarily γ(Ff)·z < N and α(Ff)·v=γ(Ff)·z−N < 0 = α0(Ff). We have verified the inequalities (S4) and completed the proof of Theorem 2. 2 Remark 2. A referee has suggested to extend this construction to boundaries of more general even-dimensional squeezed balls. However, so far we have only been able to realize odd-dimensional squeezed spheres directly modeled on the 3-dimensional ones, and leave this as an open problem. 4 A shorter proof that squeezed 3-spheres are Hamiltonian In 1973, Barnette [8] conjectured that all simple 4-polytopes admit a Hamiltonian circuit. In [4], Hebble and Lee prove that squeezed 3-spheres are (dual) Hamiltonian by explicitly constructing a Hamiltonian circuit in the dual graph; however, their proof goes through extensive case analysis. A referee has suggested that it might be possible to obtain a simpler proof of this result. In this section, we follow his or her suggestion and obtain a “proof by picture” with fewer case distinctions, which moreover only depend on parity conditions. 8 Theorem 3. (Hebble and Lee, 2000 [4]) The dual graph of any Kalai 4-polytope S(I)admits a Hamiltonian circuit. In particular, the polars of these 4-polytopes satisfy Barnette’s conjecture. Proof. Recall from Section 3.2 that the set of facets of S(I) is B(I′)∪(0 ∗S(I′)). We continue to write (i, j) = {i, i + 1, j, j + 1}for facets of S(I) in B(I′), and introduce the notation (i+1 2, j) := {0, i + 1, j, j + 1}and (i, j +1 2) := {0, i, i + 1, j + 1}for facets of S(I) in 0 ∗S(I′). Also, recall from Section 3.2 the definition of the order relations and <, and number the set G′of -maximal elements (ik, jk) of B(I′) in ascending <-order, starting with k= 1. We start our Hamiltonian circuit in the dual graph of S(I) at the facet (i0, j0) = (1,3) = {1,2,3,4} ∈ B(I′). While walking through the other facets of B(I′), we will also pick up the facets of the form (i+1 2, j) and (i, j +1 2) with i, j ≥1 of S(I′), and then return to (1,3) via the set of facets {(0, j) : 2 ≤j≤n−1}. We will also use the difference operators ∆jk=jk+1 −jk and ∆ik=ik+1 −ik. In our circuit, we repeatedly go through certain steps, and in the figures we will mark the end of one step and the beginning of the next by a square. In all steps, if all facets in G′are processed, go to step Down (and then to Finish). 1. Over the top: Start at (i0, j0) = (1,3). If j1−j0is odd, continue as in Figure 2(a). If j1−j0 is even, proceed as in Figure 2(b). In both cases, go on until (i1+1 2, j1). Set k= 1, and go to step Down. T i jj i1 i1 i2i2 j1 j1 (i0, j0) (a) j1−j0odd (b) j1−j0even Figure 2: Steps Over the top and Down. The circled facet is (i1, j1), the upper 2represents (i1+1 2, j1), and the lower 2is (i2+1 2, j1+ 1). 2. Down: If there are no more generators to be processed, go down along the facets {(iℓ, jk+1 2) : ℓ=k, k−1,...,1}and continue with step Finish. Otherwise, if ∆ik>0, continue downwards as in Figure 2 until (ik+1 +1 2, jk+ 1). If ik+1 =ik, do nothing. In both cases, increment k by 1, and continue to step Across. 3. Across: If ∆jkis even, continue as in Figure 3(a). If ∆jkis odd and not 1 and ik+1 −i0is even, continue as in Figure 3(b); if ∆jk6= 1 and ik+1 −i0are both odd, as in Figure 3(c). If ∆jk= 1 and ∆ik+1 is even, proceed as in Figure 4(a), if ∆ik+1 is odd, as in Figure 4(b). In any case, increment kby one, and repeat from step Down or Across as necessary, depending on whether the facet surrounded by a dashed circle in Figure 4 is in Gor not. 4. Finish: Now the only thing left to do is to return to (1,3) via the set of facets {(0, j) : n−1≥j≥2}, as in Figure 5. This completes the proof of Theorem 3. 2 9