Counting xyz-graphs in $\mathbb{Z}_n^3$

Question

This is a followup question to: Lower bound on the largest restrained cubic subset

How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$

This question may be seen as a generalization of counting simple cycles in $K_{n,n}$, via the hypergraph description of xyz-graphs given in the linked article. With that in mind, the problem reduces to solving for the number of "Hamiltonian" xyz-graphs, which in our generalization will be xyz-graphs (thought of as sets of hyper-edges) which touch every 2-edge in $K_{n,n,n}$ exactly twice. One example of such a Hamiltonian xyz-graph is provided in the linked question and at https://11011110.github.io/blog/2006/06/09/topology-of-xyz.html and is given by the set:

$\{(x,y,z) \ | \ x+y+z=0\} \ \cup \ \{(x,y,z) \ | \ x+y+z=1\}$

where addition is done mod n. Let the number of Hamiltonian xyz-graphs of $K_{n,n,n}$ be $H(n)$. Now we may simply look at how many copies of $K_{i,i,i}$ exist in $K_{n,n,n}$. This is simply ${n \choose i}^3$, which gives us the formula:

$ C(n) = \sum\limits_{i=2}^n {n \choose i}^3H(i) $

Note that $H(n)= \frac{n!(n-1)!}{2}$ in the 2-dimensional case of $K_{n,n}$. It seems like we could use a similar strategy for the 3-dimensional case and end up with something along the lines of $\frac{n!^2(n-1)!^2}{4}$ which would lead to

$ C(n) = \frac{1}{4}\sum\limits_{i=2}^n \frac{(i-1)!}{i}(n)_i^3 $

However I'm fairly certain this number is far too large, so there must be a number of extra constraints when building these Hamiltonian cycles.

EDIT: Unfortunately there are trivial examples of xyz-graphs which are not hamiltonian for some n, meaning that the above would only give a lower bound.

Answer 1

Consider that hamiltonian cycles of the bipartite graph are isomorphic (that is we can always permute the rows amongst themselves and the columns similarly to reach any other hamiltonian cycle).

Consider the planes given by $(x,-,-)$ and $(-,y,-)$. Permuting these planes is exactly the same as permuting the rows and columns of the $(-,-,z)$ planes. Thus we may permute in this way to get any of the hamiltonian cycles on one of the $(-,-,z)$ planes, giving us $n!(n-1)!/2$ unique xyz-graphs. Further, we may then permute the (-,-,z) plane, fixing only the one we specifically permuted before, each of which also must give a unique xyz-graph. Thus in total we have:

$H(n) \geq \frac{n!(n-1)!^2}{2}$

Which implies the bound

$C(n) \geq \frac{1}{2}\sum\limits_{i=2}^n \frac{(n)_i^3}{i^2}\\$.

EDIT: In fact, we can do better. We have only considered sub cubes here, but we may also consider xyz graphs inside ([n],[n],[m]). Since all simple cycles are hamiltonian on $K_{n,n}$, we take $m \leq n$ to avoid double counting. Then using the same construction for our first cycle and then the same permutation process above we get:

$H(n,m) \geq \frac{n!(n-1)(m-1)!}{2}$

and then

$C(n) \geq \frac{1}{2}\left (\sum\limits_{i,j=2 \ | \ i \geq j}^n \frac{(n)_i^2(n)_j}{ij} \right )$.