Suppose we want a house with infinitely many rooms. (Because real estate as a nonrival good is a pleasant fantasy.)

One obvious way to do this would be to lay out the rooms on a Cartesian grid, so that each room (x,y) has doors leading to (x-1,y), (x+1,y), (x,y-1), (x,y+1). This has the disadvantage of requiring relatively large travel times between distant rooms; if you have n rooms, then even if they’re clustered optimally close together, you still have to pass through O(sqrt(n)) rooms to get from one side of the cluster to the other.

If we abandon Cartesian geometry, we can reduce this to this to O(log(n)) by arranging the rooms on a tree graph. However, this has the disadvantage that blocking off any one room cuts us off from all the rooms below it on the tree. On the grid, it’s possible to isolate a finite set of rooms by blocking a ring of rooms around them, but if you want to divide the grid into two both-infinite sets of rooms, you need to block off an infinite number of rooms between them.

Can we do better?

Consider the following infinite graph:

Each vertex is labeled with a sequence of binary digits, infinite on the left end and terminating on the right end. We can interpret these sequences as infinitely large numbers, and add and subtract finite integers. (Specify that sequences that would correspond to finite numbers – that have all zeros to the left of some point – are not found on our graph.)

Each vertex n has exactly four edges, to the following vertices:

  • n ± 1
  • n ± 2k, where k is the largest power-of-two factor of n

For example, a vertex labeled …011000 would have connections to:

  • …011001
  • …010111
  • …101000
  • …001000

where the ellipsis stands for the same infinite sequence in each case.

I suspect, but don’t know how to prove, that:

  • the distance between two rooms a and b is O(log(|a-b|)), and
  • deleting any finite set of rooms cuts off at most finitely many rooms from the whole

…which was the original goal.

Does this graph, or something similar to it, have a name? Can anyone prove that it meets the criteria? Are there any other graph structures that would make nice places to live?

(On the criterion of inseparability: note that for any two points, there are infinitely many edges such that one endpoint is less than both points and the other endpoint is greater than both points. That probably isn’t quite a proof, but I think it gestures in the direction of one.)