Prodsimplicial-neighborly polytopes

PRODSIMPLICIAL-NEIGHBORLY POLYTOPES BENJAMIN MATSCHKE, JULIAN PFEIFLE, AND VINCENT PILAUD Abstract. We introduce PSN polytopes whose k-skeleton is combinatorially equivalent to that of a product of rsimplices. They simultaneously generalize both neighborly and neighborly cubical polytopes. We construct PSN polytopes by three different methods, the most versatile of which is an extension of Sanyal & Ziegler’s “projecting deformed products” construction to products of arbitrary simple polytopes. For general rand k, the lowest dimension we achieve is 2k+r+1. Using topological obstructions similar to those introduced by Sanyal to bound the number of vertices of Minkowski sums, we show that this dimension is minimal if we moreover require the PSN polytope to be obtained as a projection of a polytope combinatorially equivalent to the product of rsimplices, when the sum of their dimensions is at least 2k. 1. Introduction 1.1. Definitions. Let 4ndenote the n-dimensional simplex. For any tuple n= (n1, . . . , nr) of integers, we denote by 4nthe product of simplices 4n1× · · · × 4nr. This is a polytope of dimension Pni, whose non-empty faces are obtained as products of non-empty faces of the simplices 4n1, . . . , 4nr. For example, Figure 1 represents the graphs of 4i× 46, for i∈ {1,2,3}. Figure 1. The graphs of the products 4(i,6) =4i× 46, for i∈ {1,2,3}. We are interested in polytopes with the same “initial” structure as these products. Definition 1.1. Let k≥0and n= (n1, . . . , nr), with r≥1and ni≥1for all i. A polytope is (k, n)-prodsimplicial-neighborly — or (k, n)-PSN for short — if its k-skeleton is combinatorially equivalent to that of 4n=4n1× · · · × 4nr. Benjamin Matschke was supported by DFG research group Polyhedral Surfaces and by Deutsche Telekom Stiftung. Julian Pfeifle was supported by grants MTM2006-01267 and MTM2008-03020 from the Spanish Ministry of Education and Science and 2009SGR1040 from the Generalitat de Catalunya. Vincent Pilaud was partially supported by grant MTM2008-04699-C03-02 of the Spanish Ministry of Education and Science. 1 2 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD This definition is essentially motivated by two particular classes of PSN polytopes: (1) neighborly polytopes arise when r= 1; (2) neighborly cubical polytopes [JS07, SZ09] arise when n= (1,1, . . . , 1). Remark 1.2. In the literature, a polytope is k-neighborly if any subset of at most kof its vertices forms a face. Observe that such a polytope is (k−1, n)-PSN with our notation. Obviously, the product 4nitself is a (k, n)-PSN polytope of dimension Pni. We are naturally interested in finding (k, n)-PSN polytopes in smaller dimensions. For example, the cyclic polytope C2k+2(n+ 1) is a (k, n)-PSN polytope in dimension 2k+ 2. We denote by δ(k, n) the smallest possible dimension that a (k, n)-PSN polytope can have. PSN polytopes can be obtained by projecting the product 4n, or a combinatorially equivalent polytope, onto a smaller subspace. For example, the cyclic polytope C2k+2(n+ 1) (just like any polytope with n+ 1 vertices) can be seen as a projection of the simplex 4nto R2k+2. Definition 1.3. A(k, n)-PSN polytope is (k, n)-projected-prodsimplicial-neighborly — or (k, n)-PPSN for short — if it is a projection of a polytope combinatorially equivalent to 4n. We denote by δpr(k, n) the smallest possible dimension of a (k, n)-PPSN polytope. 1.2. Outline and main results. The present paper may be naturally divided into two parts. In the first part, we present three methods for constructing low-dimensional PPSN polytopes: (1) Reflections of cyclic polytopes; (2) Minkowski sums of cyclic polytopes; (3) Deformed Product constructions in the spirit of Sanyal & Ziegler [Zie04, SZ09]. The second part derives topological obstructions for the existence of such objects, using techniques developed by Sanyal in [San09] (see also [RS09]) to bound the number of vertices of Minkowski sums. In view of these obstructions, our constructions in the first part turn out to be optimal for a wide range of parameters. Constructions. Our first non-trivial example is a (k, (1, n))-PSN polytope in dimension 2k+ 2, obtained by reflecting the cyclic polytope C2k+2(n+ 1) in a well-chosen hyperplane: Proposition 2.3. For any k≥0,n≥2k+ 2 and λ∈Rsufficiently large, the polytope P:= conv (ti, . . . , t2k+2 i)T|i∈[n+ 1]∪(ti, . . . , t2k+1 i, λ −t2k+2 i)T|i∈[n+ 1] is a (k, (1, n))-PSN polytope of dimension 2k+ 2. For example, this provides us with a 4-dimensional polytope whose graph is the cartesian product K2×Kn, for any n≥3. Next, forming a well-chosen Minkowski sum of cyclic polytopes yields explicit coordinates for (k, n)-PPSN polytopes: Theorem 2.6. Let k≥0and n= (n1, . . . , nr)with r≥1and ni≥1for all i. There exist index sets I1, . . . , Ir⊂R, with |Ii|=nifor all i, such that the polytope P:= conv{wa1,...,ar|(a1, . . . , ar)∈I1× · · · × Ir} ⊂ R2k+r+1 is (k, n)-PPSN, where wa1,...,ar:= a1, . . . , ar,Pi∈[r]a2 i, . . . , Pi∈[r]a2k+2 iT.Consequently, δ(k, n)≤δpr(k, n)≤2k+r+ 1. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 3 For r= 1 we recover neighborly polytopes. Finally, we extend Sanyal & Ziegler’s technique of “projecting deformed products of polygons” [Zie04, SZ09] to products of arbitrary simple polytopes: we suitably project a suitable polytope combinatorially equivalent to a given product of simple polytopes in such a way as to preserve its complete k-skeleton. More concretely, we describe how to use colorings of the graphs of the polar polytopes of the factors in the product to raise the dimension of the preserved skeleton. The basic version of this technique yields the following result: Proposition 3.4. Let P1, . . . , Prbe simple polytopes. For each polytope Pi, denote by ni its dimension, by miits number of facets, and by χi:= χ(sk1P4 i)the chromatic number of the graph of its polar polytope P4 i. For a fixed integer d≤n, let tbe maximal such that Pt i=1 ni≤d. Then there exists a d-dimensional polytope whose k-skeleton is combinatorially equivalent to that of the product P1× · · · × Pras soon as 0≤k≤ r X i=1 (ni−mi) + t X i=1 (mi−χi) + $1 2 d−1 + t X i=1 (χi−ni)!%. A family of polytopes that minimize the last summand are products of even polytopes (all 2-dimensional faces have an even number of vertices). See Example 3.5 for the details, and the end of Section 3.1 for extensions of this technique. Specializing the factors to simplices provides another construction of PPSN polytopes. When some of these simplices are small compared to k, this technique in fact yields our best examples of PPSN polytopes: Theorem 3.8. For any k≥0and n= (n1, . . . , nr)with 1 = n1=· · · =ns< ns+1 ≤ · · · ≤ nr, δpr(k, n)≤     2(k+r)−s−tif 3s≤2k+ 2r, 2(k+r−s)+1 if 3s= 2k+ 2r+ 1, 2(k+r−s+ 1) if 3s≥2k+ 2r+ 2, where t∈ {s, . . . , r}is maximal such that 3s+Pt i=s+1(ni+ 1) ≤2k+ 2r. If ni= 1 for all i, we recover the neighborly cubical polytopes of [SZ09]. Obstructions. In order to derive lower bounds on the minimal dimension δpr(k, n) that a (k, n)-PPSN polytope can have, we apply and extend a method due to Sanyal [San09]. For any projection which preserves the k-skeleton of 4n, we construct via Gale duality a simplicial complex guaranted to be embeddable in a certain dimension. The argument is then a topological obstruction based on Sarkaria’s criterion for the embeddability of a simplicial complex in terms of colorings of Kneser graphs [Mat03]. We obtain the following result: Corollary 4.13. Let n= (n1, . . . , nr)with 1 = n1=· · · =ns< ns+1 ≤ · · · ≤ nr. Then (1) If 0≤k≤ r X i=s+1 ni−2 2+ max 0,s−1 2, then δpr(k, n)≥2k+r−s+ 1. (2) If k≥1 2Pinithen δpr(k, n)≥Pini. 4 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD In particular, the upper and lower bounds provided by Theorem 2.6 and Corollary 4.13 match over a wide range of parameters: Theorem 1.4. For any n= (n1, . . . , nr)with r≥1and ni≥2for all i, and for any ksuch that 0≤k≤Pi∈[r]ni−2 2, the smallest (k, n)-PPSN polytope has dimension exactly 2k+r+1. In other words: δpr(k, n) = 2k+r+ 1. Remark 1.5. During the final stages of completing this paper, we learned that R¨orig and Sanyal [San08, R¨or08, RS09] also applied Sanyal’s topological obstruction method to derive lower bounds on the target dimension of a projection preserving skeleta of different kind of products (products of polygons, products of simplices, and wedge products of polytopes). In particular, for a product ∆n× · · · × ∆nof ridentical simplices, r≥2, they obtain our Theorem 4.9 and a result [RS09, Theorem 4.5] that is only slightly weaker than Theorem 4.12 in this setting (compare with Sections 4.5 and 4.6). 2. Constructions from cyclic polytopes Let t7→ µd(t) := (t, t2, . . . , td)Tbe the moment curve in Rd,t1< t2<· · · < tnbe ndistinct real numbers and Cd(n) := conv{µd(ti)|i∈[n]}denote the cyclic polytope in its realization on the moment curve. We refer to [Zie95, Theorem 0.7] and [dLRS, Corollary 6.1.9] for combinatorial properties of Cd(n), in particular Gale’s Evenness Criterion which characterizes the index sets of upper and lower facets of Cd(n). Cyclic polytopes yield our first examples of PSN polytopes: Example 2.1. For any integers k≥0 and n≥2k+ 2, the cyclic polytope C2k+2(n+ 1) is (k, n)-PPSN. Example 2.2. For any k≥0 and n= (n1, . . . , nr) with r≥1 and ni≥1 for all i, define I:= {i∈[r]|ni≥2k+ 3}. Then the product Y i∈I C2k+2(ni+ 1) ×Y i/∈I 4ni is a (k, n)-PPSN polytope of dimension (2k+ 2)|I|+Pi/∈Ini(which is smaller than Pni when Iis not empty). Consequently, δ(k, n)≤δpr(k, n)≤(2k+ 2)|I|+X i/∈I ni. 2.1. Reflections of cyclic polytopes. Our next example deals with the special case of the product 41× 4nof a segment by a simplex. Using products of cyclic polytopes as in Example 2.2, we can realize the k-skeleton of this polytope in dimension 2k+3. We can lower this dimension by 1 by reflecting the cyclic polytope C2k+2(n+1) in a well-chosen hyperplane: Proposition 2.3. For any k≥0,n≥2k+ 2 and λ∈Rsufficiently large, the polytope P:= conv (ti, . . . , t2k+2 i)T|i∈[n+ 1]∪(ti, . . . , t2k+1 i, λ −t2k+2 i)T|i∈[n+ 1] is a (k, (1, n))-PSN polytope of dimension 2k+ 2. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 5 Proof. The polytope Pis obtained as the convex hull of two copies of the cyclic polytope C2k+2(n+ 1). The first one Q:= conv{µ2k+2(ti)|i∈[n+ 1]}lies on the moment curve µd, while the second one is obtained as a reflection of Qwith respect to a hyperplane that is orthogonal to the last coordinate vector u2k+2 and sufficiently far away. During this process, (1) we destroy all the faces of Qonly contained in upper facets of Q; (2) we create prisms over faces of Qthat lie in at least one upper and one lower facet of Q. In other words, we create prisms over the faces of Qstrictly preserved under the orthogonal projection π:R2k+2 →R2k+1 with kernel Ru2k+2. The projected polytope π(Q) is nothing but the cyclic polytope C2k+1(n+ 1). Since this polytope is k-neighborly, any (≤k−1)-face of Qis strictly preserved by π, and thus, we take a prism over all (≤k−1)-faces of Q. Thus, in order to complete the proof that the k-skeleton of Pis that of 41× 4n, it is enough to show that any k-face of Qremains in P. This is obviously the case if this k-face is also a k-face of C2k+1(n+ 1), and follows from the next combinatorial lemma otherwise.  Lemma 2.4. Ak-face of C2k+2(n+1) which is not a k-face of C2k+1(n+1) is only contained in lower facets of C2k+2(n+ 1). Proof. Let F⊂[n+ 1] be a k-face of C2k+2(n+ 1) that is contained in at least one upper facet G⊂[n+ 1] of C2k+2(n+ 1). Then, (1) if n+ 1 ∈GrF, then Gr{n+ 1}is a facet of C2k+1(n+ 1) containing F. (2) otherwise, n+ 1 ∈F, and F0:= Fr{n+ 1}has only kelements. Thus, F0is a face of C2k(n), and can be completed to a facet of C2k(n). Adding the index n+ 1 back to this facet, we obtain a facet of C2k+1(n+ 1) containing F. In both cases, we have shown that Fis a k-face of C2k+1(n+ 1).  2.2. Minkowski sums of cyclic polytopes. Our next examples are Minkowski sums of cyclic polytopes. We first describe an easy construction that avoids all technicalities, but only yields (k, n)-PPSN polytopes in dimension 2k+ 2r. After that, we show how to reduce the dimension to 2k+r+ 1, which according to Corollary 4.13 is best possible for large ni’s. Proposition 2.5. Let k≥0and n= (n1, . . . , nr)with r≥1and ni≥1for all i. For any pairwise disjoint index sets I1, . . . , Ir⊂R, with |Ii|=nifor all i, the polytope P:= convva1,...,ar|(a1, . . . , ar)∈I1× · · · × Ir⊂R2k+2r is (k, n)-PPSN, where va1,...,ar:=  X i∈[r] ai,X i∈[r] a2 i, . . . , X i∈[r] a2k+2r i  T ∈R2k+2r. Proof. The vertex set of 4nis indexed by I1× · · · × Ir. Let A=A1× · · · × Ar⊂I1× · · · × Ir define a k-face of 4n. Consider the polynomial f(t) := Y i∈[r]Y a∈Ai (t−a)2= 2k+2r X j=0 cjtj. Since Aindexes a k-face of 4n, we know that P|Ai|=k+r, so that the degree of f(t) is indeed 2k+ 2r. Since f(t)≥0, and equality holds if and only if t∈Si∈[r]Ai, the inner 6 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD product (c1, . . . , c2k+2r)·va1,...,arequals (c1, . . . , c2k+2r)  Pi∈[r]ai . . . Pi∈[r]a2k+2r i   =X i∈[r] 2k+2r X j=1 cjaj i=X i∈[r]f(ai)−c0≥ −rc0, with equality if and only if (a1, . . . , ar)∈A. Thus, Aindexes a face of Pdefined by the linear inequality Pi∈[r]cixi≥ −rc0. To realize the k-skeleton of 4n1×· · ·×4nreven in dimension 2k+r+1, we slightly modify this construction in the following way. Theorem 2.6. Let k≥0and n= (n1, . . . , nr)with r≥1and ni≥1for all i. There exist index sets I1, . . . , Ir⊂R, with |Ii|=nifor all i, such that the polytope P:= conv{wa1,...,ar|(a1, . . . , ar)∈I1× · · · × Ir} ⊂ R2k+r+1 is (k, n)-PPSN, where wa1,...,ar:= a1, . . . , ar,X i∈[r] a2 i, . . . , X i∈[r] a2k+2 iT ∈R2k+r+1. Proof. We will choose the index sets Iito be sufficiently separated in a sense that will be made explicit later in the proof. This choice will enable us, for each k-face Fof 4nindexed by A1× · · · × Ar⊂I1× · · · × Ir, to construct a monic polynomial (i.e., a polynomial with leading coefficient equal to 1) fF(t) := 2k+2 X j=0 cjtj that has, for all i∈[r], the form fF(t) = Qi(t)Y a∈Ai (t−a)2+sit+ri with polynomials Qi(t) everywhere positive and certain reals riand si. From the coefficients of this polynomial, we build the vector nF:= (s1−c1, . . . , sr−c1,−c2,−c3, . . . , −c2k+2)∈R2k+r+1. To prove that nFis a face-defining normal vector for F, take an arbitrary (a1, . . . , ar) in I1× · · · × Ir, and consider the following inequality for the inner product: nF·wa1,...,ar=X i∈[r] siai− 2k+2 X j=1 cjaj i  =X i∈[r] (siai+c0−fF(ai)) =X i∈[r] c0−Qi(ai)Y a∈Ai (ai−a)2−ri ≤rc0−X i∈[r] ri. Equality holds if and only if (a1, . . . , ar)∈A1×· · ·×Ar. Given the existence of a polynomial fF with the claimed properties, this proves that A1× · · · × Arindexes all wa1,...,ar’s that lie on a PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 7 face F0in P, and they of course span F0by definition of P. To prove that F0is combinatorially equivalent to Fit suffices to show that each wa1,...,ar∈F0is in fact a vertex of P, since P is a projection of 4n. This can be shown with the normal vector (2a1, . . . , 2ar,−1,0, . . . , 0), using the same calculation as before. Before showing how to choose the index sets Iithat enable us to construct the polynomials fFin general, we would like to make a brief aside to show the smallest example.  Example 2.7. For k= 1 and r= 2, choose the index sets I1,I2⊂Rarbitrarily, but separated in the sense that the largest element of I1be smaller than the smallest element of I2. For any 1-dimensional face Fof Pindexed by {a, b}×{c} ⊂ I1×I2, consider the polynomial fFof degree 2k+ 2 = 4: fF(t) := (t−a)2(t−b)2= (t2+αt +β)(t−c)2+s2t+r2, where α:= 2(−a−b+c), β:= a2+b2+ 3c2+ 4ab −4ac −4bc, r2:= a2b2−βc2, s2:= −2a2b−2ab2−αc2+ 2βc. Since the index sets I1,I2are separated, the discriminant α2−4β=−8(c−a)(c−b) is negative, which implies that the polynomial Q2(t) = t2+αt +βis positive for all values of t. Proof of Theorem 2.6, continued. We still need to show how to choose the index sets Iithat enable us to construct the polynomials fFin general. Once we have chosen these index sets, finding fFis equivalent to the task of finding polynomials Qi(t) such that (i) Qi(t) is monic of degree 2k+ 2 −2|Ai|. (ii) The rpolynomials fi(t) := Qi(t)Qa∈Ai(t−a)2are equal up to possibly the coefficients in front of t0and t1. (iii) Qi(t)>0 for all t∈R. The first two items form a linear equation system on the coefficients of the Qi(t)’s which has the same number of equations as variables. We will show that it has a unique solution if one chooses the right index sets Ii(the third item will be dealt with at the end). To do this, choose pairwise distinct reals ¯a1, . . . , ¯ar∈Rand look at the similar equation system: (i) ¯ Qi(t) are monic polynomials of degree 2k+ 2 −2|Ai|. (ii) The rpolynomials ¯ fi(t) := ¯ Qi(t)(t−¯ai)2|Ai|are equal up to possibly the coefficients in front of t0and t1. The first equation system moves into the second when we deform the points of the sets Ai continuously to ¯ai, respectively. If we show that the second equation system has a unique solution then so has the first equation system as long as we have chosen the sets Iiclose enough to the ¯ai’s, by continuity of the determinant (note that in the end, we can fulfill all these closeness conditions required for all k-faces of 4nsince there are only finitely many k-faces). Note that a polynomial ¯ fi(t) of degree 2k+ 2 has the form (1) ¯ Qi(t)(t−¯ai)2|Ai|+sit+ri for a monic polynomial ¯ Qiand some reals siand ri, if and only if ¯ f00 i(t) has the form (2) Ri(t)(t−¯ai)2(|Ai|−1) 8 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD for a polynomial Ri(t) with leading coefficient (2k+ 2)(2k+ 1). The backward direction can be settled by assuming without loss of generality ¯ai= 0 (otherwise just make a variable shift (t−¯ai)7→ t) and then integrating (2) twice with integration constants zero to obtain (1). Therefore the second equation system is equivalent to the following third one: (i) Ri(t) are polynomials of degree 2k−2(|Ai| − 1) with leading coefficient (2k+ 2)(2k+ 1). (ii) The rpolynomials gi(t):=Ri(t)·(t−¯ai)2(|Ai|−1) all equal the same polynomial, say g(t). Since Pi2(|Ai| − 1) = 2k, it has the unique solution Ri(t) = (2k+ 2)(2k+ 1) Y j6=i (t−¯aj)2(|Aj|−1), with g(t) = (2k+ 2)(2k+ 1) Y j∈[r] (t−¯aj)2(|Aj|−1). Therefore the second system also has a unique solution, where the ¯ fi(t) are obtained by integrating gi(t) twice with some specific integration constants. For a fixed iwe can again assume ¯ai= 0. Then both integration constants have been zero for this i, hence ¯ fi(0) = 0 and ¯ f0 i(0) = 0. Since giis non-negative and zero only at isolated points, ¯ fiis strictly convex, hence non-negative and zero only at t= 0. Therefore ¯ Qi(t) is positive for t6= 0. Since we chose ¯ai= 0, we can quickly compute the correspondence between the coefficients of ¯ Qi(t) = Pj¯qi,jtjand of Ri(t) = Pjri,jtj: ri,j =2|Ai|(2|Ai| − 1) + 4j|Ai|+j(j−1)¯qi,j. In particular ¯ Qi(0) = ¯qi,0=ri,0 2|Ai|(2|Ai| − 1) =Ri(0) 2|Ai|(2|Ai| − 1) >0, therefore ¯ Qi(t) is everywhere positive, hence so is Qi(t) if one chooses Iipossibly even closer to ¯ai, since the solutions of linear equation systems move continuously when one deforms the entries of the equation system by a homotopy (as long as the determinant stays non-zero), since the determinant and taking the adjoint matrix are continuous maps. The positivity of Qi(t) finishes the proof.  3. Projections of deformed products of simple polytopes In the previous section, we saw an explicit construction of polytopes whose k-skeleton is equivalent to that of a product of simplices. In this section, we provide another construction of (k, n)-PPSN polytopes, using Sanyal & Ziegler’s technique of “projecting deformed products of polygons” [Zie04, SZ09] and generalizing it to products of arbitrary simple polytopes. This generalized technique consists in suitably projecting suitable polytopes combinatorially equivalent to a given product of simple polytopes in such a way as to preserve its complete k-skeleton. The special case of products of simplices then yields (k, n)-PPSN polytopes. 3.1. General situation. We first discuss the general setting: for any given product P= P1× · · · × Prof simple polytopes, we construct a polytope P∼combinatorially equivalent to Pand whose k-skeleton is preserved under the projection on the first dcoordinates. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 9 Deformed products of simple polytopes. Let P1, . . . , Prbe simple polytopes of respective dimensions n1, . . . , nrand facet descriptions Pi={x∈Rni|Aix≤bi}, where each real matrix Ai∈Rmi×nihas one row for each of the mifacets of Piand ni= dim Pimany columns, and biis a right-hand side vector in Rmi. The product P=P1× · · · × Prthen has dimension n:= Pi∈[r]ni, and is given by the m:= Pi∈[r]miinequalities    A1 ... Ar   x≤   b1 . . . br   . The left hand m×nmatrix shall be denoted by A. It is proved in [AZ99] that for any matrix A∼obtained from Aby arbitrarily changing the zero entries above the diagonal blocks, there exists a right-hand side b∼such that the deformed polytope P∼defined by the inequality system A∼x≤b∼is combinatorially equivalent to P. The equivalence is the obvious one: it maps the facet defined by the i-th row of Ato the one given by the i-th row of A∼, for all i. Following [SZ09], we will use this “deformed product” construction in such a way that the projection of P∼to the first dcoordinates preserves its k-skeleton in the following sense. Preserved faces and the Projection Lemma. For integers n > d, let π:Rn→Rd denote the orthogonal projection to the first dcoordinates, and τ:Rn→Rn−ddenote the dual orthogonal projection to the last n−dcoordinates. Let Pbe a full-dimensional simple polytope in Rn, with 0 in its interior. The following notion of preserved faces — see Figure 2 — will be used extensively in the end of this paper: Definition 3.1 ([Zie04]).A proper face Fof a polytope Pis strictly preserved under πif (i) π(F)is a face of π(P), (ii) Fand π(F)are combinatorially isomorphic, and (iii) π−1(π(F)) equals F. pp q (a) (b) s q s r r Figure 2. (a) Projection of a tetrahedron onto R2: the edge pq is strictly preserved, while neither the edge qr, nor the face qrs, nor the edge qs are (because of conditions (i), (ii) and (iii) respectively). (b) Projection of a tetrahedron to R: only the vertex pis strictly preserved. The characterization of strictly preserved faces of Puses the normal vectors of the facets of P. Let F1, . . . , Fmdenote the facets of Pand for all i∈[m], let fidenote the normal 16 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD (1) any subset of at least α:= n−d 2vectors in Gis positively spanning; (2) the number of bad facets is β:= r−s+1, and therefore any k-face of P∼is contained in at least γ:= n−k−r+s−1 good facets. From this, the claim follows.  Proof of (2). Consider the deformed product of Figure 7a. Using similar calculations as before, we deduce that (1) any subset of at least α:= t−s+n−d+t−s−1 2vectors in Gis positively spanning; (2) the number of bad facets is β:= r−t, and therefore any k-face of P∼is contained in at least γ:= n−k−r+tgood facets. This yields a bound of k≤d+t−s−1 2−r+s. We optimize the final ‘−1’ away by suitably deforming the matrix At+1 as in Figure 7b. This amounts to adding one more vector g?to the Gale diagram, so that the first row of At+1 ceases to be a bad facet. This deformation is valid because: (1) the matrix            −1. . . −1? . . . ? M ... M 1 ... 1            still defines a simplex, as long as the ‘?’ entries are negative and M0 is chosen sufficiently large. (2) we can in fact choose the new vector g?to have only negative entries, by imposing an additional restriction on the Gale diagram G={e1, . . . , en−d,g1, . . . , gd+t, g?}of Q. Namely, we require the vertices of the (d+t)-dimensional simplicial polytope Qthat correspond to the Gale vectors g1, . . . , gd+tto lie on a facet. This forces the remaining vectors e1, . . . , en−d, g?to be positively spanning, so that g?has only negative entries.  Finally, we reformulate Proposition 3.7 to express, in terms of kand n= (n1, . . . , nr), what dimensions a (k, n)-PPSN polytope can have. This yields upper bounds on δpr(k, n). Theorem 3.8. For any k≥0and n= (n1, . . . , nr)with 1 = n1=· · · =ns< ns+1 ≤ · · · ≤ nr, δpr(k, n)≤     2(k+r)−s−tif 3s≤2k+ 2r, 2(k+r−s)+1 if 3s= 2k+ 2r+ 1, 2(k+r−s+ 1) if 3s≥2k+ 2r+ 2, where t∈ {s, . . . , r}is maximal such that 3s+ t X i=s+1 (ni+ 1) ≤2k+ 2r. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 17 (a) (b) 1 -1 1 -1 -1-1 -1-1 -1 1 -1 1 -1 -1-1 M M M -1-1 -1 Figure 7. Obtaining PPSN polytopes from a deformed product construction, when few of the factors are segments. Part (a) shows the technique used so far, and part (b) an additional optimization that exchanges a bad facet for a new vector in the Gale transform. Proof. Apply part (1) of Proposition 3.7 when 3s≥2k+ 2r+ 2 and part (2) otherwise.  Remark 3.9. When all the ni’s are large compared to k, the dimension of the (k, n)-PPSN polytope provided by this theorem is bigger than the dimension 2k+r+1 of the (k, n)-PPSN polytope obtained by the Minkowski sum of cyclic polytopes of Theorem 2.6. However, if we have many segments (neighborly cubical polytopes), or more generally if many ni’s are small compared to k, this construction provides our best examples of PPSN polytopes. 4. Topological Obstructions In this section, we give lower bounds on the minimal dimension δpr(k, n)ofa(k, n)-PPSN polytope, applying and extending a method developed by Sanyal [San09] to bound the number of vertices of Minkowski sums of polytopes. This method provides lower bounds on the target dimension of any linear projection that preserves a given set of faces of a polytope. It uses Gale duality to associate a certain simplicial complex Kto the set of faces that are preserved under the projection. Then lower bounds on the embeddability dimension of Ktransfer to lower bounds on the target dimension of the projection. In turn, the embeddability dimension is bounded via colorings of the Kneser graph of the system of minimal non-faces of K, using Sarkaria’s Embeddability Theorem. For the convenience of the reader, we first quickly recall this embeddability criterion. We then provide a brief overview of Sanyal’s method before applying it to obtain lower bounds on the dimension of (k, n)-PPSN polytopes. As mentioned in the introduction, these bounds match the upper bounds obtained from our different constructions for a wide range of parameters, and thus give the exact value of the minimal dimension of a PPSN polytope. 18 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD 4.1. Sarkaria’s embeddability criterion. 4.1.1. Kneser graphs. Recall that a k-coloring of a graph G= (V, E) is a map c:V→[k] such that c(u)6=c(v) for (u, v)∈E. As usual, we denote χ(G) the chromatic number of G (i.e., the minimal ksuch that Gadmits a k-coloring). We are interested in the chromatic number of so-called Kneser graphs. Let Zbe a subset of the power set 2[n]of [n]. The Kneser graph on Z, denoted KG(Z), is the graph with vertex set Z, where two vertices X, Y ∈ Z are related if and only if X∩Y=∅: KG(Z) = Z,{(X, Y )∈ Z2|X∩Y=∅}. Let KGk n= KG[n] kdenote the Kneser graph on the set of k-tuples of [n]. For example, the graph KG1 nis the complete graph Kn(of chromatic number n) and the graph KG2 5is the Petersen graph (of chromatic number 3). Remark 4.1. (1) If n≤2k−1, then any two k-tuples of [n] intersect and the Kneser graph KGk nis independent (i.e., it has no edge). Thus its chromatic number is χ(KGk n) = 1. (2) If n≥2k−1, then χ(KGk n)≤n−2k+ 2. Indeed, the map c:[n] k→[n−2k+ 2] defined by c(F) = min(F∪ {n−2k+ 2}) is a (n−2k+ 2)-coloring of KGk n. In fact, it turns out that this upper bound is the exact chromatic number of the Kneser graph: χ(KGk n) = max{1, n −2k+ 2}. This result has been conjectured by Kneser in 1955, and proved by Lov´asz in 1978 applying the Borsuk-Ulam Theorem — see [Mat03] for more details. However, we will only need the upper bound for the topological obstruction. 4.1.2. Sarkaria’s Theorem. Our lower bounds on the dimension of (k, n)-PPSN polytopes rely on lower bounds for the dimension in which certain simplicial complexes can be embedded. Among other possible methods [Mat03], we use Sarkaria’s Coloring and Embedding Theorem. We associate to any simplicial complex Kthe set system Zof minimal non-faces of K, that is, the inclusion-minimal sets of 2V(K)rK. For example, the complex of minimal non-faces of the k-skeleton of the n-dimensional simplex is [n+1] k+2 . Sarkaria’s Theorem provides a lower bound on the dimension into which Kcan be embedded, in terms of the chromatic number of the Kneser graph of Z. Theorem 4.2 (Sarkaria’s Theorem).Let Kbe a simplicial complex embeddable in Rd,Zbe the system of minimal non-faces of K, and KG(Z)be the Kneser graph on Z. Then d≥ |V(K)| − χ(KG(Z)) −1. In other words, we get large lower bounds on the possible embedding dimension of Kwhen we obtain colorings with few colors of the Kneser graph on the minimal non-faces of K. We refer to the excellent treatment in [Mat03] for further details. 4.2. Sanyal’s topological obstruction method. For given integers n > d, we consider the orthogonal projection π:Rn→Rdto the first dcoordinates, and its dual projection τ:Rn→Rn−dto the last n−dcoordinates. Let Pbe a full-dimensional simple polytope in Rn, with 0 in its interior, and assume that its vertices are strictly preserved under π. Let F1, . . . , Fmdenote the facets of P, and for all i∈[m], let fidenote the normal vector of Fi, and gi=τ(fi). For any face Fof P, let ϕ(F) denote the set of indices of the facets of P containing F,i.e., such that F=Ti∈ϕ(F)Fi. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 19 Lemma 4.3 (Sanyal [San09]).The vector configuration G={gi|i∈[m]} ⊂ Rn−dis the Gale transform of the vertex set of a (full-dimensional) polytope Qof Rm−n+d−1. Up to a slight perturbation of the facets of P, we can even assume Qto be simplicial. We will refer to the polytope Qas Sanyal’s projection polytope. The faces of this polytope capture the key notion of strictly preserved faces of P— remember Definition 3.1. Indeed, the Projection Lemma 3.2 ensures that for any face Fof Pstrictly preserved by the projection π, the set {gi|i∈ϕ(F)}is positively spanning, which implies by Gale duality that the set of vertices {ai|i∈[m]rϕ(F)}forms a face of Q. Example 4.4. Let Pbe a triangular prism in 3-space that projects to a hexagon as in Figure 8a, so that n= 3, d= 2 and m= 5. The vector configuration G⊂R1obtained by projecting P’s normal vectors consists of three vectors pointing up and two pointing down, so that Sanyal’s projection polytope Qis a bipyramid over a triangle. An edge Fi∩Fjof P that is preserved under projection corresponds to the face [5] r{i, j}of Q. Notice that the six faces of Qcorresponding to the six edges of Pthat are preserved under projection (in bold in Figure 8a) make up the entire boundary complex of the bipyramid Q. 3 1 (a) (b) 4 2 5 1 23 45 3 1 5 2 4 Figure 8. (a) Projection of a triangular prism and (b) its associated projection polytope Q. The six faces of Qcorresponding to the six edges of P preserved under projection (bold) make up the entire boundary complex of Q. Let Fbe a subset of the set of all strictly preserved faces of Punder π. Define Kto be the simplicial complex induced by {[m]rϕ(F)|F∈ F}. Remark 4.5. Notice that not all non-empty faces of Kcorrespond to non-empty faces in F: in Example 4.4, if Fconsist of all strictly preserved edges, then Kis the entire boundary complex of Sanyal’s projection polytope Q, so that it contains the edge {2,3}. But then the complementary intersection of facets, F1∩F4∩F5, does not correspond to any non-empty face of P. Since the set of vertices {ai|i∈[m]rϕ(F)}forms a face of Qfor any face F∈ F, and since Qis simplicial, Kis a subcomplex of the face complex of Q⊂Rm−n+d−1. In particular, when Kis not the entire boundary complex of Q, it embeds into Rm−n+d−2by stereographic projection (otherwise, it only embeds into Rm−n+d−1, as happens in Example 4.4). 20 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD Thus, given the simple polytope P⊂Rn, and a set Fof faces of Pthat we want to preserve under projection, the study of the embeddability of the corresponding abstract simplicial complex Kprovides lower bounds on the dimension din which we can project P. We proceed in the following way: (1) we first choose our subset Fof strictly preserved faces sufficiently simple to be understandable, and sufficiently large to provide an obstruction; (2) we then understand the system Zof minimal non-faces of the simplicial complex K; (3) finally, we find a suitable coloring of the Kneser graph on Zand apply Sarkaria’s Theorem 4.2 to bound the dimension in which Kcan be embedded: a t-coloring of KG(Z) ensures that Kis not embeddable into |V(K)| − t−2 = m−t−2, which by the previous paragraph bounds the dimension dfrom below as follows: Theorem 4.6 (Sanyal [San09]).Let Pbe a simple polytope in Rnwhose facets are in general position, and let π:Rn→Rdbe a projection. Let Fbe a subset of the set of all strictly preserved faces of Punder π,Kbe the simplicial complex induced by {[m]rϕ(F)|F∈ F}, and let Zbe its system of minimal non-faces. If the Kneser graph KG(Z)is t-colorable, then (1) if Kis not the entire boundary complex of the Sanyal polytope Q, then d≥n−t+ 1; (2) otherwise, d≥n−t. In the remainder of this section, we apply Sanyal’s topological obstruction to our problem. The hope was initially to extend it to bound the target dimension of a projection preserving the k-skeleton of an arbitrary product of simple polytopes. However, the combinatorics involved to deal with this general question turn out to be too complicated and we restrict our attention to products of simplices. We obtain in this manner bounds on the minimal dimension δpr(k, n) of a (k, n)-PPSN polytope. 4.3. Preserving the k-skeleton of a product of simplices. In this section, we understand the abstract simplicial complex Kcorresponding to our problem, and describe its system of minimal non-faces. The facets of 4nare exactly the products ψi,j =4n1× · · · × 4ni−1×(4nir{j})× 4ni+1 × · · · × 4nr, for i∈[r] and j∈[ni+ 1]. We identify the facet ψi,j with the element j∈[ni+ 1] of the disjoint union [n1+1]][n2+1]] · · · ] [nr+ 1]. Let F=F1×· · ·×Frbe a k-face of 4n. Then Fis contained in a facet ψi,j of 4nif and only if j /∈Fi. Thus, the set of facets of 4nthat do not contain Fis exactly F1] · · · ] Fr. Consequently, if we want to preserve the k-skeleton of 4n, then the abstract simplicial complex K we are interested in is induced by (3) F1] · · · ] Fr∅ 6=Fi⊂[ni+ 1] for all i∈[r],and X i∈[r] (|Fi| − 1) = k. Remark 4.7. In contrast to the general case, when we want to preserve the complete k-skeleton of a product of simplices, the complex Kcannot be the entire boundary complex of the Sanyal polytope Q. In consequence, the better lower bound from part (1) of Sanyal’s Theorem 4.6 always holds, and we always use it from now on without further notice. To prove that Kcannot cover the entire boundary complex of Q, observe that dim Q=m−n+d−1 = X(ni+ 1) −Xni+d−1 = r+d−1, PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 21 while dim K=r+k−1 by (3). A necessary condition for Kto be the entire boundary complex of Qis that dim K= dim Q−1, which translates to d=k+ 1. Now suppose that the entire k-skeleton of 4nis preserved under projection to dimension k+ 1. Then the projections of those k-faces are facets of π(4n). Since any ridge of the projected polytope is contained in exactly two facets, and the entire k-skeleton of 4nis preserved, we know that any (k−1)-face of 4nis also contained in exactly two k-faces. But this can only happen if k=n−1, which means n=d. Observe again that Kcan be the entire boundary complex of Qif we do not preserve all k-faces of 4n— see Example 4.4. The following lemma gives a description of the minimal non-faces of K: Lemma 4.8. The system of minimal non-faces of Kis Z=G1] · · · ] Gr|Gi| 6= 1 for all i∈[r],and X i|Gi6=∅ (|Gi| − 1) = k+ 1. Proof. A subset G=G1] · · · ] Grof [n1+ 1] ][n2+ 1] ] · · · ] [nr+ 1] is a face of Kwhen it can be extended to a subset F1] · · · ] Frwith P(|Fi| − 1) = kand ∅ 6=Fi⊂[ni+ 1] for all i∈[r], that is, when k≥i∈[r]|Gi=∅+X i∈[r] (|Gi| − 1) = X i|Gi6=∅ (|Gi| − 1). Thus, Gis a non-face if and only if X i|Gi6=∅ (|Gi| − 1) ≥k+ 1. If Pi|Gi6=∅(|Gi| − 1) > k + 1, then removing any element provides a smaller non-face. If there is an isuch that |Gi|= 1, then removing the unique element of Giprovides a smaller non-face. Thus, if Gis a minimal non-face, then Pi|Gi6=∅(|Gi| − 1) = k+ 1, and |Gi| 6= 1 for all i∈[r]. Reciprocally, if Gis a non-minimal non-face, then it is possible to remove one element keeping a non-face. Let i∈[r] be such that we can remove one element from Gi, keeping a non-face. Then, either |Gi|= 1, or X j|Gj6=∅ (|Gj| − 1) ≥1+(|Gi| − 2) + X j6=i|Gj6=∅ (|Gj| − 1) ≥k+ 2, since we keep a non-face.  4.4. Colorings of KG(Z).The next step consists in providing a suitable coloring for the Kneser graph on the system Zof minimal non-faces of K. Let S:= {i∈[r]|ni= 1}denote the set of indices corresponding to the segments, and R:= {i∈[r]|ni≥2}the set of indices corresponding to the non-segments in the product 4n. We first provide a coloring for two extremal situations. Theorem 4.9 (Topological obstruction for low-dimensional skeleta).If k≤Pi∈Rni−2 2, then the dimension of any (k, n)-PPSN polytope cannot be smaller than 2k+|R|+ 1: δpr(k, n)≥2k+|R|+ 1. 22 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD Proof. Let k1, . . . , kr∈Nbe such that X i∈[r] ki=kand (ki= 0 for i∈S; 0≤ki≤ni−2 2for i∈R. Observe that (1) such a tuple exists since k≤Pi∈Rni−2 2. (2) for any minimal non-face G=G1] · · · ] Grof Z, there exists i∈[r] such that |Gi| ≥ ki+ 2. Indeed, if |Gi| ≤ ki+ 1 for all i∈[r], then k+ 1 = X i|Gi6=∅ (|Gi| − 1) ≤X i|Gi6=∅ ki≤X i∈[r] ki=k, which is impossible. For all i∈[r], we fix a proper coloring γi:[ni+1] [ki+2]→[χi] of the Kneser graph KGki+2 ni+1, with χi= 1 color if i∈Sand χi=ni−2ki−1 colors if i∈R— see Section 4.1.1. Then, we define a coloring γ:Z → [χ1]]· · · ][χr] of the Kneser graph on Zas follows. Let G=G1]· · · ]Gr be a given minimal non-face of Z. We choose arbitrarily an i∈[r] such that |Gi| ≥ ki+ 2, and again arbitrarily a subset gof Giwith ki+ 2 elements. We color Gwith the color of gin KGki+2 ni+1, that is, we define γ(G) = γi(g). The coloring γis a proper coloring of the Kneser graph KG(Z). Indeed, let G=G1]· · ·]Gr and H=H1] · · · ] Hrbe two minimal non-faces of Zrelated by an edge in KG(Z), which means that they do not intersect. Let i∈[r] and g⊂Gibe such that we have colored G with γi(g), and similarly j∈[r] and h⊂Gjbe such that we have colored Hwith γj(h). Since the color sets of γ1, . . . , γrare disjoint, the non-faces Gand Hcan receive the same color γi(G) = γj(H) only if i=jand gand hare not related by an edge in KGki+2 ni+1, which implies that g∩h6=∅. But this cannot happen, because g∩h⊂Gi∩Hi, which is empty by assumption. Thus, Gand Hget different colors. This provides a proper coloring of KG(Z) with Pχicolors. By Theorem 4.6 and Remark 4.7, we know that the dimension dof the projection is at least X i∈[r] ni−X i∈[r] χi+ 1 = 2k+|R|+ 1.  Theorem 4.10 (Topological obstruction for high-dimensional skeleta).If k≥1 2Pini, then any (k, n)-PPSN polytope is combinatorially equivalent to 4n: δpr(k, n)≥Xni. Proof. Let G=G1] · · · ] Grand H=H1] · · · ] Hrbe two minimal non-faces of Z. Let A={i∈[r]|Gi6=∅or Hi6=∅}. Then X i∈A (|Gi|+|Hi|)≥X Gi6=∅ (|Gi| − 1) + X Hi6=∅ (|Hi| − 1) + |A| = 2k+2+|A|>X i∈[r] ni+|A| ≥ X i∈A (ni+ 1). Thus, there exists i∈Asuch that |Gi|+|Hi|> ni+ 1, which implies that Gi∩Hi6=∅, and proves that G∩H6=∅. PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 23 Consequently, the Kneser graph KG(Z) is independent (and we can color it with only one color). We obtain that the dimension dof the projection is at least Pni. In other words, in this extremal case, there is no better (k, n)-PSN polytope than the product 4nitself.  Remark 4.11. Theorem 4.10 can sometimes be strengthened a little: If k=1 2Pni−1, and k+ 1 is not representable as a sum of a subset of {n1, . . . , nr}, then δpr(k, n) = Pni. Proof. As in the previous theorem, we prove that the Kneser graph KG(Z) is independent. Indeed, assume that G=G1] · · · ] Grand H=H1] · · · ] Hrare two minimal non-faces of Zrelated by an edge in KG(Z). Then, G∩His empty, which implies that for all i∈[r] (4) |Gi|+|Hi| ≤ ni+ 1. Let U={i|Gi6=∅} and V={i|Hi6=∅}. Then, X i∈U∪V (|Gi|+|Hi|) = X i∈U (|Gi| − 1) + X i∈V (|Hi| − 1) + |U|+|V|= 2k+2+|U|+|V| =X i∈[r] ni+|U|+|V|(?) ≥X i∈U∪V ni+|U∪V|=X i∈U∪V (ni+ 1). Summing (4) over i∈U∪Vimplies that both the inequality (?) and (4) for i∈U∪Vare in fact equalities. The tightness of (?) implies furthermore that |U|+|V|=|U∪V|, so that U∩V=∅; in other words, Hiis empty whenever Giis not. The equality in (4) then asserts that |Gi|=ni+ 1 for all i∈U, and therefore k+ 1 = X i∈U (|Gi| − 1) = X i∈U ni is representable as a sum of a subset of the ni, which contradicts the assumption.  Finally, to fill the gap in the ranges of kcovered by Theorems 4.9 and 4.10, we merge both coloring ideas as follows. We partition [r] = A]Band choose ki≥0 for all i∈Aand kB≥0 such that (5) X i∈A ki!+kB≤k. We will see later what the best choice for A,B,kBand the ki’s is. Let nB=Pi∈Bni. Color the Kneser graphs KGki+2 ni+1 for i∈Aand KGkB+1 nBwith pairwise disjoint color sets with χi=(ni−2ki−1 if 2ki≤ni−2, 1 if 2ki≥ni−2, and χB=     0 if nB= 0, nB−2kBif 2kB≤nB−1, 1 if 2kB≥nB−1, colors respectively. Observe now that for all minimal non-faces G=G1] · · · ] Gr, •either there is an i∈Asuch that |Gi| ≥ ki+ 2, •or Pi∈B|Gi6=∅(|Gi| − 1) ≥kB+ 1. 24 B. MATSCHKE, J. PFEIFLE, AND V. PILAUD Indeed, otherwise k+ 1 = X i|Gi6=∅ (|Gi| − 1) ≤ X i∈A ki!+kB≤k. This permits us to define a coloring of KG(Z) in the following way. For each minimal non-face G=G1] · · · ] Gr, we arbitrarily choose one of the following strategies: (1) If we can find an i∈Asuch that |Gi| ≥ ki+ 2, we choose an arbitrary subset gof Gi with ki+ 2 elements, and color Gwith the color of gin KGki+2 ni+1; (2) Otherwise, Pi∈B|Gi6=∅(|Gi| − 1) ≥kB+ 1, and we choose an arbitrary subset gof ] i∈B (Gir{ni+ 1})⊂] i∈B [ni] with kB+ 1 elements and color Gwith the color of gin KGkB+1 nB. By exactly the same argument as in the proof of Theorem 4.9, one can verify that this provides a valid coloring of the Kneser graph KG(Z) with χ:= χ(A, B, ki, kB) := X i∈A χi+χB many colors. Therefore Sanyal’s Theorem 4.6 and Remark 4.7 yield the following lower bound on the dimension dof any (k, n)-PPSN polytope: d≥dk:= dk(A, B, ki, kB) := X i ni+ 1 −χ≥δpr(k, n). It remains to choose parameters A,B, and {ki|i∈A}and kBthat maximize this bound. We proceed algorithmically, by first fixing Aand B, and choosing the ki’s and kBto maximize the bound on the dimension dk. For this, we first start with ki= 0 for all iand kB= 0, and observe the variation of dkas we increase individual ki’s or kB. By (5), we are only allowed a total of ksuch increases. During this process, we will always maintain the conditions 2ki≤ni−1 for all i∈Aiand 2kB≤nB(which makes sense by the formulas for χiand χB). We start with ki= 0 for all iand kB= 0. Then χ(A, B, 0,0) = X i∈A (ni−1) + |S∩A|+nB =X i∈A ni− |A|+|S∩A|+X i∈B ni=X i∈[r] ni−r+|B∪S|, and dk(A, B, 0,0) = 1 + r− |B∪S|, where S={i∈[r]|ni= 1}denotes the set of segments. We now study the variation of dkas we increase each of the ki’s and kBby one. For i∈A, increasing kiby one decreases χiby      2,if 2ki≤ni−4, 1,if 2ki=ni−3, 0,if 2ki≥ni−2, PRODSIMPLICIAL-NEIGHBORLY POLYTOPES 25 and hence increases dkby the same amount. Observe in particular that dkremains invariant if we increase kifor some segment i∈S(because ni= 1 for segments). Thus, it makes sense to choose Bto contain all segments. Similarly, increasing kBby one decreases χBby      2,if 2kB≤nB−3, 1,if 2kB=nB−2, 0,if 2kB≥nB−1, and increases dkby the same amount. Recall that we are allowed at most kincreases of ki’s or kBby (5). Heuristically, it seems reasonable to first increase the ki’s or kBthat increase dkby two, and then these that increase dkby one. Hence we get a case distinction on k, which also depends on Aand B: Theorem 4.12 (Topological obstruction, general case).Let k≥0and n= (n1, . . . , nr)with r≥1and ni≥1for all i. Let [r] = A]Bbe a partition of [r]with B⊃S:= {i∈[r]|ni= 1}. Define K1:= K1(A, B) := X i∈Ani−2 2+ max 0,nB−1 2, K2:= K2(A, B) := i∈A|niis odd+(1if nBis even and non-zero, 0otherwise. Then the following lower bounds hold for the dimension of a (k, n)-PPSN polytope: (1) If 0≤k≤K1, then δpr(k, n)≥r+ 1 − |B|+ 2k; (2) If K1≤k≤K1+K2, then δpr(k, n)≥r+ 1 − |B|+K1+k; (3) If K1+K2≤k, then δpr(k, n)≥r+ 1 − |B|+ 2K1+K2. This theorem enables us to recover Theorem 4.9 and Theorem 4.10: Corollary 4.13. Let k≥0and n= (n1, . . . , nr)with r≥1and ni≥1for all i, and define S:= {i∈[r]|ni= 1}and R:= {i∈[r]|ni≥2}. Then (1) If 0≤k≤X i∈Rni−2 2+ max 0,|S| − 1 2, then δpr(k, n)≥2k+|R|+ 1. (2) If k≥1 2Pnithen δpr(k, n)≥Pini. Proof. Take A=Rand B=Sfor (1), and A=∅and B= [r] for (2).  4.5. Explicit lower bounds. There is an algorithm to explicitly choose in general the partitions [r] = A]Bwhich yields the best bounds in Theorem 4.12. Since this algorithm is quite technical, we just present the best results we obtain with this topological obstruction. We refer to [MMPP09] for further details. We fix K1=K1(R, S) and define d0=r+ 1 − |S|and n=Pi∈[r]ni. The best lower bound dkthat we obtain with this coloring can be summarized explicitly by the following case distinction — see Figure 9: