1
$\begingroup$

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

1 Answers 1

2

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})$.

  • 0
    @Steven Stadnicki Thank you. I think my problem is that its not obvious to me how to define surface here. But I would be very interested in showing some $\Omega(n^{2/3})$ bound and I agree with you that the isoperimetric argument will probably be fruitfull. Btw: One can get a better packing in terms of degree one vertices if one arranges the cubes such that they "fill" a big octahedron.2012-01-12