10
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ Shouldn't the answer to (1) be 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. $\endgroup$
    – Ryan Budney
    Commented May 31, 2013 at 12:52
  • 4
    $\begingroup$ In case this helps, see Thm 2.4 in google.es/… $\endgroup$
    – Fernando Muro
    Commented May 31, 2013 at 13:01
  • $\begingroup$ 1)No. For complexes regular polydrons in the division, like tetrahedrons, which can have many combinatorial shapes. 2)Yes. Probably the algorithm which is used to traverse(DFS) the possible pairs inbetween two sets of groups can be adapted... 3)I think this problem can be solved by reducing the problem into an automorphism group traverse problem, using the regular algorithm for exhausting the orbits in a given abelian group. $\endgroup$
    – Henry.L
    Commented May 31, 2013 at 13:54
  • $\begingroup$ Fernando: thanks for this reference! Ryan: see Fernando's link, it contradicts what you appear to be saying. Henr: doesn't an affirmative answer to 3 force an affirmative answer to 1? $\endgroup$
    – Vidit Nanda
    Commented May 31, 2013 at 14:55
  • 2
    $\begingroup$ Here is another relevant article: "The insufficiency of barycentric subdivision" by Ross L. Finney (projecteuclid.org/euclid.mmj/1028999363). It claims that two locally finite simplicial complexes are isomorphic if their barycentric subdivisions are isomorphic. It further claims that any isomorphism between the barycentric subdivisions of $K$ and $L$ is induced by an isomorphism $K\to L$, as long as $K$ is connected and is not a 1-manifold, or a simplex, or the boundary of a simplex. Perhaps the analysis leading to this latter result may help with problem 3. $\endgroup$
    – Ricardo Andrade
    Commented Jun 2, 2013 at 5:28

1 Answer 1

Reset to default
3
$\begingroup$

[As requested by Vidit Nanda, I am reposting a slightly edited version of my comment above as an answer. Nevertheless, I hope someone will eventually give a satisfactory answer to this question.]

The following article is relevant for this question: "The insufficiency of barycentric subdivision" by Ross L. Finney (published in Michigan Mathematical Journal, Volume 12, Issue 3 (1965), pages 263-272).

Let $K$ and $L$ be locally finite simplicial complexes. The cited article claims that $K$ and $L$ are isomorphic if their barycentric subdivisions are isomorphic. It also states that any isomorphism between the barycentric subdivisions of $K$ and $L$ is induced by an isomorphism $K\to L$, as long as $K$ is connected and verifies the following two conditions:

  • $K$ is not isomorphic to a simplex or to the boundary of a simplex, and
  • the geometric realization of $K$ is not a $1$-manifold without boundary (i.e. not homeomorphic to $S^1$ or to $\mathbb{R}$).

Perhaps the analysis leading to this latter result may help with problem 3 in the question.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks a ton, Ricardo. I have accepted your answer for now so that my question doesn't keep getting popped to the front page. I hope you will understand if I undo this acceptance in the event of a more precise answer from you or someone else. $\endgroup$
    – Vidit Nanda
    Commented Jun 14, 2013 at 14:05
  • $\begingroup$ @Vidit: You are welcome. If someone actually gives a satisfactory answer to your question, you should absolutely accept that instead. I certainly hope a better answer does eventually come along. I am also curious about it! $\endgroup$
    – Ricardo Andrade
    Commented Jun 14, 2013 at 21:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .