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

<p>The complexity of bendless three-dimensional orthogonal graph drawing.
D. Eppstein.
J. Graph Algorithms and Applications 17 (1): 35–55, 2013.
<a href="http://dx.doi.org/10.7155/jgaa.00283" rel="nofollow noreferrer">http://dx.doi.org/10.7155/jgaa.00283</a></p>

<p>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, <a href="https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html" rel="nofollow noreferrer">https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html</a> (see the ETA at the bottom).</p>

<p>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:</p>

<p>Isometric diamond subgraphs.
D. Eppstein.
16th Int. Symp. Graph Drawing, LNCS 5417, 2009, pp. 384–389.
<a href="https://arxiv.org/abs/0807.2218" rel="nofollow noreferrer">https://arxiv.org/abs/0807.2218</a></p>

CC BY-SA 3.0
2017-06-22T21:00:25.780Z
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
CC BY-SA 3.0
2017-06-23T01:16:27.953Z
Your labeling question looks interesting but unfamiliar, sorry.
David Eppstein
CC BY-SA 3.0
2017-06-22T20:43:44.047Z
2017-06-22T20:43:44.047Z
David Eppstein
<p>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.</p>

<p>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 &lt; 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). </p>

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

CC BY-SA 3.0
2017-06-22T20:30:42.050Z
2017-06-22T20:30:42.050Z
daniello
<p>Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:</p>

<ol>
<li><p>Each row in the cube (in any of the three directions) has exactly 2 or 0 points.</p></li>
<li><p>If two points are in the same row (any of three), connect them with an edge. The subset must be connected by these edges.</p></li>
</ol>

<p>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? </p>

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

<p>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.</p>

CC BY-SA 3.0
2017-06-22T20:09:02.090Z
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
CC BY-SA 3.0
2017-06-22T20:12:28.933Z
I guess if addition is done mod n then the above construction works
daniello
CC BY-SA 3.0
2017-06-22T20:22:09.320Z
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
CC BY-SA 3.0
2017-06-22T20:31:23.073Z
Wrote it now as an answer, hopefully this is more clear
daniello
<graph-theory><lower-bounds><hypergraphs>
Lower bound on the largest restrained cubic subset
Max Hopkins
# Lower bound on the largest restrained cubic subset

(Asked by: username_0 on 2017-06-22)

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.

**Tags:** graph-theory, lower-bounds, hypergraphs
> **Comments:**
> **username_1**: 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.  
> **username_1**: I guess if addition is done mod n then the above construction works  
> **username_0**: 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  
> **username_1**: Wrote it now as an answer, hopefully this is more clear  

---

## 2 answers

### Answer by username_2 on 2017-06-22. Score: 3 | Accepted answer

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>

> **Comments:**
> **username_0**: 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?  
> **username_2**: Your labeling question looks interesting but unfamiliar, sorry.  

---

### Answer by username_1 on 2017-06-22. Score: 2

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.


---

