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? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T03:22:56Z http://mathoverflow.net/feeds/question/18938 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/18938/triangulations-coming-from-a-poset-or-what-conditions-are-necessary-and-suffici 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? Rasmus 2010-03-21T16:57:46Z 2010-08-24T10:50:23Z <p>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.</p> <p>Is there a name for triangulations having this special property of "coming from a poset?"</p> <p>EDIT: Apparently, the following formulation of my question is cleaner: <em>what conditions are necessary and sufficient for a finite simplicial complex to be the order complex of a poset?</em></p> http://mathoverflow.net/questions/18938/triangulations-coming-from-a-poset-or-what-conditions-are-necessary-and-suffici/19228#19228 Answer by David Speyer for 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? David Speyer 2010-03-24T19:08:04Z 2010-03-24T19:08:04Z <p>I don't know a name for this concept, but I know names for two related concepts.</p> <p>A simplicial complex $\Delta$ is called <em>flag</em> or <em>clique</em> 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 &lt; j \leq r$, then $(v_1, v_2, \ldots, v_r)$ is a face of $\Delta$.</p> <p>A simplicial complex $\Delta$ is called <em>balanced</em> 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. </p> <p>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. </p> http://mathoverflow.net/questions/18938/triangulations-coming-from-a-poset-or-what-conditions-are-necessary-and-suffici/20129#20129 Answer by Gwyn Whieldon for 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? Gwyn Whieldon 2010-04-02T02:09:34Z 2010-04-02T03:18:41Z <p>To rephrase your question, what conditions are necessary and sufficient for a simplicial complex to be an order complex?</p> <p>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.</p> <p>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.</p> <p>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!</p> http://mathoverflow.net/questions/18938/triangulations-coming-from-a-poset-or-what-conditions-are-necessary-and-suffici/36505#36505 Answer by Vincenzo Marra for 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? Vincenzo Marra 2010-08-23T23:52:33Z 2010-08-23T23:52:33Z <p>Here are necessary and sufficient conditions for an abstract, finite simplicial complex $\mathcal{S}$ to be the order complex of some partially ordered set.</p> <p>(i) $\mathcal{S}$ has no missing faces of cardinality $\geq 3$; and</p> <p>(ii) The graph given by the edges (=$1$-dimensional simplices) of $\mathcal{S}$ is a comparability.</p> <p>[Definitions. (a) A <em>missing face</em> 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 <em>comparability</em> if its edges can be transitively oriented, meaning that whenever edges <code>$\{p, r_1\}, \{r_1, r_2\},\ldots, \{r_{u−1}, r_u\}, \{r_u, q\}$</code> are oriented as $(p, r_1), (r_1, r_2),\ldots, (r_{u−1}, r_u), (r_u, q)$, then there exists an edge <code>$\{p, q\}$</code> oriented as $(p, q)$.]</p> <p>This characterisation appears with a sketch of proof $-$ which is not hard, anyway $-$ in</p> <blockquote> <p>M. M. Bayer, <em>Barycentric subdivisions</em>. Pacific J. Math. 135 (1988), no. 1, pp. 1-16. </p> </blockquote> <p>As Bayer points out, the result was first observed in </p> <blockquote> <p>R. Stanley, <em>Balanced Cohen-Macaulay complexes</em>, Trans. Amer. Math. Soc, 249 (1979), pp. 139-157.</p> </blockquote> <p>@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 <em>must</em> be used. For this, first check that the barycentric subdivision of <em>any</em> 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$. </p> <p>I hope this helps.</p>