# Lower bound on the largest restrained cubic subset

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.

• 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. – daniello Jun 22 '17 at 20:09
• I guess if addition is done mod n then the above construction works – daniello Jun 22 '17 at 20:12
• 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 – Max Hopkins Jun 22 '17 at 20:22
• Wrote it now as an answer, hopefully this is more clear – daniello Jun 22 '17 at 20:31

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

• 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? – Max Hopkins Jun 22 '17 at 21:00
• Your labeling question looks interesting but unfamiliar, sorry. – David Eppstein Jun 23 '17 at 1:16

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.