Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints:Each row in the cube (in any of the three directions) has exactly 2 or 0 points.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.
Lower bound on the largest restrained cubic subset
graph theory;lower bounds;hypergraphs
These subsets of grids, and your graph-theoretic interpretation of them, are studied in my paperThe complexity of bendless three-dimensional orthogonal graph drawing.D. Eppstein.J. Graph Algorithms and Applications 17 (1): 3555, 2013.http://dx.doi.org/10.7155/jgaa.00283I 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. 384389.https://arxiv.org/abs/0807.2218