With apologies to fellow algebraic topologists, I confess that I have no idea how to answer this innocent-looking question:

(

1) Let's say we know that a finite simplicial complex $S$ is the barycentric subdivision of some other simplicial complex $K$. Can we find $K$ (up to simplicial isomorphism) from knowledge of $S$ alone?

Nor can I find answers to the related question:

(

2) Given a simplicial complex $S$, can we decide if an "inverse-subdivision" $K$ exists? That is, can we decide if $\text{Sd}K = S$ has a solution $K$?

Ideally, one would like an affirmative answer to:

(

3) Are there efficient algorithms which decide (2) and solve (1), given $S$?

Efficient in this case would mean polynomial time in the number of simplices in $S$ (this might be super-exponential in the number of simplices in $K$, if $K$ exists).

**Background:**

Let $K$ be an abstract simplicial complex. Its *barycentric subdivision* $\text{Sd}K$ is defined to be the simplicial complex whose vertices are the simplices $\sigma \in K$, and each $d$-simplex is a sequence $\sigma_0 < \sigma_1 < \cdots < \sigma_d$ of strict face relations in $K$.

It is well-known that the geometric realizations of $\text{Sd}K$ and $K$ are homeomorphic, and barycentric subdivisions are used with remarkable frequency in basic algebraic topology (e.g., in proving the equivalence of simplicial and singular homology, or that simplicial homology satisfies the excision axiom, see Hatcher Ch. 2.1).

**Update:**

From the comments, there doesn't even appear to be a consensus on whether non-isomorphic simplicial complexes can have isomorphic barycentric subdivisions. Maybe someone wants to take a stab at this foundational question as well.

no? I would think there would be many non-isomorphic complexes that share a common barycentric subdivision. For (2), I think the answer is yes. A barycentric subdivision has rather strict combinatorial properties. I can't imagine an efficient algorithm -- more of an exhaustive search for very particular subcomplexes. – Ryan Budney May 31 '13 at 12:52