# Restricted Cube Packing

I want to pack n cubes in 3-space under the following 3 restrictions:
1) At each vertex only 2 cubes may touch
2) No two cubes may share an edge
3) No two cubes share any subface

2,3 just mean that they have to touch on a vertex

I am interested in minimizing the number of corners of the cubes which don't touch any other cubes.

Does anyone have an idea for a lowerbound on the number of vertices which only belong to one cube?
In other words, regardless of the arrangement, how many vertices will only belong to one cube?

The only lowerbound I have is the trivial 8.

Thank you

-

While this may be a bit tricky to prove, intuition strongly suggests that the best packing will have a 3d checkerboard arrangement of cubes; i.e., cubes only go into cells $(i,j,k)$ with $i+j+k$ even (EDIT: as @mjqxxxx notes below, this should actually be those cells for which both $i+j$ and $i+k$ are even, which changes the resulting density of the tiling but not the asymptotics), and dualization then turns this into a discrete version of an isoperimetric problem, where you're trying to minimize the 'surface area' of your arrangement for a given volume (since the only vertices in this arrangement belonging to only one cube are those that are on the surface cubes). Precise bounds on the constant will be hard, but the isoperimetric formulation suggests that an arrangement of $k^3$ cubes will have a surface area of at least $\Omega(k^2)$, or in other words, that your lower bound will be of the form $\Omega(n^{2/3})$.
I'm not sure you actually mean the cells with $i+j+k$ even (density $1/2$ in each constant-$k$ layer). This would seem to have cubes at, say, $(0,0,0)$ and $(1,1,0)$, which share an edge (assuming they're axis-aligned). Maybe you mean the cells with $i+k$ and $j+k$ both even (density $1/4$ in each layer)? (The $\Omega(n^{2/3})$ scaling is unchanged.) – mjqxxxx Jan 10 '12 at 17:23
Ahh, yes - sorry, I was looking at the 2d case in my head (where the cells with $i+j$ even work correctly) and missed that that doesn't quite translate up to 3d how I thought it does. I'll correct the answer. – Steven Stadnicki Jan 10 '12 at 17:32
@Steven Stadnicki Thank your for your answer. For me it is not straight forward to show the $\Omega(n^(2/3))$ lowerbound since there can be cubes on the surface which are connected to 8 other cubes. So I would have to show that in a neighborhood of contant size c, each cube on the surface has a $\leq c$ neighbor which has a free vertex. – alex Jan 11 '12 at 17:05
alex: I'm not quite sure what you mean; almost by definition, cubes on the 'surface' can't be connected to 8 other cubes. I agree that the $n^{2/3}$ lower bound isn't trivial to prove, but a reformulation should at least bring it within reach. (For instance, it's certainly possible to show that no packing is more dense than the checkerboard-style packing given here.) – Steven Stadnicki Jan 12 '12 at 8:24