# Triangulations coming from a poset. Or: What conditions are necessary and sufficient for a finite simplicial complex to be the order complex of a poset?

Every partially ordered set gives a triangulation of (the geometric realisation of) its order complex. (The n-simplices of the order complex are the chains $x_0\leq x_1\leq\cdots\leq x_n$.) However, there are triangulations of topological spaces that do not arise this way.

Is there a name for triangulations having this special property of "coming from a poset?"

EDIT: Apparently, the following formulation of my question is cleaner: what conditions are necessary and sufficient for a finite simplicial complex to be the order complex of a poset?

-
Doesn't every triangulation come from a poset? Let $V$ be the set of vertices of the triangulation, $S=$ set of subsets of $V$, a poset via inclusion, and $T\subset S$ the sub-poset corresponding to the triangulation. What am I missing? –  Paul Mar 21 '10 at 19:24
If on the other hand you're interested in when a simplicial complex is a triangulation of a manifold, that has a very nice (and algorithmically impossible to implement in general) solution. –  Ryan Budney Mar 21 '10 at 22:26
@Paul: The triangulation coming from the poset you construct is the baryzentric subdivision of the triangulation we started with. –  Rasmus Bentmann Mar 21 '10 at 23:15
@Ryan Budney: I have changed manifold to topological space, sorry. –  Rasmus Bentmann Mar 21 '10 at 23:22

Here are necessary and sufficient conditions for an abstract, finite simplicial complex $\mathcal{S}$ to be the order complex of some partially ordered set.

(i) $\mathcal{S}$ has no missing faces of cardinality $\geq 3$; and

(ii) The graph given by the edges (=$1$-dimensional simplices) of $\mathcal{S}$ is a comparability.

[Definitions. (a) A missing face of $\mathcal{S}$ is a subset $M$ of its vertices (=$0$-dimensional simplices) such that $M \not \in \mathcal{S}$, but all proper subsets $P\subseteq M$ satisfy $P\in \mathcal{S}$. (b) A graph (=undirected graph with no loops nor multiple edges) is a comparability if its edges can be transitively oriented, meaning that whenever edges $\{p, r_1\}, \{r_1, r_2\},\ldots, \{r_{u−1}, r_u\}, \{r_u, q\}$ are oriented as $(p, r_1), (r_1, r_2),\ldots, (r_{u−1}, r_u), (r_u, q)$, then there exists an edge $\{p, q\}$ oriented as $(p, q)$.]

This characterisation appears with a sketch of proof $-$ which is not hard, anyway $-$ in

M. M. Bayer, Barycentric subdivisions. Pacific J. Math. 135 (1988), no. 1, pp. 1-16.

As Bayer points out, the result was first observed in

R. Stanley, Balanced Cohen-Macaulay complexes, Trans. Amer. Math. Soc, 249 (1979), pp. 139-157.

@Rasmus and @Gwyn: The characterisation might perhaps disappoint you if you were expecting something more topological. However, it's easy to prove that no topological characterisation of order complexes is possible, and therefore a combinatorial condition such as the one on comparabilities must be used. For this, first check that the barycentric subdivision of any simplicial complex indeed is an order complex. Next observe that barycentric subdivision of a simplicial complex does not change the homeomorphism type of the underlying polyhedron of the complex. Finally, conclude that for any topological space $T$ that is homeomorphic to a compact polyhedron, there is an order complex whose underlying polyhedron is homeomorphic to $T$.

I hope this helps.

-
"No missing faces" is the same as flag complex. –  Victor Protsak Aug 24 '10 at 0:19
@Vincenzo Marra: Wow, that's nice. Thank you for this information. –  Rasmus Bentmann Aug 24 '10 at 15:25

To rephrase your question, what conditions are necessary and sufficient for a simplicial complex to be an order complex?

There are also a few easy necessary conditions. For one, any simplicial complex is the Stanley-Reisner complex of a square-free monomial ideal (label each vertex with a variable, and the minimal non-faces in the simplicial complex are exactly the monomial generators of the ideal.) For all order complexes, their Stanley-Reisner ideal is an edge ideal (i.e. a square free monomial ideal generated in degree 2, called an "edge ideal" because it can be thought of as corresponding to a graph G with an edge for each generator.) This is immediate, because a minimal "non-face" in the order complex is a pair of incomparable elements, so all generators must be of degree 2. This does quickly cut down on the types of simplicial complexes to consider.

Unfortunately, having a 2-generated SR-ideal is also not sufficient. There are numerous subgraphs of a graph which will prevent the Stanley-Reisner complex of its edge ideal from being an order complex. For example, if the graph has an induced cycle of length longer than 7, the complex can't arise as an order complex.

I was working a few months ago on trying to classify the structures in graphs which would prohibit their edge ideals from having SR-complexes which were order complexes, but found the other forbidden structures weren't very easy to characterize. I'd love to see some more answers to this question as well!

-

I don't know a name for this concept, but I know names for two related concepts.

A simplicial complex $\Delta$ is called flag or clique if, whenever $v_1$, $v_2$, ..., $v_r$ is a collection of vertices such that $(v_i, v_j)$ is an edge of $\Delta$ for all $1 \leq i < j \leq r$, then $(v_1, v_2, \ldots, v_r)$ is a face of $\Delta$.

A simplicial complex $\Delta$ is called balanced if $\Delta$ is pure of dimension $d$ and it is possible to color the vertices of $\Delta$ with $d+1$ colors so that no face contains two vertices of the same color.

If $\Delta$ is the order complex of a poset then it is flag; if $\Delta$ is the order complex of a graded poset then it is balanced.

-
I don't think this works. Consider the "bowtie": two triangles $(a,b,c)$ and $(c,d,e)$ glued along a single vertex. This can be three colored; say $a$ and $d$ have color $0$; $c$ has color $1$; and $b$ and $e$ have color $2$. If we order the colors in the obvious numerical way, your proposed poset is not transitive. Admittedly, if we order $1 < 0 < 2$, then your construction works, but I think there is probably an example where no ordering works. –  David Speyer Mar 24 '10 at 20:26
I see. A example where no coloring works should be given by the same idea. Just glue a triangle to each vertex of (a,b,c). –  HenrikRüping Mar 24 '10 at 21:35
My previous example was a reply to a claimed proof (now deleted) that flag + balanced implies order complex. –  David Speyer Mar 24 '10 at 21:47
This is maybe too tautological a characterisation: The complex is flag and there is a total order on the vertices such that if $x<y<z$ and there is one edge between $x$ and $y$ and one between $y$ and $z$, then there is an edge between $x$ and $z$. (In one direction it uses the fact that a partial order can be extended to a total one.) –  Torsten Ekedahl Apr 2 '10 at 9:53