2

The abstract combinatorial structure of a polytope is sometimes called its "face lattice". For example, see this or this.

But this is not always a lattice.

In a digon, the two edges are different upper bounds for the set of vertices, so there is no unique least upper bound. In a hemicube, a pair of vertices ($a,b$ in the wiki image) has an edge ($1$) and a face ($III$) as two incomparable upper bounds.

What conditions on the polytope are necessary or sufficient for it to be a lattice? For example, I suppose convexity is sufficient; and the "atomistic" property looks relevant.

mr_e_man
  • 5,364
  • I would note that the hemicube is an atomistic polytope (according to the definition given on that Wiki page). Also, I think that that definition differs slightly from the purely order-theoretic definition. – mhum Jan 16 '20 at 01:28
  • 1
    Also, FWIW, it seems to me that the term "face lattice" is almost always only used in the context of convex polytopes and almost never used in the case of general, abstract polytopes for the simple reason that (as you've observed) the face posets of abstract polytopes are not guaranteed to be lattices. – mhum Jan 16 '20 at 02:09
  • I haven't yet seen a proof of the sufficiency of convexity. Do you know where I can find one? If it's easy, you could include it in your answer. – mr_e_man Jan 16 '20 at 02:17
  • 1
    Hm. It seems that the fact that the face poset of a convex polytope is a lattice is often taken to be so elementary that neither a proof nor even a reference to a proof is provided in many sources. If I can't find a good reference or proof sketch, I'll try to reconstruct one myself. – mhum Jan 16 '20 at 02:48
  • ...No, the hemicube is not atomistic by either definition; all 2-faces (and the 3-face) have the same vertex set. But we can replace this with a different example, from an old answer of mine: a tiling of twelve rhombi on a flat torus; it is atomistic, but the vertices ${U,X}$ have $AUBX$ and $DUEX$ as two incomparable upper bounds. – mr_e_man Jan 19 '20 at 20:30
  • Ah! You are absolutely right. This is quite a blunder. In fact, the hemicube (and digon) both belong to a class that McMullen & Schute call "flat" -- each facet contains every vertex which is almost the exact opposite of atomistic. – mhum Jan 20 '20 at 19:03
  • Atomisticity (by the other definition) implies vertex-describability. We're given that any face $A$ is a supremum of some set of vertices ${W_i}$. Clearly $A$ is an upper bound for the set ${V_i}\supseteq{W_i}$ of all vertices below $A$. If $X$ is any other upper bound for ${V_i}$, then $X$ is also an upper bound for ${W_i}$, so $X\geq\sup{W_i}=A$; therefore $A=\sup{V_i}$. Now if two faces $A,B$ have the same vertex set ${V_i}$, then $A=\sup{V_i}$ and $B=\sup{V_i}$, so $A=B$. – mr_e_man Jan 21 '20 at 19:41
  • And vertex-describability does not imply atomisticity. Take a $4$-hosohedron and put extra vertices on three of the edges to split them in half. The resulting polyhedron has two quadrilateral faces and two triangle faces, and it is vertex-describable. But it's not atomistic, since the unsplit edge would have to be the supremum of its two vertices (the "north and south poles"), but the quadrilaterals are different incomparable upper bounds for the same two vertices. – mr_e_man Jan 21 '20 at 19:55

3 Answers3

3

The argument in Wikipedia handles the case of a convex body fairly straightforwardly: if we have a (minimal) description of a $d$-dimensional body $B$ as the intersection of a set $H_1, H_2, \ldots, H_n$ of half-$d$-spaces defined as $H_i=\{v: v\cdot \mathbf{n}_i\leq c_i\}$, then each face is obtained by replacing some subset of the inequalities by equalities; i.e., by intersecting $B$ with some number of suitably defined $(d-1)$-planes $P_i=\{v: v\cdot\mathbf{n}_i=c_i\}$. Then if $\mathcal{F}_1$ is the face obtained by intersecting $B$ with $\{P_i: i\in S_1\}$ and $\mathcal{F}_2$ is the face obtained by intersecting $B$ with $\{P_i: i\in S_2\}$, then their meet and join in the face lattice are the faces obtained by intersecting $B$ with $\{P_i: i\in S_1\cup S_2\}$ and $\{P_i: i\in S_1\cap S_2\}$.

Steven Stadnicki
  • 51,746
  • Consider the four 2-faces $F_i$ around a vertex $V$ of an octahedron, where $F_1$ and $F_3$ are opposite, intersecting only at $V$. Thus $V$ can be described as the intersection of the two planes $F_1,F_3$; but then, since ${1,3}\cap{2}={}$, the join of $V$ and $F_2$ would be the whole octahedron, while it should be just $F_2$. So I guess $V$ must be described with all four planes. – mr_e_man Jan 16 '20 at 21:20
  • @mr_e_man You're right, and I totally missed that in this description — I had hit the same issue in other attempts to say basically the same thing, but missed that it was relevant here. I think as long as you use the maximal descriptions of each node in the face lattice then this is still fine, but I'm definitely less sure. – Steven Stadnicki Jan 16 '20 at 21:52
  • (That said, my gut instinct was originally to say that 'the intersection of any two faces is a face' is a sufficient condition, but I feel like there could be a counterexample based on a dual polytope to one of your examples.) – Steven Stadnicki Jan 16 '20 at 21:53
  • After taking a closer look at the fundamentals of convex polytopes (e.g. Farkas' lemma: The conical hull of a finite set of vectors is equal to the intersection of all half-spaces containing it), I think you were essentially right. The intersection of any two faces is a face; that gives a greatest lower bound. Duality gives a least upper bound. – mr_e_man May 26 '22 at 22:41
1

  • Here is a necessary (but not sufficient) condition, [1, $\S$2A, pg. 29 ]:

    If an $n$-polytope $\mathcal{P}$ is a lattice, then its edge-graph is $n$-connected, meaning that, for every pair of vertices of $\mathcal{P}$, there exist $n$ pairwise disjoint edge-paths having these vertices as end points.

    It is evidently not sufficient since both the digon and the hemicube both satisfy this condition.

  • As well, it is stated (without proof) that atomisticity -- or, as it seems to be more commonly known, vertex-describability -- is necessary in [5, pg. 291]. This is the property of each face being defined by a unique set of vertices.

  • A proof of the sufficiency of convexity can be found in [2, Thm. 2.7].

  • Another set of polytopes for which their face posets are lattices are the universal regular polytopes [1, $\S$ 3D] which are a superset of regular convex polytopes. While they are stated to be lattices in [1, Thm. 3D7], no proof is provided there; instead, the reader is referred to [3] and [4].

  1. McMullen, Peter, and Egon Schulte. Abstract regular polytopes. Vol. 92. Cambridge University Press, 2002.

  2. Ziegler, Günter M.. Lectures on Polytopes. United States, Springer New York, 1995.

  3. Tits, Jacques. "Groupes et géométries de Coxeter, preprint Inst." Hautes Études Sci (1961).

  4. Tits, Jacques. "Géométries polyédriques et groupes simples." Atti della II Riunione del Groupement des Mathématiciens d'Expression Latine. Edizioni Cremonese, 1963.

  5. Connelly, Robert, Asia Ivić Weiss, and Walter Whiteley, eds. Rigidity and Symmetry. Vol. 70. Springer, 2014.

mhum
  • 2,447
  • Apparently "pairwise disjoint edge-paths" means only that the edges don't intersect; the intermediate vertices do intersect on the hemicube. And I don't think atomisticity is trivial (by either definition); it can't be proven from graded lattice properties alone, as shown by a linear lattice such as $0<1<2<3$ (which has a single "vertex" $1$). And to clarify "being defined by a unique set of vertices", I would say it means, for two faces $A,B$, if the set of all vertices $V_i\leq A$ equals the set of all vertices $V_i\leq B$, then $A=B$. – mr_e_man Jan 17 '20 at 00:00
  • That linear lattice satisfies all properties of an abstract polytope except the "diamond property". I don't see a "trivial" way to apply this property in proving atomisticity; we have two arbitrary faces (not necessarily 2-faces), and vertices below them, and suprema of these vertices, but nothing with grades differing by $2$. – mr_e_man Jan 17 '20 at 00:13
  • Oh, I thought the necessity of vertex-describability was trivial because if you have two distinct faces, (say, $F_1$ and $F_2$) containing the same set of vertices (say, $S$), then $F_1$ and $F_2$ seemed to be two distinct least upper bounds for the set $S$. Perhaps this is not the case? – mhum Jan 17 '20 at 00:27
  • In that linear lattice, $2$ and $3$ are both "defined" by the vertex $1$. But the supremum of $1$ is $1$. – mr_e_man Jan 17 '20 at 00:28
  • Right, but as you've observed, that's not a polytope so it doesn't exactly apply. Let me see if I can find a more concrete proof. FWIW, it's stated without proof in this arXiv paper. – mhum Jan 17 '20 at 00:32
  • Hmm. Upon further reflection, it seems that the necessity of vertex-describability is perhaps not quite as trivial as I thought. Might need to draw up a proof of my own. – mhum Jan 17 '20 at 23:51
  • You're getting the bounty, as you've certainly given this question "more attention" and tried to improve your answer. But I'm not satisfied. I don't have access to your references (though someone else may find them useful); I would appreciate it if you'd write out the proofs here (or at least sketches) for some of these properties. – mr_e_man Jan 20 '20 at 19:40
  • 1
    It would be ideal to provide some proof sketches here. But I've tried to track down some of the source references (at least for the Tits papers) and boy howdy are they non-trivial. I mean, the first gap to bridge is that the original proofs take place in a fairly different context so there's a pretty big gap in language & terms. I'm unfortunately not proficient enough to cover this ground. – mhum Jan 20 '20 at 21:24
0

I'll try to show that any (finite) polytope that is also a lattice is atomistic.

In any polytope, for any face $A$, there is a well-defined set of all vertices $V_i\leq A$. The definition of a lattice gives the existence of $S=\sup\{V_i\}$, and clearly $A$ is an upper bound of $\{V_i\}$, so $A\geq S\geq V_i$. Now $S$ has its own set of vertices $W_i\leq S$. This contains $\{V_i\}$ since $V_i\leq S$; but it's also contained in $\{V_i\}$ since $W_i\leq S\leq A$. Therefore, $A$ and $S$ have the same vertex set $\{V_i\}$. We need to show that $A=S$.

The section $A/F_{-1}$ is itself a polytope, and also a lattice: if $X\leq A$ and $Y\leq A$, then $\sup\{X,Y\}\leq A$ and $\inf\{X,Y\}\leq A$. So, without loss of generality, $A=F_n$ is the greatest face, and $\{V_i\}$ is the set of all vertices in the polytope.

The result ($A=S$) is clearly true when the number of vertices is $0$ or $1$.

For induction, suppose the result is true for smaller sets of vertices. Considering $A\geq S$, let's assume $A>S$ for contradiction. Then by the dyadic/diamond property there is some $T\neq S$ but with the same rank, so $T\not\leq S$ and $T\not\geq S$.

If the vertex set of $T$ is all of the vertices ($T\geq V_i$ for all $i$), then $T\geq\sup\{V_i\}=S$, a contradiction.

If the vertex set of $T$ is smaller ($T\not\geq V_i$ for some $i$), then by induction $T$ is the supremum of this set. But since $S\geq V_i$ for all $i$, $S$ is an upper bound for this smaller set, so $S\geq T$, a contradiction. This concludes the proof.

mr_e_man
  • 5,364