# How many set partitions on a big cube’s boundary arise from cubomino decompositions of the solid cube?

Introduction. This is a counting question about configurations that can appear on the outside of assembled Soma cube-like puzzles. More specifically, it’s about the ways in which the pieces of an assembled puzzle can partition the exterior of the cube.

Construction. Suppose you have at your disposal an unlimited supply of every possible cubomino shape, that is, shapes that can be made from one or more unit cubes by gluing faces to faces (glued faces must coincide). Also suppose that you have both red and blue versions of each shape. Now consider complete $s\times s \times s$ oriented cubic “assemblies” of such pieces, with one constraint: like-colored puzzle pieces may not occur face-to-face. (Pieces of the same color may touch at corners or edges.) An assembly need not be achievable with physical pieces. A valid assembly could contain interlocked torus-like pieces, for example.

Set partitions, especially on the boundary. Ignoring color, the individual pieces of a valid assembly partition the cube's $s^3$ unit cube locations. One characteristic of a set partition arising in this way is that its partition elements are each face-connected subsets of the cube. The color rule imposes additional restrictions; for example, no valid assembly yields a partition that contains three mutually adjacent parts.

If we focus our attention on the assembled cube's boundary, we get a set partition of the $s^3-(s-2)^3$ boundary positions. Within the boundary, partition parts need no longer be face-connected subsets, but whether an arbitrary set partition that contains disconnected parts does or not arise from a puzzle assembly depends on whether the disconnected parts can all be “connected up” through the cube’s interior. (Example below.)

Question. Call a partition of the cube’s boundary lattice-realizable if it occurs in some valid puzzle assembly. Let $c(s)$ be the number of distinct lattice-realizable set partitions of the boundary of an $s\times s\times s$ cube. How does $c(s)$ grow as $s$ grows? In particular, is $c(s) \le M^{(s^2)}$ for some constant $M$?

Context. This construction works without modification in dimensions other than 3.

Let $c(d,s)$ be the number of distinct lattice-realizable set partitions of the boundary of the generalized cube of volume $s^d$. When $d=1$, the cube is an interval of length $s$, the boundary has cardinality 1 or 2 (the endpoint(s)), and there are either 1 or 2 set partitions of the boundary, none of which fail to be lattice-realizable. Trivially, $c(1,s) \le M^{(s^0)}$ for some constant $M$ (any $M\ge 2$ works).

When $d=2$, there is a convenient upper bound for $c(2,s)$: the number of non-crossing partitions on $4s-4$ elements, which is known to be the Catalan number $C_{4s-4}$. Known asymptotics of the Catalan numbers give $c(2,s) \le C_{4s-4} \le M^{(s^1)}$ for constant $M$ ($M=4^4$ works, for example). In contrast, the number of (all, non-crossing or not) set partitions on the $4s-4$ boundary elements is the Bell number $B_{4s-4}$, which is not bounded by $M^{(s^1)}$ for any constant $M$.

For $d=1$ and $d=2$, then, $c(d,s)$ grows no faster than $M^{(s^{d-1})}$. What about $d>2$? Unfortunately, there's no analog for non-crossing partitions when $d>2$. For $d=3$, every set partition of points on the surface of a cube (or sphere) is non-crossing in the sense of being realizable via disjoint connected subsets of the interior of the cube.

Related topics. The problem I'm looking into comes from symbolic dynamics, but it looks like there might be useful results (though I've yet to find them) in various areas of study. Knot theorists have looked at the notion of lattice knots (and other sorts of thickened knots); this gets at one way in which discretization reduces the potential complexity that can appear in a cube. Questions about 3-D or multilayer integrated circuit design concern configurations on a boundary that can arise from internal lattice-like connections, but that research focuses on finding efficient design algorithms, not on counting. Spin models in statistical mechanics, quantum entanglement, holography, and computational linguistics are potentially related topics.

Example. Without loss of generality, position a $3\times3\times3$ cube with opposite corners at $(1,1,1)$ and $(s,s,s)$, and consider the following three-element partition of its 26 boundary positions: two cardinality-two parts: $\{(2,2,1),(2,2,3)\}$ and $\{(1,2,2),(3,2,2)\}$ and one cardinality-24 part (the rest of the boundary). The single interior position of this cube, $(2,2,2)$ can only “connect up” one of the two small partition elements (each of which are disconnected when only the boundary is considered), so no valid puzzle assembly will yield this partition.

-