Zonotopes whose cellular strings are all coherent
Rob Edman Pakawut Jiradilok Gaku Liu Thomas McConville
math.CO 52C40









Zonotopes whose cellular strings are all coherent
    Rob Edman, Pakawut Jiradilok, Gaku Liu, Thomas McConville
    December 30, 2023
=============================================================




A cellular string of a polytope is a sequence of faces stacked on top of each other in a given direction. The poset of cellular strings, ordered by refinement, is known to be homotopy equivalent to a sphere. The subposet of coherent cellular strings is the face lattice of the fiber polytope, hence is homeomorphic to a sphere. In some special cases, every cellular string is coherent. Such polytopes are said to be all-coherent. We give a complete classification of zonotopes with the all-coherence property in terms of their oriented matroid structure. Although the face lattice of the fiber polytope in this case is not an oriented matroid invariant, we prove that the all-coherence property is invariant.







§ INTRODUCTION


We consider the problem of realizing spaces of polytopal subdivisions as the boundary complex of a polytope. For example, the set of triangulations of a convex polygon form the vertices of a polytope known as the associahedron. The facets of an associahedron correspond to diagonals where a facet and vertex are incident exactly when the triangulation includes the diagonal. In this situation, we are given the combinatorics of the polytope, namely the face lattice, and we need to provide a geometric realization.

Among the many polytopal realizations of the associahedron (see <cit.> for a survey), the secondary polytope construction of Gelfand, Kapranov, and Zelevinsky is particularly elegant <cit.>. Given a finite set of points  in ^d, the secondary polytope Σ() is the Newton polytope of the -determinant. Its vertices correspond to regular triangulations of , where a triangulation  is regular (or coherent) if there exists a function f: such that  is the set of lower faces of the convex hull of {(x,f(x)): x∈}⊆^d+1. If  is the set of vertices of a convex polygon, then every triangulation is regular, so the secondary polytope realizes the associahedron.

Given a linear surjection of polytopes π:P Q, the Baues poset ω(P,Q) is the set of polytopal subdivisions of Q by images of faces of P, ordered by refinement; see Section <ref> for a more precise definition. For example, when P is a simplex, the maximally refined subdivisions of Q in ω(P,Q) are a family of triangulations with specified vertices. For generic functions π, Baues observed that if P is a d-simplex and Q is 1-dimensional, then ω(P,Q) is the face lattice of a (d-1)-cube <cit.>. If P is a d-cube and Q is 1-dimensional, then ω(P,Q) is the face lattice of a (d-1)-dimensional permutahedron. When P is a d-dimensional permutahedron, the maximally refined subdivisions of Q may be identified with reduced words for the longest element of a type A_d Coxeter system. Baues noticed that the order complex of ω(P,Q) is not always a simplicial sphere, but he conjectured that it is homotopy-equivalent to a sphere. This was proved for any polytopes P,Q with Q=1 by Billera, Kapranov, and Sturmfels <cit.>. We refer to the survey article by Reiner for many other results of this type <cit.>.

As with triangulations, there is a distinguished subset of polytopal subdivisions in ω(P,Q) called coherent subdivisions. Generalizing the secondary polytope construction, the fiber polytope introduced by Billera and Sturmfels is a polytope of dimension P- Q whose faces correspond to coherent subdivisions of Q <cit.>. Hence, the Baues poset ω(P,Q) contains a canonical spherical subspace of dimension P- Q-1, and Baues' original question is whether this subspace is homotopy-equivalent to the full poset ω(P,Q). We consider the stronger question:


For which projections f:P Q is ω(P,Q) isomorphic to the face lattice of a polytope of dimension P- Q?


Using the fiber polytope construction, the poset ω(P,Q) is the face lattice of a ( P- Q)-dimensional polytope exactly when every element of ω(P,Q) is coherent; see Section <ref> for details. Hence, we may rephrase Question <ref> as asking whether every subdivision of Q by faces of P is coherent. If π:P Q has this property, we say the projection is all-coherent.



In this work, we examine the special case of Question <ref> where P is a zonotope and Q is 1-dimensional. A zonotope with n zones is the image of a n-dimensional cube under a linear map. To any zonotope with a distinguished linear functional, one may associate an (acyclic) oriented matroid, an abstract combinatorial object that records the faces of the zonotope. Some background on oriented matroids is given in Section <ref>. Given P and Q as above, it is known that the facial structure of the fiber polytope of π:P Q is not an oriented matroid invariant. That is, there exists a zonotope with two distinct linear functionals defining the same oriented matroid whose fiber polytopes are not combinatorially equivalent; see Example <ref>. However, we prove that the all-coherence property is invariant.

Our main result is a characterization of the all-coherence property for the set of cellular strings of a zonotope.


Let Z be a zonotope with a generic linear functional π. The following are equivalent.



  *  The pair (Z,π) is all-coherent.

  *  The Baues poset ω(Z,π) is the face lattice of a polytope.

  *  The order complex Δ(ω(Z,π)) is a simplicial sphere.

  *  Every monotone path is coherent.

  *  The acyclic oriented matroid  associated to (Z,π) is in the list given in Section <ref>.





The equivalence of (<ref>)-(<ref>) is proved for all polytopes in Corollary <ref>. Since the order complex Δ(ω(Z,π)) only depends on the oriented matroid corresponding to (Z,π), we may take Statement (<ref>) as the definition of the all-coherence property for an oriented matroid. We prove the equivalence of (<ref>) and (<ref>) in Corollary <ref>. Our proof of this equivalence works for zonotopes only. Finally, we give a complete classification of zonotopes with the all-coherence property in Section <ref> using the techniques developed in Section <ref>.


The all-coherence property was previously studied for projections P Q where P is a cube and Q is 2-dimensional <cit.> or P and Q are cyclic polytopes <cit.>. It was observed that in many cases of an all-coherent projection, there is a “nice” formula for the number of generic tilings. In Section <ref>, we demonstrate a family of zonotopes for which every cellular string is coherent. As in the preceding literature, the monotone paths of these zonotopes admit a nice enumeration.

This paper continues the work by the first author <cit.>, which contained several techniques to detect incoherent monotone paths and had a partial classification of all-coherent zonotopes. However, our proof of the full classification primarily relies on Proposition <ref>, which is new to this paper.






§ UNIVERSAL COHERENCE FOR POLYTOPES


In this section, we recall coherence and the Baues poset of polyhedral subdivisions induced by a projection of polytopes. In Section <ref>, we prove that every element of the Baues poset is coherent exactly when its order complex is homeomorphic to a sphere of a certain dimension.



 §.§ Fiber polytope


Given a polytope P and linear functional ψ, let P^ψ be the face

    P^ψ={x∈ P: ψ(x)=min_y∈ Pψ(y)}.


That is, P^ψ is the face of P at which ψ is minimized. The normal fan of P⊆^d is a subdivision of (^d)^* into relatively open cones where ψ_1 and ψ_2 lie in the same cone if P^ψ_1=P^ψ_2. Let π:P Q be a surjective (affine) linear map of polytopes. A collection Δ of faces of the boundary complex of P is called a π-induced subdivision of Q if


  * {π(F): F∈Δ} is a polyhedral complex subdividing Q with all π(F) distinct, and 

  * if π(F)⊆π(F^) then F=F^∩π^-1(π(F)).


For any π:P Q, there is always the trivial subdivision Δ={P}. A π-induced subdivision Δ is coherent if there exists a linear functional ψ:P such that for x∈ Q and F∈Δ with x∈π(F),

    π^-1(x)^ψ=F∩π^-1(x).

Any linear functional ψ defines a unique coherent subdivision Δ^ψ. For example, Δ^0 is the trivial subdivision.

The Baues poset ω(P,Q) is the set of π-induced subdivisions, partially ordered by refinement: Δ≤Δ^ if for any face F in Δ there exists F^ in Δ^ such that F⊆ F^. The subposet of coherent subdivisions is denoted ω_(P,Q).

The fiber polytope Σ(P,Q) was defined by Billera and Sturmfels as the Minkowski integral 1/(Q)∫_Qπ^-1(x)dx; see <cit.> for details. This polytope lives in the ambient space of P and is of dimension P- Q. The faces of the fiber polytope encode coherent subdivisions of Q in the following sense. For linear functionals ψ_1,ψ_2:P, Δ^ψ_1=Δ^ψ_2 if and only if ψ_1 and ψ_2 lie in the relative interior of the same cone of the normal fan of Σ(P,Q). For the most part, we will only need results about the normal fan of a fiber polytope rather than the polytope itself.











 §.§ All-coherence property


Given a poset X, the order complex Δ(X) is the abstract simplicial complex whose faces are chains x_0<⋯<x_d of X. If X has a unique maximum or minimum element, we let X be the same poset with these elements removed. In particular, ω(P,Q) is the poset of nontrivial subdivisions of Q by faces of P.

We say that a projection π:P Q is all-coherent if every π-induced subdivision of Q is coherent. The following theorem gives a useful characterization of the all-coherence property.



Given a projection π:P Q, the following statements are equivalent.


  *  The map π is all-coherent.

  *  The Baues poset ω(P,Q) is isomorphic to the face lattice of a polytope of dimension P- Q.

  *  The order complex Δ(ω(P,Q)) is a simplicial sphere of dimension P- Q-1.




We prove (<ref>)(<ref>)(<ref>)(<ref>).

If P Q is all-coherent, then ω(P,Q)=ω_(P,Q). The latter poset is isomorphic to the face lattice of the fiber polytope Σ(P,Q), which is a polytope of dimension P- Q.

If ω(P,Q) is the face lattice of a polytope R, then its proper part ω(P,Q) is the face poset of its boundary complex R. The order complex Δ(ω(P,Q)) is realized by the barycentric subdivision of R, so it is a simplicial sphere. If R= P- Q, then its boundary complex has dimension P- Q-1.

Now assume Δ(ω(P,Q)) is a simplicial sphere of dimension d= P- Q-1. The inclusion ω_(P,Q)ω(P,Q) induces an injective simplicial map

    Δ(ω_(P,Q))Δ(ω(P,Q)).

The geometric realization of this map is a continuous map ^d^d which is a homeomorphism onto its image. If it is not surjective, then we obtain a subspace of ^d which is homeomorphic to ^d. This is well-known to be impossible, e.g. by an application of the Borsuk-Ulam Theorem; see <cit.>. Hence, ω(P,Q)=ω_(P,Q) holds, which means that P Q is all-coherent.


If Q=1, we can drop the dimension condition. This proves the equivalence of Theorem <ref>(<ref>)-(<ref>).


If Q=1, then the following are equivalent.


  *  The map π:P Q is all-coherent.

  *  The Baues poset ω(P,Q) is the face lattice of a polytope.

  *  The order complex Δ(ω(P,Q)) is a simplicial sphere.




The proof of (<ref>)(<ref>)(<ref>) is immediate. It remains to show (<ref>) implies (<ref>).

Suppose Q=1 and Δ(ω(P,Q)) is a simplicial sphere. Then <cit.> states that Δ(ω(P,Q)) is homotopy equivalent to a sphere of dimension P-2. Hence, Δ(ω(P,Q)) is homeomorphic to ^ P-2. By Theorem <ref>, it follows that π is all-coherent.






§ ORIENTED MATROIDS


In this section, we develop some notation for oriented matroids. For more background on oriented matroids, we recommend <cit.>.





 §.§ Hyperplane arrangements


The normal fan of a zonotope is the set of cones cut out by a real, central hyperplane arrangement. In this section, we recall some notation for hyperplane arrangements.

A real hyperplane arrangement (or arrangement) is a finite set of hyperplanes in a real vector space V. We will assume that the arrangement is central, which means that every hyperplane contains the origin. Each hyperplane partitions V into two open half-spaces and the hyperplane itself. We typically assume that an arrangement comes with an orientation; that is, for each hyperplane H, we set H^0=H and assign the label H^+ and H^- to the two open half-spaces defined by H. A face of an arrangement  is any nonempty cone of the form ⋂_H∈H^x(H) where x∈{0,+,-}^. Maximal faces are called chambers. A sign vector is an element of {0,+,-}^E for some finite set E. A sign vector x∈{0,+,-}^ is a covector of  if there is a face F of  such that F = ⋂_H∈H^x(H). The set of covectors of  will be denoted ().

We say a zonotope Z=Z(ρ) is generated by a set of vectors ρ={ρ_1,…,ρ_n}⊆ V if it is (an affine translation of) the image of [0,1]^n under the matrix with columns vectors ρ_1,…,ρ_n. The normal fan of Z is the hyperplane arrangement ={H_1,…,H_n} in V^* where H_i is the set of linear functionals annihilating ρ_i. In this situation, we say that Z is dual to .





Set I=[0,1] and let π:I^6 Z be a generic projection from the standard 6-dimensional cube to a 2-dimensional zonotope Z with 6 zones. We may assume that π takes the form

    (1     1     1     1     1     1
    a_1     a_2     a_3     a_4     a_5     a_6)

for some a_1<⋯<a_6. A linear map π̂:^6^3 that is a factor of π takes the form

    (1     1     1     1     1     1
    a_1     a_2     a_3     a_4     a_5     a_6
    b_1     b_2     b_3     b_4     b_5     b_6)

for some b_1,…,b_6∈. Let Ẑ be the image of I^6 under π̂. For 1≤ i<j<k≤ 6, let Δ_ijk^a denote the minor

    a_ib_j-a_ib_k+a_jb_k-a_jb_i+a_kb_i-a_kb_j.

The sequence of signs (Δ_ijk^a)_1≤ i<j<k≤ 6 is the chirotope of Ẑ, and it completely determines the facial structure of Ẑ. As a function of b, the minor Δ_ijk^a is a linear form on ^6. Hence, the normal fan of the fiber polytope associated to the projection π is the set of cones cut out by the hyperplane arrangement

    ^a={Δ_ijk^a: 1≤ i<j<k≤ 6},

which is known as a discriminantal arrangement (cf. <cit.>).

The Baues poset ω(I^6,Z) is the collection of subdivisions of Z by zonogons, each of which is the Minkowski sum of several edges of Z. In particular, the maximally refined subdivisions of Z are by rhombi. The coherent rhombic tilings correspond to the chambers of ^a. There are a total of 904 distinct rhombic tilings of Z. However, there is no choice of vector a for which all 904 tilings are coherent. A simple way to see this is that the (proper) subposet of ω(I^6,Z) of tilings refining the zonotopal subdivision in Figure <ref> is a rank 4 Boolean lattice, but the subposet of coherent subdivisions is the face lattice of a 4-dimensional polytope. Moreover, the number of chambers of ^a may vary for different choices of a. For example, one can check that ^(1,2,3,4,5,6) has 888 chambers, whereas ^(1,2,3,4,5,7) has 892 chambers. Sturmfels <cit.> classified the combinatorial types of discriminantal arrangements of this form, showing that it has at least 876 and at most 892 chambers.

The all-coherence property for a projection of the form π:I^n Z, Z⊆^2 was completely classified by Edelman and Reiner <cit.>. In that paper, the authors observed that the number of rhombus tilings of Z admits a nice product formula when they are all-coherent, as given by MacMahon when Z is a hexagon <cit.> or Elnitsky when Z is an octogon <cit.>. Interestingly, many (but not all) of the discriminantal arrangements are free when the projection π has the all-coherence property. However, no direct connection between freeness and all-coherence is known. Bailey <cit.> observed a similar connection between all-coherence of the zonotopal tilings of a 3-dimensional zonotope Z and freeness of the corresponding discriminantal arrangement.









 §.§ Cellular strings



Fix an arrangement  of hyperplanes in ^n. Designate one of the chambers of  to be the fundamental chamber c_0. Given two chambers c and c' of , let S(c,c') denote the set of hyperplanes of  for which c and c' lie on opposite sides of the hyperplane. A gallery is a sequence of chambers c_0,…,c_l such that |S(c_i-1,c_i)|=1 for all i. This gallery may be drawn as a path in ^n connecting generic points in each chamber. It is reduced if |S(c_0,c_l)|=l, which means that it may be represented by a path that crosses each hyperplane at most once. For our purposes, a gallery is always assumed to be reduced and connecting a pair of antipodal chambers c_0, -c_0. Such a gallery defines a total order on the arrangement  where H<H^ if H is crossed before H^. If Z is a zonotope dual to , then a gallery on  corresponds to a monotone path on Z. For this correspondence, one chooses a linear functional π that is minimized on Z at v_0, the vertex whose normal cone is c_0.



The cellular strings of  may be defined in several equivalent ways, e.g. as sequences of faces, covectors (Section <ref>), or chambers. Given a fundamental chamber c_0, we orient each H∈ so that c_0 is on the negative side of H. We define a cellular string as a sequence of faces (F_1,…,F_l) of  such that for each H∈, there exists i∈[l] such that F_i is supported by H, F_j⊆ H^- if j<i and F_j⊆ H^+ if j>i. In particular, a cellular string determines an ordered set partition (_1,…,_l) of the set .

In terms of a zonotope Z with generic functional π, a cellular string is a sequence of faces (F_1,…,F_l) where F_1 contains the bottom vertex, F_l contains the top vertex, and adjacent faces F_i,F_i+1 meet at a vertex v_i such that π(x)≤π(v_i)≤π(y) for x∈ F_i, y∈ F_i+1. We note that this definition of a cellular string agrees with that of a π-induced subdivision given in Section <ref>.




Given a real vector space V, let  be a set of hyperplanes in V^* and let π be a generic point in V^*. For H∈, let v_H be a vector in V such that ⟨ v_H,H⟩=0 and π(v_H)>0, and let Z be the zonotope generated by {v_H: H∈}. Then an ordered set partition (_1,…,_l) of  defines a π-coherent cellular string of Z if and only if there exists ψ∈ V^* such that

    ψ(v_H)/π(v_H)=ψ(v_H^)/π(v_H^)

for H,H^ in the same block, and

    ψ(v_H)/π(v_H)<ψ(v_H^)/π(v_H^)

if H∈_i, H^∈_j, i<j.



First assume that the ordered set partition (_1,…,_l) of  defines a π-coherent cellular string. Let =(F_1,…,F_l) denote the sequence of faces of Z and (x_1,…,x_l) the sequence of covectors associated to this cellular string. Since this string is π-coherent, there exists a linear functional ψ such that Δ^ψ=.

For an index i, let p_i=∑_j: j<i∑_H∈_jv_H. The face F_i is the Minkowski sum of the point p_i with the image of [0,1]^|_i| under a matrix with column set {v_H: H∈_i}.

Fix some q∈ such that q>π(p_i) and q<π(p_i+v_H) for H∈. By the coherence assumption, the face π^-1(q)^ψ is equal to π^-1(q)∩ F_i. Fix H,H^∈, and set v=v_H, v^=v_H^. Pick λ,λ^∈[0,1] such that π(p_i+λ v)=q=π(p_i+λ^v^). Then λπ(v)=λ^π(v^).

Assume H and H^ are both in _i. Then ψ(p_i+λ v)=ψ(v_i+λ^v^), so λψ(v)=λ^ψ(v^). Consequently, ψ(v)/π(v)=ψ(v^)/π(v^).

On the other hand, suppose H∈_i and H^∈_j with i<j. Then p_i+λ^v^ is in Z but not in F_i. Hence, ψ(p_i+λ v)<ψ(p_i+λ^v^) holds, which implies ψ(v)/π(v)<ψ(v^)/π(v^).



Now let (_1,…,_l) be an ordered set partition of  and assume that there exists ψ∈ V^* such that

    ψ(v_H)/π(v_H)=ψ(v_H^)/π(v_H^)

for H,H^ in the same block, and

    ψ(v_H)/π(v_H)<ψ(v_H^)/π(v_H^)

if H∈_i, H^∈_j, i<j.

For each i, let λ_i denote the ratio ψ(v_H)/π(v_H) for some H∈_i. Let p_i=∑_j: j<i∑_H∈_jv_H. Let F_i be the zonotope generated by {v_H: H∈_i}, translated by p_i.

We claim that F_i is a face of Z, namely that F_i=Z^ψ_i where ψ_i=ψ-λ_iπ. For H∈,


    ψ_i(v_H)=ψ(v_H)-λ_iπ(v_H)=0 H∈_i
    <0 H∈_j, j<i
    >0 H∈_j, j>i.


Using the case H∈_i, we see that ψ_i takes a common value ψ_i(p_i) on the zonotope F_i. The zonotope Z is the set of points

    Z={∑_H∈μ_H v_H: (μ_H)∈[0,1]^}.


For p∈ Z, there exists a representation p-p_i=∑_H∈μ_H v_H where μ_H≤ 0 for H∈_j, j<i and μ_H≥ 0 for H∈_j, j>i. By the previous calculation, we have ψ_i(p-p_i)≥ 0. Hence, ψ_i is minimized on Z at F_i.

The image π(F_i) is the interval [π(p_i),π(p_i+1)]. Hence, the images of the faces F_i partition the image of Z into intervals. For q∈π(F_i), ψ_i is minimized on π^-1(q) at F_i∩π^-1(q). But ψ_i=ψ-λ_iπ and π is constant on π^-1(q), so ψ is minimized on π^-1(q) at F_i∩π^-1(q) as well. Therefore, (F_1,…,F_l) is a π-coherent cellular string induced by ψ.



Since the set of cellular strings of  starting from c_0 does not depend on the choice of π∈ c_0, we may define the pair (,c_0) to be all-coherent if there exists some π in the interior of c_0 such that π:Z^1 is all-coherent. If π is replaced by some other π^ in c_0, it would still be all-coherent by Corollary <ref>.


Given a gallery γ in  and an intersection subspace X, there is an induced gallery γ_X on the localized arrangement _X where γ_X crosses elements of _X in the same order as γ. If X∈ L_2, then there are two possibilities for γ_X. If γ and γ^ are galleries, the L_2-separation set L_2(γ,γ^) is the set of X∈ L_2 such that γ_X≠γ^_X. The set of galleries forms a graph such that γ and γ^ are adjacent if |L_2(γ,γ^)|=1.


The graph of galleries is known to be connected <cit.>. More recently, the diameter of this graph was investigated by Reiner and Roichman <cit.>. In their paper, they observe that the graph-theoretic distance between two galleries γ and γ^ is bounded below by |L_2(γ,γ^)|. On the other hand, if (,c_0) is all-coherent, then there exists a path between γ and γ^ of length equal to |L_2(γ,γ^)|. We conjecture that the converse statement holds: If the distance between any reduced galleries γ and γ^ is given by |L_2(γ,γ^)|, then (,c_0) is all-coherent.





 §.§ An all-coherent family


In this section, we consider an explicit 2-parameter family of zonotopes Z with linear functional π such that (Z,π) is all-coherent. We present this example in detail as it will be useful for the classification in Section <ref>.

Fix positive integers r,m. Let e_1,…,e_r be the elementary basis vectors in ^r, and define vectors a_1,…,a_m where a_i=ie_r+∑_j=1^re_j. Let Z be the zonotope generated by E={a_1,…,a_m,e_1,…,e_r}. Let π:^r be the sum of coordinates function. In particular, π(e_i)=1 and π(a_j)=j+r.

We claim that (Z,π) is all-coherent. To prove this, we first determine some necessary conditions for a permutation of E to define a monotone path. Then we show that each such permutation may be realized as a coherent monotone path by a suitable linear functional. Finally, we invoke Lemma <ref> to complete the proof.

Let p be a monotone path on Z, and let ≺ be the induced total order on E. For 1≤ k<l≤ m, we have a relation (l-k)e_r-a_l+a_k=0, so either e_r≺ a_l≺ a_k or a_k≺ a_l≺ e_r holds. Combining these relations, we have either e_r≺ a_m≺⋯≺ a_1 or a_1≺⋯≺ a_m≺ e_r. By the relation a_i=ie_r+∑_j=1^re_j, the maximum and minimum elements under ≺ must be elementary basis vectors.

Now assume ≺ is a total ordering on E whose maximum and minimum elements are elementary basis vectors, and either e_r≺ a_m≺⋯≺ a_1 or a_1≺⋯≺ a_m≺ e_r holds. We construct a linear functional ψ realizing ≺ as a coherent monotone path. To do so, we distinguish three cases:


  *  e_r is maximal with respect to ≺,

  *  e_r is minimal with repsect to ≺, or

  *  e_r is neither minimal nor maximal.


We let ψ_j=ψ(e_j) and α=∑_j=1^rψ_j. We observe that ψ(e_j)/π(e_j)=ψ_j and ψ(a_i)/π(a_i)=(α+iψ_r)/(i+r). We assume throughout that ψ is chosen so that if e_i≺ e_j then ψ_i<ψ_j. We impose additional constraints on ψ separately for the three cases above.

Suppose we are in Case <ref>, and let e_k be the minimum element under ≺. Set ψ_r=1, and for j∈[r-1]{k}, let ψ_j be a positive number such that 0<ψ_j<1 and


  * if a_i≺ e_j then i/i+r<ψ_j, and

  * if e_j≺ a_i then ψ_j<i/i+r.


Finally, choose ψ_k<0 such that α=0. Then ψ(a_i)/π(a_i)=i/i+r. By the preceding conditions, we conclude that ≺ is realized as a coherent monotone path by ψ.

Case <ref> follows by similar reasoning as Case <ref>. Assume we are in Case <ref>, and let e_k and e_l be the minimum and maximum elements of E under ≺, respectively. Furthermore, assume that a_1≺⋯≺ a_m≺ e_r holds. Set ψ_r=0, and for j∈[r-1]{k,l}, let ψ_j be a real number such that


  * if a_i≺ e_j then -1/i+r<ψ_j, and

  * if e_j≺ a_i then ψ_j<-1/i+r.


Finally, choose ψ_k<0, ψ_l>0 such that ψ_k<ψ_i<ψ_l for all i and α=-1. Then ψ(a_i)/π(a_i)=-1/i+r, and we again conclude that ≺ is realized as a coherent monotone path by ψ. A similar argument exists when e_r≺ a_m≺⋯≺ a_1 holds. In that case, we fix α=1 and choose ψ accordingly.

We have now proven that every monotone path is coherent. By Lemma <ref>, this implies that every cellular string is coherent.

In our proof of all-coherence of (Z,π), we identified the monotone paths on Z with total orderings of E such that



  *  the maximum and minimum elements of E are equal to e_k,e_l for some k,l, and

  *  either e_r≺ a_m≺⋯≺ a_1 or a_1≺⋯≺ a_m≺ e_r holds.


Using this characterization of monotone paths, we may q-count them as follows. Let γ_0 be the monotone path corresponding to the sequence (e_1,…,e_r-1,a_1,…,a_m,e_r). Then

    ∑_γq^|L_2(γ_0,γ)|=(1+q^m+2)[r-1]!_q[m+r-1
    m+1]_q.


We use condition <ref> to distinguish two cases for a monotone path γ. If a_1≺⋯≺ a_m≺ e_r, then γ may be constructed by taking an arbitrary permutation τ of [r-1] and shuffling (e_τ(2),…,e_τ(r-1)) with (a_1,…,a_m,e_r). We may identify this shuffle with a partition λ in a (r-2)×(m+1) box. Then |L_2(γ_0,γ)| is equal to the number of inversions of τ plus the size of λ. Hence, these monotone paths contribute

    [r-1]!_q[m+r-1
    m+1]_q

to the q-count. On the other hand, if e_r≺ a_m≺⋯≺ a_1 holds, then γ may be constructed in the same way except that (e_τ(1),…,e_τ(r-2)) is shuffled with (e_r,a_m,…,a_1). Flipping (a_1,…,a_m,e_r) and pushing e_τ(r-1) to the end adds a factor of q^m+2 to the previous q-count for these paths.


  In Example <ref>, we noted the large overlap between zonogons whose rhombic tilings are all coherent and whose discriminantal arrangements are free, as observed in <cit.>. In contrast, the arrangements dual to the fiber zonotopes in the 2-parameter family of zonotopes described in this section are not free in general. This lack of freeness is already present when r=4 and m=1. Indeed, its characteristic polynomial (x-1)x(x^2 - 9x + 26) does not factor into linear polynomials over .






 §.§ Covector axioms


Fix a finite set E. Recall a sign vector is an element of {+,-,0}^E. Sign vectors form a monoid under composition, where

    (x∘ y)(e)=x(e)     x(e)≠ 0
    y(e)    ,

for x,y∈{+,-,0}^E. We note that the identity element of the monoid is the 0-vector. The set {+,-,0} is partially ordered where 0<+, 0<-, and + and - are incomparable. This ordering extends to {+,-,0}^E by the product ordering. The negation -x is the vector whose signs are reversed from x. Given sign vectors x,y, the separation set S(x,y) is the set of elements e∈ E such that x(e)=-y(e) and x(e)≠ 0. The support of a sign vector x is the set (x)={e∈ E: x(e)≠ 0}.

A submonoid  of sign vectors is said to be the set of covectors of an oriented matroid if it is closed under negation and


  *  for x,y∈, e∈ S(x,y), there exists z∈ such that z(e)=0 and z(f)=(x∘ y)(f)=(y∘ x)(f) for f∈ E S(x,y). (elimination)


As an example, the set of covectors of a hyperplane arrangement defined in <ref> satisfies these properties. An oriented matroid that comes from a hyperplane arrangement is said to be realizable. While not every oriented matroid is realizable, a theorem of Folkman and Lawrence states that oriented matroids are “close” to being realizable <cit.>. For our purposes, we use the following consequence: the proper part of the poset of covectors of any oriented matroid is isomorphic to the poset of faces of a regular CW-sphere.

The set of covectors completely determines the rest of the data associated with an oriented matroid. Hence, we say that two oriented matroids are equal if they have the same set of covectors. For a discussion of other axiomatizations of oriented matroids, we refer to <cit.>.


Cellular strings may be defined at the level of oriented matroids as they were for zonotopes in Section <ref>. If (,E) is an acyclic oriented matroid with c_0=-^E being the all-negative covector, then a cellular string of  is a sequence of covectors (x_1,…,x_l) such that x_1∘ c_0=c_0, x_l∘(-c_0)=-c_0 and x_i∘(-c_0)=x_i+1∘ c_0 for all i. We let ω() denote the set of cellular strings of .

The main difference between cellular strings of zonotopes and oriented matroids is that we do not know of a notion of “coherence” for oriented matroids. In particular, given two realizations (Z,π),(Z^,π^) of an acyclic oriented matroid, a cellular string may be coherent for (Z,π) but incoherent for (Z^,π^). However, using Theorem <ref>, we can say  is all-coherent if ω() is homeomorphic to a sphere.








§ ALL-COHERENCE PROPERTY FOR ZONOTOPES






 §.§ Coherence of monotone paths


The main result in this section is Lemma <ref>, which says that if all monotone paths of a zonotope are coherent, then so is every cellular string. This lemma appeared previously as <cit.>. 


For this section, we fix a zonotope Z=Z(A) for some matrix A and generic linear functional π. We let E denote the set of column vectors of A. We will assume that E contains no zero vectors nor any parallel or antiparallel pairs of vectors. Furthermore, we scale the elements of E so that π(e)=1 for each e∈ E. This results in no loss of generality as the poset of cellular strings is invariant under these changes.




Let  be a cellular string. If every cellular string properly refining  is coherent, then  is coherent.




Assume that every cellular string properly refining  is coherent. Let (E_1,…,E_l) be the ordered set partition of E induced by . Let ^(1) be a maximal proper cellular string of . Then ^(1) corresponds to the ordered set partition

    (E_1,…,E_k-1,E_1^,…,E_m^,E_k+1,…,E_l)

which differs from  by breaking up a unique block E_k. Let F be the element of  generated by E_k. Then F is a zonotope containing a cellular string generated by (E_1^,…,E_m^). Consequently, F admits an opposite cellular string generated by (E_m^,…,E_1^). Hence, there is a cellular string ^(2) of Z generated by

    (E_1,…,E_k-1,E_m^,…,E_1^,E_k+1,…,E_l).


By assumption, both ^(1) and ^(2) are coherent cellular strings. Hence, there exist linear functionals ψ^(1),ψ^(2) such that ^(i)=Δ^ψ^(i) for i=1,2. By Lemma <ref> and the normalization assumption (π(e)=1 for all e∈ E), there is a unique value ψ^(i)_E_j=ψ^(i)(e) for e∈ E_j. We may similarly define ψ^(i)_E_j^ for blocks E_j^.

Let t be the smallest number in the interval [0,1] such that there exists j∈{1,…,m-1} with


    (1-t)ψ^(1)_E_j^+tψ^(2)_E_j^=(1-t)ψ^(1)_E_j+1^+tψ^(2)_E_j+1^.


Let ψ=(1-t)ψ^(1)+tψ^(2). It is clear that ψ is constant on each block of ^(1). As before, we let ψ_E_j=ψ(e) for e∈ E_j and ψ_E_j^=ψ(e) for e∈ E_j^. Then for e∈ E_k, we have


    ψ_E_1<⋯<ψ_E_k-1<ψ_E_1^≤⋯≤ψ_E_m^<ψ_E_k+1<⋯<ψ_E_l


and ψ_E_j^=ψ_E_j+1^. Hence Δ^ψ is a cellular string that refines  and is properly refined by ^(1). By the maximality of ^(1), we deduce =Δ^ψ, as desired.



Letting  be the trivial cellular string, we deduce the following corollary.


If every monotone path is coherent, then (Z,π) is all-coherent.





The analogue of Lemma <ref> for general polytope projections fails to hold. For example, there exists a point configuration with two coherent triangulations connected by an incoherent bistellar flip <cit.>.







  Consider the zonotope in Figure <ref> with a linear functional π such that the bolded path is monotone. This path can be flipped to the left through the middle hexagon face or to the right through one of the rhombic faces. Indeed, one can check that every monotone path is adjacent to exactly two monotone paths. Hence, the graph of monotone paths is a cycle. Since the subgraph of coherent paths is also a cycle, we conclude that every monotone path is coherent. Corollary <ref> then implies that the zonotope is all-coherent.







 §.§ Gradedness


The face lattice of a polytope is graded by dimension. Thus, if (,c_0) is all-coherent, then ω(,c_0) is a graded lattice. In practice, the poset of cellular strings is typically not graded, which makes this a useful criterion for the all-coherence property. In the following proposition, we give a useful refinement to this criterion.


Let (,c_0) be all-coherent, and let r=().


  *  ω(,c_0) is graded and every maximal chain contains exactly r elements.

  *  There does not exist a proper cellular string  such that ∑_x∈( x-1)≥ r-1.




The first claim is immediate from Theorem <ref>.

Let  be a cellular string of (,c_0), and suppose it contains a covector x such that x>1. Set X= x. Let y be any covector such that x≤ y and x= y+1. Then y_X is a cocircuit of _X, and there exists a cellular string ^ of (_X,(c_0)_X) containing y_X. This cellular string lifts to a partial cellular string of  between x∘ c_0 and x∘(-c_0). Replacing x in  by this partial cellular string, we obtain a new cellular string ^< such that

    1+∑_z∈^( z-1)≥∑_z∈( z-1).


Suppose (,c_0) has a proper cellular string  such that ∑_x∈( x-1)≥ r-1. Then we may apply the above construction repeatedly to obtain a chain with at least r elements. Extending this chain by the trivial cellular string gives a chain of with at least r+1 elements, contradicting (<ref>).




Proposition <ref>(<ref>) gives a useful test for incoherence, as in the following example.


Let Z be the image of the 4-cube under the map

    π=(1     0     1     0
    0     1     1     0
    0     1     0     1)

and define f:^3 such that f(x,y,z)=x+y+z. Let  be the acyclic oriented matroid associated to (Z,f) with ground set {a,b,c,d} corresponding to the six columns of π. We order the ground set a<b<c<d to agree with the ordering of the columns of π. Then  has a unique circuit (+,+,-,-), along with its negative (-,-,+,+). The other 14 elements of {+,-}^{a,b,c,d} are maximal covectors of .

The oriented matroid  has a cellular string consisting of two cocircuits (0,-,-,0) and (+,0,0,+). But ((0,-,-,0) - 1) + ((+,0,0,+) - 1) = 2 = -1, so (Z,f) is not all-coherent by Proposition <ref>(<ref>).







 §.§ Matroid operations




Let V be a real vector space of dimension r. Fix an r× n real matrix A, and let E be the set of column vectors of A. We let Z=Z(A) and let π be a linear functional on ^r that is generic with respect to Z. This defines an acyclic oriented matroid . Since the coherence of cellular strings is invariant under scaling the columns of A, we will assume throughout this section that π(e)=1 for all e∈ E. Let  be the set of hyperplanes in V^* for which () is the normal fan of Z. Let c_0 be the chamber of  containing π. For simplicity, we will assume that the set E does not contain any zero vectors or pairs of parallel vectors.





Let Z be the direct sum of Z with an m-cube. We realize this zonotope by a matrix A=A⊕ I_m where I_m is the rank m identity matrix. If π is a generic linear functional on ^r+m whose restriction to Z is equal to π, then (Z,π) is all-coherent if and only if (Z,π) is all-coherent.



It suffices to prove the lemma for m=1 since if m>1, the zonotope Z decomposes as (Z⊕[0,1]^m-1)⊕[0,1], and the result follows by induction. Hence, we will assume m=1 for the remainder of the proof.

Let e be the unit vector in the last coordinate of ^r+1. Let π be a generic linear functional on ^r+1 whose restriction to Z is π. We may assume that π(e)=1 without affecting coherence of a cellular string on Z.

Let γ be a cellular string on Z. Let γ be the cellular string on Z obtained by deleting e from γ. Suppose γ is π-coherent. Then there exists a linear functional ψ on ^r that picks out γ. Let (E_1,…,E_l) be the ordered set partition of {a_1,…,a_n} induced by γ. This means for a∈ E_i, b∈ E_j, ψ(a)≤ψ(b) if i≤ j.

We define a linear functional ψ that determines the string γ as follows. For each a_i, set ψ(a_i)=ψ(a_i). If e is added to a block E_i to form γ, then set ψ(e)=ψ(a) for some a∈ E_i. If e is in its own block between E_i and E_i+1, then set ψ(e) to be a value strictly between ψ(a) and ψ(b) where a∈ E_i, b∈ E_i+1. In either case, we have produced the desired linear functional.

Conversely, if we start with a π-coherent string γ induced by ψ, then ψ induces γ on Z. This completes the proof.







For oriented matroids (,E),(^,E^) on disjoint ground sets E,E^, the direct sum ⊕^ of  and ^ is an oriented matroid with covectors ()×(^). An oriented matroid is indecomposable if cannot be expressed as a direct sum of two nontrivial oriented matroids. It is straightforward to show that the circuits of ⊕^ is the union of ()×{0} and {0}×(^) <cit.>.



Let  be an acyclic oriented matroid that decomposes as _1⊕_2. If both _1 and _2 have a circuit supported by at least 3 elements, then  is not all-coherent.



Let E_i be the ground set of _i for i=1,2. Assume that _1 and _2 each have a circuit supported by at least 3 elements. Then for i=1,2 there exists x_i∈(_i) such that x_i is a corank 1 covector and _i x_i^-1(0)≥ 2.

Let _i=(y_1^(i),y_2^(i),…,y_l_i^(i)) be a cellular string of _i containing x_i such that each cell y_j^(i) is rank 1 unless y_j^(i)=x_i for i=1,2. Without loss of generality we may assume that l_1≤ l_2. By the assumption on x_i, we have l_1≥ 3. We define a new string =(y_1,…,y_m) for  where y_j=y_j^(1)⊕ y_j^(2) if j≤ l_1 and y_j=+^E_1⊕ y_j^(2) if l_1<j≤ l_2. Then


    ∑( y_j-1)    = ∑_j=1^l_1 y_j^(1)+∑_j=1^l_2( y_j^(2)-1)
       ≥ (_1+1)+(_2-1)
       =.


By Proposition <ref>, we conclude that  is not all-coherent.




Let Z be the image of the 6-cube under the map

    (1     0     .5     0     0     0
    0     1     .5     0     0     0
    0     0     0     1     0     .5
    0     0     0     0     1     .5)

and define π:^4 such that π(w,x,y,z)=w+x+y+z. We note that π(v)=1 for each column vector v. Let  be the acyclic oriented matroid associated to (Z,π) with ground set {a,b,c,d,e,f} corresponding to the four columns of the matrix. Then  decomposes into two rank 2 matroids, each of corank 1. Hence, (Z,π) is not all-coherent.

In particular, we claim that the cellular string {0–0–, +–+-0, +-0+-+, +0++0+} is not coherent. Suppose to the contrary that it is picked out by a linear functional ψ:^4. By definition, this means

    ψ(a)=ψ(d)<ψ(f)<ψ(c)<ψ(b)=ψ(e).

But the first and last equality imply

    2ψ(c) = ψ(a)+ψ(b) = ψ(d)+ψ(e)=2ψ(f),

contradicting the inequality ψ(f)<ψ(c).





The last general construction we consider are weak map images. Given two oriented matroids ,^ with the same ground set E, there is a weak map ^ if for every circuit x of , there exists a circuit y of ^ such that y≤ x. That is, every circuit of  “contains” a circuit of ^. Geometrically, a weak map image of a vector configuration is obtained by moving the vectors to a more special position. The map is said to be rank-preserving if  and ^ have the same rank. We remark that if e∈ E, there exist weak maps /e and e. Here, we view the contraction /e as an oriented matroid on E where e is a coloop, and we view the deletion e as an oriented matroid on E where e is a loop. In this way, the weak maps /e and e are both rank-preserving.


Let ,^ be acyclic oriented matroids with the same rank. Assume that there is a rank-preserving weak map ^. If  is all-coherent, then so is ^.


To prove this proposition, one may observe that the list of oriented matroids in the classification in Section <ref> is closed under rank-preserving weak map images. Unfortunately, we do not have a direct proof.

The rank preservation assumption in Proposition <ref> is necessary since the n-cube I^n is all-coherent, but every oriented matroid on E={1,…,n} is a weak map image of the free oriented matroid (I^n), including incoherent ones.







§ CLASSIFICATION




 §.§ Affine models and monotone families


Let Z be a zonotope generated by v_1, …, v_n ∈ V and let π∈ V^∗ be a generic linear functional. Let H_π be the hyperplane { x ∈ V : π(x) = 1 }. We define

    (Z,π) := ⋃_i=1^n ({ tv_i : t ∈}∩ H_π).

Thus, (Z,π) is a set of n points in H_π. Note that the oriented matroid of Z depends only on the oriented matroid of (Z,π) as an affine point set. In particular, the all-coherence property depends only on this oriented matroid. We will call any set of points in affine space with the same oriented matroid as (Z,π) an affine model for (Z,π).

Given an affine space W, we define a (closed) half-space of W to be a subset of the form {x ∈ W : ψ (x) ≤ c } for some affine map ψ : W → and c ∈. Note that ∅ and W are half-spaces of W in this definition. We denote the set of all half-spaces of W by HS(W), and give it a topology in the obvious way. For K ∈ HS(W), we denote by ∂ K and K^∘ the boundary and interior, respectively, of K as a subspace of W.

If  is a finite set of points in W, we define a monotone family with respect to  to be a continuous path {K_t}_t ∈ [0,1] in HS(W) such that


  * K_0 = ∅

  * K_1 = W

  * For every p ∈, there exists t_p ∈ (0,1) such that p ∈∂ K_t_p and p ∈ K_t^∘ for all t > t_p.
 
To each monotone family {K_t}_t ∈ [0,1] with respect to  we associate an ordered set partition of  as follows: Let t_1 < … < t_l be all the numbers in (0,1) such that ∂ K_t_i∩≠∅. Then the ordered set partition associated to {K_t}_t ∈ [0,1] is

    (∂ K_t_1∩, ∂ K_t_2∩, …, ∂ K_t_l∩).

We call any partition of  obtained in this way a monotone partition. As the following proposition states, monotone partitions of affine models are in bijection with proper cellular strings.

 
Let  be an affine model for (Z,π). Then there is a bijection from the set of all monotone partitions of  to the set of all proper cellular strings of (Z,π), and such that the image of (E_1,…,E_l) under this bijection is (F_1,…,F_l) where (F_i) = | E_i |.



We may assume = (Z,π). We have a homeomorphism from S(V^∗) := {ψ∈ V^∗ : ‖ψ‖ = 1} to HS(H_π) given by ψ↦{ x ∈ H_π : ψ(x) ≥ 0 }. Recall that each proper cellular string of (Z,π) can be specified by a path γ : [0,1] → S(V^∗) such that γ(0) = -π/‖π‖, γ(1) = π/‖π‖, and for each i, γ intersects the hyperplane {ψ∈ V^∗ : ψ(v_i) = 0 } exactly once. The image of the set of all such paths under the above homeomorphism is precisely the set of monotone families with respect to (Z,π). It is easy to check that this homeomorphism induces a bijection between the proper cellular strings of (Z,π) and the monotone partitions of (Z,π), and this bijection satisfies the desired property.


In the proof of classification we will need the following lemma.

 
Let  be a finite set of points in an affine space W. Suppose that K_1, …, K_m ∈ HS(W) are such that for each 1 ≤ i < m, (K_i ∖ K_i+1^∘) ∩ = ∅. Then there exists a monotone family with respect to  containing K_1, …, K_m.



We define a family {L_t}_t ∈ (-∞,∞) of half-spaces of W as follows: For i = 1, …, m, let L_i = K_i. If K_1 = {x ∈ W : ψ_1 (x) ≤ c_1 }, then for t < 1 define

    L_t = { x ∈ W : ψ_1(x) ≤ c_1 + t - 1 }

and if K_m = {x ∈ W : ψ_m (x) ≤ c_m }, for t > m define

    L_t = { x ∈ W : ψ_m(x) ≤ c_m + t - m }.

Finally, if i < t < i+1 for i=1, …, m-1, we define L_t as follows. Let ℓ_i = ∂ K_i ∩∂ K_i+1. Then ℓ_i is a codimension 2 affine subspace of W, and the set

    Φ_i := { K ∈ HS(W) : ∂ K ⊃ℓ_i }

is homeomorphic to a circle and contains K_i, K_i+1. We let { L_t }_t ∈ [i,i+1] be the shortest arc in Φ_i with L_i = K_i and L_i+1 = K_i+1.

The condition (K_i ∖ K_i+1^∘) ∩ = ∅ guarantees that in the above construction, for every p ∈ there exists t_p ∈ (-∞,∞) such that p ∈∂ L_t_p and p ∈ L_t^∘ for all t > t_p. Thus, setting L_-∞ = ∅ and L_∞ = W we obtain a monotone family with respect to  containing K_1, …, K_m.




 §.§ Classification theorem


To classify the all-coherent zonotopes, it suffices to give their affine models. Here are four such affine models:



  * The set U_2,n of n points in a straight line. This corresponds to a zonotope of dimension 2 and any generic linear functional.

  * For r ≥ 3, the set E_r,m = {e_1,…,e_r,a_1,…,a_m}, where e_1, …, e_r are the vertices of an (r-1)-dimensional simplex and a_1, …, a_m are points in the interior of the simplex such that a_1, …, a_m, e_r are collinear. This is the affine model for the all-coherent family in Section <ref>.

  * For r ≥ 3, the set Ẽ_r,m, which is defined in the same way as E_r,m except a_1 is on the boundary of the simplex.

  * The set R_3, the set of 6 points in ^2 shown in Figure <ref>. The corresponding zonotope Z for R_3 is shown in Figure <ref>, with π the vertical direction in the figure. One can check that the poset of proper cellular strings of (Z,π) is homoemorphic to a circle, which implies the all-coherence property for R_3.

 


We now show that, up to the addition of coloops, these are the only all-coherent affine models.


Let Z be a zonotope of dimension r and π a generic linear functional. The following are equivalent.


  * (Z,π) is all-coherent.

  * There does not exist a proper cellular string (F_1,…,F_l) of (Z,π) with

    ∑_i=1^l ((F_i)-1) ≥ r-1.


  * The affine model for (Z,π) is E ∪ L, where E is of the form ∅, U_2,n, E_r,m, Ẽ_r,m, or R_3 and L is a (possibly empty) set of coloops of E ∪ L.



(1)(2) follows from Proposition <ref>, and (3)(1) has been proven earlier. Our goal is to prove (2)(3).

Assume (2) holds. Let  be an affine model for (Z,π). We may assume  is full-dimensional in ^r-1. For any polytope Q, let V(Q) denote its vertex set. We first show the following.


The convex hull of  is a simplex.



Suppose the contrary, and let Q be the convex hull of . Let F be any facet of Q. If there are at least two vertices of Q not in F, then there is an edge e of Q disjoint from F. Otherwise, Q is a pyramid over F, and since Q is not a simplex, if we replace F with any other facet of Q then there will be two vertices of Q not in F. So we may assume there is an edge e of Q disjoint from F.

Let K_1 be the half-space of ^r-1 which does not contain Q and whose boundary supports F. Let K_2 be any half-space of ^r-1 which contains Q and whose boundary supports e. Then (K_1 ∖ K_2^∘) ∩ Q = ∅, so by Lemma <ref>, there is a monotone family with respect to  containing K_1, K_2. In particular, the associated monotone partition of  contains V(F) and V(e). Thus, by Proposition <ref>, there is a cellular string (F_1,…,F_l) of (Z,π) with

    ∑_i=1^l ((F_i)-1) ≥ (| V(F) | -1) + (| V(e) | - 1) ≥ (r-2) + 1 = r-1.

This contradicts (2), proving the claim.


Now, let σ denote the convex hull of .

 
If a_1, a_2 are distinct points in ∖ V(σ), then there exists b ∈ V(σ) such that a_1, a_2, and b are collinear. 



Suppose the contrary. Let ℓ be the line through a_1 and a_2, and let p_1, p_2 be the endpoints of the segment ℓ∩σ. Let C_1 and C_2 be the vertex sets of the minimal faces of σ containing p_1 and p_2, respectively. By assumption, C_1 and C_2 have at least two elements. It is thus possible to choose a partition (B_1,B_2) of B such that C_i ⊈B_j for all i, j.

Let σ_1, σ_2 be the faces of σ with vertex sets B_1, B_2 respectively. Let K_1 be a half-space of ^r-1 which does not contain σ and whose boundary supports σ_1. Let K_2 be a half-space of ^r-1 whose boundary contains ℓ and such that σ_1 ⊂ K_2^∘ and σ_2 ∩ K_2 = ∅. (This is possible by the definitions of σ_1 and σ_2.) Finally, let K_3 be a half-space of ^r-1 which contains σ and whose boundary supports σ_3. Then (K_1 ∖ K_2^∘) ∩σ = (K_2 ∖ K_3^∘) ∩σ = ∅, so by Lemma <ref> there is a monotone family with respect to  containing K_1, K_2, K_3. Hence, there is a cellular string (F_1,…,F_l) of (Z,π) with

    ∑_i=1^l ((F_i)-1) ≥ (| V(σ_1) | - 1) + (|{a_1,a_2}| - 1) + (| V(σ_2) | - 1) = r-1

which contradicts (2).


We can now complete the proof. If ∖ V(σ) has at most one points, then it is easy to see that  is of one of the forms described in (3). Assume ∖ V(σ) has at least two distinct points a_1, a_2, and let ℓ_12 be the line through these points. By Proposition <ref>, ℓ_12 contains some vertex b_12 of σ. If every point of ∖ V(σ) is on ℓ_12, then  is of one of the forms described in (3), as desired.

Assume there is some a_3 ∈∖ V(σ) not on ℓ_12. Then by Proposition <ref>, there are vertices b_13 and b_23 of σ such that a_1, a_3, b_13 lie on a line ℓ_13 and a_2, a_3, b_23 lie on a line ℓ_23. Moreover, since a_3 ∉ℓ_12, b_12≠ b_13≠ b_12. Since ℓ_12 and ℓ_13 intersect at a_1, there is a 2-plane P containing ℓ_12 and ℓ_13. Since a_2, a_3 ∈ P, we have ℓ_23⊂ P, and hence b_23∈ P. Hence a_1, a_2, a_3, b_12, b_13, b_23 all lie in P, and thus a_1, a_2, a_3 are all in the face F of σ with vertices b_12, b_13, b_23. It is easy to check that these six points must be in the configuration R_3.

Now suppose that there is some a_4 ∈∖ (V(σ) ∪{a_1,a_2,a_3}). The above argument works with a_4 instead of a_3. However, because a_1 is in the interior of F, F is the only 2-face of σ containing a_1, and hence a_4 ∈ F. However, it is easy to check that one cannot have 4 distinct points in a triangle, not all on the same line, such that the line through any two of them passes through a vertex of the triangle. Thus there is no such a_4. Hence, = R_3 ∪ L, where L is a set of coloops of . This concludes the proof.






§ ACKNOWLEDGEMENTS


The authors thank Victor Reiner for offering advice at several stages in this project. The second author was supported by NSF/DMS-1351590. The fourth author was partially supported by NSF/DMS-1148634. Part of this material was based on work supported by NSF/DMS-1440140 while the third and fourth authors were in residence at the Mathematical Sciences Research Institute in Fall 2017.




plain


