3
$\begingroup$

Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:

  1. Each row in the cube (in any of the three directions) has exactly 2 or 0 points.

  2. If two points are in the same row (any of three), connect them with an edge. The subset must be connected by these edges.

It is easy to build such a set which is $\Omega(n)$, for instance a staircase, or stacking squares. Is it the case that these structures are also $O(n)$? Or is there an $\Omega(n^2)$ bound?

Building such a set would require adding a linear number of points for each added dimension, which is hard due to the first restriction.

This problem may also be reformatted graph-theoretically. We may express points in the cube as 3-edges in a 3-uniform tripartite hypergraph. In this case our restraints become that each set of 2 points contained in a 3-edge is contained in exactly two 3-edges, and the 3-edges are connected.

$\endgroup$
  • 1
    $\begingroup$ The point set $\{(x,y,z) : z = x + y\} \cup \{(x,y,z) : z = x + y + 1\}$ "almost" works to give a $n^2$ lower bound, except that a few rows contain only one point, i think. $\endgroup$ – daniello Jun 22 '17 at 20:09
  • $\begingroup$ I guess if addition is done mod n then the above construction works $\endgroup$ – daniello Jun 22 '17 at 20:12
  • $\begingroup$ This certainly gives that each row (x,y,-) has degree 2. It's not clear to me that (x,-,z) or (-,y,z) do on the other hand. I'm a little confused by your second comment as well, how could a row have a single point but be 0 or 2 mod n? I think I misunderstand your mod n comment $\endgroup$ – Max Hopkins Jun 22 '17 at 20:22
  • $\begingroup$ Wrote it now as an answer, hopefully this is more clear $\endgroup$ – daniello Jun 22 '17 at 20:31
3
$\begingroup$

These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paper

The complexity of bendless three-dimensional orthogonal graph drawing. D. Eppstein. J. Graph Algorithms and Applications 17 (1): 35–55, 2013. http://dx.doi.org/10.7155/jgaa.00283

I don't think I included the quadratic example suggested in daniello's answer in this paper, but you can find it in one of my blog posts from ten years ago, https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html (see the ETA at the bottom).

Incidentally, the same construction (points with coordinate sum 0 or 1) in the 3d integer lattice, without the mod $n$ part, produces a lattice embedding of the hexagonal tiling of the plane. Doing the same thing in 4d, similarly, produces a lattice embedding of the 3d diamond lattice. See another of my papers:

Isometric diamond subgraphs. D. Eppstein. 16th Int. Symp. Graph Drawing, LNCS 5417, 2009, pp. 384–389. https://arxiv.org/abs/0807.2218

$\endgroup$
  • $\begingroup$ Fantastic to hear this has been studied--at a glance this is exactly what I'm looking for. I will read through the paper. I am particularly interested in a lower bound on labelings $\gamma: [n] \times [n] \times [n] \to F_2^d$ (or in more generality n,m,k to any finite abelian group) such that for a subset of this sort $C$: $\sum\limits_{e \in C} \gamma(e) \neq 0$. Do you know if this has been looked at before as well? $\endgroup$ – Max Hopkins Jun 22 '17 at 21:00
  • $\begingroup$ Your labeling question looks interesting but unfamiliar, sorry. $\endgroup$ – David Eppstein Jun 23 '17 at 1:16
2
$\begingroup$

Consider the points in the cube as indexed by $(x,y,z) \in \mathbb{Z}_n^3$ and consider the point set $\{(x,y,z) : z = x + y\} \cup \{(x,y,z) : z = x + y + 1\}$. Here addition is done modulo $n$. This point set has $2n^2$ points - for each of the $n^2$ choices of $x$ and $y$ there are exactly two choices of $z$. By the same argument every row (in either direction) contains exactly two elements: fixing two of the variables leaves exactly two choices for the third.

Finally we argue that the point set is connected. First observe that if you are in a point (x,y,z) such that z = x + y then you can either increase z or decrease one of x or y. If you are in a point x,y,z such that z = x + y + 1 you can decrease z or increase one of x and y. We now give a path from any point $(x_1, y_1, z_1)$ to any other point $(x_2, y_2, z_2)$ in the point set. To go from $(x_1, y_1, z_1)$ to $(x_2, y_2, z_2)$, try first to bring $x_1$ closer to $x_2$ - if $x_1 < x_2$ then increase $x_1$ (you may have to decrease $z$ first). Once $x_1 = x_2$ do the same to make $y_1 = y_2$. At this point either $z_1 = z_2$ or they are one apart (and adjacent).

Note that the construction is tight because each row can only contain at most 2 points.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.