Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e. balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer (which I exploded vertically for visualization):
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Shermer.119b.jpg
Essentially all our irreducible examples are based on Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability:

Can every (embedded) object constructed by gluing unit cubes face-to-face, regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11 May 2011 (original posting on 2 January 2011). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e. balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer (which I exploded vertically for visualization):

Essentially all our irreducible examples are based on Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability:

Can every (embedded) object constructed by gluing unit cubes face-to-face, regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11 May 2011 (original posting on 2 January 2011). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e., balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer  (which I exploded vertically for visualization):
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Shermer.119b.jpg
Essentially all our irreducible examples are based on  Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's  Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability.:

Can every (embedded) object constructed by gluing unit cubes face-to-face,  regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass  Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11May11 (original posting 2Jan11). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e. balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer  (which I exploded vertically for visualization):
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Shermer.119b.jpg
Essentially all our irreducible examples are based on  Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's  Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability:

Can every (embedded) object constructed by gluing unit cubes face-to-face,  regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass  Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11 May 2011 (original posting on 2 January 2011). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e., balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer (which I exploded vertically for visualization):
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Shermer.119b.jpg
Essentially all our irreducible examples are based on Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability.:

Can every (embedded) object constructed by gluing unit cubes face-to-face, regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11May11 (original posting 2Jan11). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."

Janos Pach asked a deep question 23 years ago (1988) that remains unsolved today:

Can every animal—a topological ball in $\mathbb{R^3}$ composed of unit cubes glued face-to-face—be reduced to a single unit cube by adding and deleting cubes, while always maintaining the animal (ball) property?

("Animal" was an apparently original coinage of Janos's.) I and my students quickly found irreducible animals, i.e., balls of unit cubes from which no cube can be removed without destroying the topological-ball property. Here is one of 119 cubes due to Tom Shermer (which I exploded vertically for visualization):
alt text http://cs.smith.edu/%7Eorourke/MathOverflow/Shermer.119b.jpg
Essentially all our irreducible examples are based on Bing's House with Two Rooms (unbeknownst to us at the time). So if Pach's question has a positive answer, it requires adding cubes as well as deleting. This history is recounted in Günter Ziegler's Lectures on Polytopes, Springer, 1995, p.276. His non-shellability Theorem 8.15 (p.243) is based on these irreducible animals.

So, I finally come to my question, which is essentially a question of shellability.:

Can every (embedded) object constructed by gluing unit cubes face-to-face, regardless of genus, be reduced to a single unit cube by adding and deleting cubes, while always maintaining that the surface is a 2-manifold?

This is exactly Pach's question, but with the ball-requirement removed. All the irreducible animals I know rely on violating the topological-ball requirement for their irreducibility; so it is (remotely) possible that reduction alone suffices(!). I am tempted to introduce a new genera to encompass Plantae & Animalia; but I resist.

Any pointers that may lead me to information on the generalization of Pach's question would be greatly appreciated. Thanks!

Addendum, 11May11 (original posting 2Jan11). The problem is now solved (positively): Every animal can be reduced by adding and deleting cubes. The proof is contained in two papers, the second of which appeared as a tech report in May 2010: "A solution to the animal problem," by Akira Nakamura. Here is the PDF. The first paper, an earlier 2006 tech report, is called simply, "B-Problem," by Akira Nakamura, Kenichi Morita, and Katsunobu Imai. Here is its PDF. I would summarize but I do not yet understand the papers, which are presented in terms of "digital topology."