Consider a $D$-dimensional hypercubic lattice, i.e. a graph $H$ embedded in ${\mathbb R}^D$ where the vertices have integer coordinates $ (x_1,...,x_D) \in {\mathbb Z}^D$ and edges are between all pairs $ \{ (x_1,...,x_i,...,x_D), (x_1,...,x_i+1,...,x_D)\}$.

From this graph $H$, build a second graph $S$ the following way.

  • consider the family of vertices of $H$, embedded in the $D-1$-dimensional hyperplanes $S_t$ defined by $\sum_{i=1}^D x_i = t$ with $t \in {\mathbb Z}$

  • consider that there is an edge between two vertices in $S_t$ if, in $H$, those two vertices have a common neighbour in $S_{t+1}$ or/and $S_{t-1}$.

Obviously $S = \cup_t S_t$ is a disconnected graph with each $S_t$ being a $D-1$ dimensional layer.

I remarked that for $D = 2, 3$, and apparently also for $D=4$, the $S_t$ are actually $D-1$-hypersphere packing contact graphs.

My question is, for what values of $D$ does this hold?

  • $\begingroup$ In your definition of adjacency, do you mean $x_i+1$? $\endgroup$
    – Casteels
    May 20, 2014 at 8:23
  • $\begingroup$ Right - I've just done the editing. $\endgroup$
    – Mathias
    May 20, 2014 at 17:51
  • $\begingroup$ If I'm mentally translating right, these entities are usually known as the $A_n$ lattices and you might be able to find useful information on them under that name; in particular, en.wikipedia.org/wiki/Root_system#An is a decent starting point. Your intuition is good; they're related to sphere packing, although for $n\gt 3$ they're not the most efficient packings. $\endgroup$ May 20, 2014 at 18:20
  • $\begingroup$ Thanks for this answer. I'll have to dig into root systems then. Yet I would have expected this to hold for a bit more dimensions since up to $D=8$, the compact hypersphere packs are laminated. Or maybe I have to go into the details to see how my $D$ and your $n$ map. $\endgroup$
    – Mathias
    May 21, 2014 at 4:20
  • $\begingroup$ @Mathias I may be slightly off my mark; this isn't my area of expertise, but I believe what you've described is the $A_n$ lattice as opposed to $D_n$ (my $n$ is your $D-1$); if I'm right, then through up to three dimensions of packing - or 4 dimensions of hypercube - you're correct in your assumption, but then I believe it will break down one dimension higher and no longer be the densest packing. If you want more reading on this, I highly, highly recommend Conway and Sloane's Sphere Packings, Lattices and Groups, which is absolutely the canonical reference. $\endgroup$ May 21, 2014 at 15:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.