Perfect codes in the \(n\)-dimensional grid \(\Lambda_n\) of the lattice \(\mathbb{Z}^n\) (\(0<n\in\mathbb{Z}\)) and its quotient toroidal grids were obtained via the truncated distance in \(\mathbb{Z}^n\) given between \(u=(u_1,\cdots,u_n)\) and \(v=(v_1, \ldots,v_n)\) as the graph distance \(h(u,v)\) in \(\Lambda_n\), if \(|u_i-v_i|\le 1\), for all \(i\in\{1, \ldots,n\}\), and as \(n+1\), otherwise. Such codes are extended to superlattice graphs \(\Gamma_n\) obtained by glueing ternary \(n\)-cubes along their codimension 1 ternary subcubes in such a way that each binary \(n\)-subcube is contained in a unique maximal lattice of \(\Gamma_n\). The existence of an infinite number of isolated perfect truncated-metric codes of radius 2 in \(\Gamma_n\) for \(n=2\) is ascertained, leading to conjecture such existence for \(n>2\) with radius \(n\).
Motivated by ideas in computer architecture associated to signal transmission via a finite field (cf. [10, 9, 13]) and related with ideas in coding theory and lattice domination by means of the Lee metric arising from the Minkowsky \(\ell_p\) norm [4] with \(p=1\), these ideas are tied to the Golomb-Welch Conjecture [12, 14, 15] investigated via perfect Lee codes [10], diameter perfect Lee codes [13], tilings with generalized Lee spheres [2, 9], perfect dominating sets (PDS’s) [19], perfect-distance dominating sets (PDDS’s) [1] and efficient dominating sets [8].
Let \(0<n\in\mathbb{Z}\). The aforementioned codes and dominating sets are realized in the tiling of the lattice \(\mathbb{Z}^n\) whose tiles are translates of a common generalized Lee sphere. This tiling happens in the \(n\)-dimensional grid \(\Lambda_n\), namely the lattice graph whose vertex set is \(\mathbb{Z}^n\) with exactly one edge between each two vertices at euclidean distance 1. A natural follow-up here is to consider tilings of \(\mathbb{Z}^n\) with two different generalized Lee spheres, which for \(n>3\) is only possible by modifying the notion of Lee distance \(d\) to that of a truncated distance \(\rho\), defined below (not a standard distance, but see Remark 1.6), having perfect code applications (Subsection 1.3, based on the rainbow-coloring results of [11]).
Furthermore, superlattice graphs \(\Gamma_n\), namely compounds of ternary \(n\)-cubes glued along codimension 1 ternary subcubes (Remark 1.1 and Section 2) that generalize the lattice graphs \(\Lambda_n\) (even though the \(\Gamma_n\) are not lattice graphs themselves), allow to extend the mentioned perfect code applications (Section 3). These graphs \(\Gamma_n\) can be taken as “ alternate reality” graphs since they offer from each vertex of any of its ternary \(n\)-cubes glued in the compound \(\Gamma_n\) two ternary options as arrows indicating coordinate directions.
The Hamming distance \(h(u,v)\) between vectors \(u=(u_1,\cdots,u_n)\) and \(v=(v_1, \ldots,v_n)\) in \(\mathbb{Z}^n\subset\mathbb{R}^n\) is the number of positions \(i\in[n]=\{1, \ldots,n\}\) for which \(u_i\ne v_i\). Now, let \(\rho:\mathbb{Z}^n\times\mathbb{Z}^n\rightarrow\mathbb{Z}\) be given by: \[\begin{aligned} \label{ro}\rho(u,v)=\begin{cases} h(u,v),&\mbox{ if }|u_i-v_i|\le 1\mbox{ for all }i\in[n]; \\ n+1,& \mbox{otherwise.}\\ \end{cases} \end{aligned} \tag{1}\]
Given \(S\subseteq\mathbb{Z}^n\), let \([S]\) be the induced subgraph of \(S\) in \(\Lambda_n\). In (1), the Hamming distance \(h\) is equivalent to the graph distance in \(\Lambda_n\), which is extensible to the graphs \(\Gamma_n\). These graphs \(\Gamma_n\) allow the formation of algorithm flowcharts that can be adapted to follow directions in the ternary \(n\)-cubes, with vertices representing decision conditional diamonds that lead to “Yes” or “True” and “No” or “False” arrows, i.e. two oriented edges representing two sides of a triangle in a ternary \((n-1)\)-cube, each such arrow representing one or more process rectangles. An elementary example of this is given in Section 4.
We assign to each component \(H\) of \([S]\) an integer \(t_H>0\) to be understood as the radius of a truncated sphere with center \(H\). Moreover, for every component \(H'\) of \([S]\) in the translation class \(\langle H\rangle\) of \(H\) in \(\mathbb{Z}^n\), we assume \(t_{H'}=t_H\). This yields a correspondence \(\kappa\) from the set of translation classes \(\langle H\rangle\) of components \(H\) of \([S]\) into \(\mathbb{Z}\) such that \(\kappa(\langle H\rangle)=t_H\), \(\forall H\in\langle H\rangle\).
Let \(\rho(u,S)=\min\{\rho(u,s)|s\in S\}\). Let \((H)^{\kappa(\langle H\rangle)}=\{u\in\mathbb{Z}^n|\rho(u,H)\le\kappa(\langle H\rangle)\}\). For each component \(H\) of \(S\), \((H)^{\kappa(\langle H\rangle)}\) is the truncated sphere centered at \(H\) (or around \(H\)) with radius \(\kappa(\langle H\rangle)\). Here, \(H\) is the truncated center of \((H)^{\kappa(\langle H\rangle)}\) and its vertices are the central vertices of \(H\).
A \(\kappa\)–perfect truncated-metric code, or \(\kappa\)-PTMC, is a set \(S\subseteq\mathbb{Z}^n\) such that for every \(u\in\mathbb{Z}^n\) there exists a unique \(s\in S\) with \(\rho(u,s)=\rho(u,S)\) and such that the collection \[\begin{aligned} \{(H)^{\kappa(\langle H\rangle)}|H\mbox{ is a connected component of }S\}, \end{aligned} \tag{2}\] forms a partition of \(\mathbb{Z}^n\).
Given \(0<t\in\mathbb{Z}\), a \(\kappa\)-PTMC is a \(t\)-PTMC if all \(\kappa(\langle H\rangle)\)’s are equal to \(t\). If \(|H|=1\), then \(|(H)^t|=\sum_{i=0}^t2^i{n\choose i}\), for \(0\le t\le n\), (which is less than the cardinal of the corresponding \(\ell_1\) sphere of radius \(t\), for \(t>1\) [4]). We note that 1-PTMC’s coincide with PDS’s [19].
Remark 1.1. A binary (resp. ternary) \(n\)–cube graph \(Q_n^i\), succinctly called \(n\)–cube (resp. \(n\)–tercube), is a cartesian product \(K_i\square\cdots\square K_i\) of \(n\) complete graphs \(K_i\) with \(V(K_i)=\{0, \ldots,i-1\}=F_i\), the field of order \(i=2\) (resp. \(3\)). In Sections 2 and 3, we extend the study of PTMC’s from the graphs \(\Lambda_n\) to the graphs \(\Gamma_n\). These cannot have non-isolated PDS’s, or non-isolated 1-PTMC’s. However, the ternary perfect single-error-correcting codes of length \(\frac{3^t-1}{2}\) [2, 17] are isolated PDS’s, that is efficient dominating sets [8] in the ternary \(\frac{3^t-1}{2}\)-cubes. These also are edge-disjoint unions of triangles, for \(t>0\).
In \(\Gamma_n\) for Sections 2 and 3, we redefine now a non-isolated PDS as a subset \(S\subset V(\Gamma_n)\) if every vertex of \(\Gamma_n\) not in \(S\) is adjacent to just either one vertex of \(S\) (as in PDS’s) or the two end-vertices of an edge of \(S\). As a consequence now, a non-isolated PDS is not necessarily a PDS.
Remark 1.2. Some graph-coloring results of [11] are restated below in Theorem 1.11-1.13 in terms of PTMC’s asserting the existence of PTMC’s in \(\Lambda_n\) that are lattice [13], that is lattice-like [1], having their induced components \(H\) with vertex sets:
(a) whose convex hulls are \(n\)-parallelotopes (resp. both 0-cubes and \((n-1)\)-cubes);
(b) contained in, and dominating, truncated spheres centered at the components \(H\) of radius \(n\) (resp. radii \(n-2\) and 1) that are the tiles of an associated lattice tiling of \(\mathbb{Z}^n\); for \(n=3\), this is schematized on the left of Figure 1 representing the assignment of the last coordinate value mod 3 on the projection of the PTMC onto \(\mathbb{Z}^{n-1}\); the case \(n=4\) (the first PTMC which is neither PDS nor PDDS) can be visualized in the same way, where the dominating edges, red colored in the copy of \(Q^2_4\subset\mathbb{Z}^4\) on the right of Figure 1 indicate truncated spheres of radius 2 and 1 centered respectively at \((0,0,0,0)\) and \((1,1,1,1)\).
Remark 1.3. We observe that:
(I) a \(t\)-PTMC (resp. a truncated \(t\)-sphere) of \(\Lambda_n\) is defined like a PDDS [1] (resp. generalized Lee sphere [9]) with \(\rho\) instead of the Lee distance \(d\);
(II) 1-PTMC’s of \(\Lambda_n\) (resp. truncated 1-spheres) coincide with PDS’s [19] (resp. generalized Lee 1-spheres).
(III) an example [1] cited in Remark 1.10, below, justifies that our definition of PTMC above employs translation classes instead of isomorphism classes, for in such example the truncated spheres have common radius (namely 1) for both appearing translation classes, but that does not exclude the eventuality of an example with differing radii.
Remark 1.4. Related to Theorems 1.12 and 1.13 on building “lattice” \(\kappa\)-PTMC’s whose induced components are \(r\)-cubes of different dimensions \(r\) (\(0\le r\le n\)), we have:
(A) the perfect covering codes with spheres of two different radii in Chapter 19 [5] and
(B) a negative answer [18] to a conjecture [19] claiming that the induced components of every 1-PTMC \(S\) in an \(n\)-cube \(Q^2_n\) are all \(r\)-cubes \(Q^2_r\) (not necessarily in the same translation class [7]), with \(r\) fixed. In fact, it was found in [18] that a 1-PTMC in \(Q^2_{13}\) whose induced components are \(r\)-cubes \(Q^2_r\) of two different values \(r=r_1\) and \(r=r_2\) exists, specifically for \(r_1=4\) and \(r_2=0\). This seems to be the only known counterexample to the cited conjecture [19].
If no confusion arises, every \((a_1, \ldots,a_n)\in\mathbb{Z}^n\) is expressed as \(a_1\cdots a_n\). Let \(O=00\cdots 0\), \(e_1=10\cdots 0\), \(e_2=010\cdots 0\), \(\ldots\), \(e_{n-1}=0\cdots 010\) and \(e_n=00\cdots 01\).
Let \(z\in\mathbb{Z}^n\), let \(H=(V,E)\) be a subgraph of \(\Lambda_n\) and let \(H+z\) be the subgraph \(H'=(V',E')\) whose vertex set is \(V'=V+z=\{w\in\mathbb{Z}^n;\exists\; v\in V\) such that \(w=v+z\}\) so that \(uv\in E\) \(\Leftrightarrow\) \((u+z)(v+z)\in E'\). For example, let \(H\) be induced in \(\Lambda_n\) by the vertices with entries in \(\{0,1\}\). Then, every translation \(H+z\) of \(H\) in \(\Lambda_n\) (in particular \(H\) itself) is isomorphic to \(Q^2_n\).
Let \(i\in[n]\). Each edge (resp. segment) \(uv\) of \(\Lambda_n\) (resp. \(\mathbb{R}^n\supset\mathbb{Z}^n\)) with \(u\ne v\) is parallel to \(Oe_i\in E(\Lambda_n) \Leftrightarrow u-v\in\{\pm e_i\}\) (resp. \(\Leftrightarrow\exists a\in\mathbb{R}\setminus\{0\}\) with \(u-v=ae_i\)). A parallelotope \(\mathcal P\) in \(\mathbb{R}^n\) is a cartesian product of segments parallel to some of the \(Oe_i\)’s (\(i\in[n]\)). We restrict to parallelotopes \(\mathcal P\) having their vertices in \(\mathbb{Z}^n\). An edge of \(\mathcal P\) is a segment of unit length parallel to some \(Oe_i\) (\(i\in[n]\)) separating a pair of vertices of \(\Lambda_n\) in \(\mathcal P\). Recall that a trivial subgraph of \(\Lambda_n\) is composed by just one vertex. The proof of the following is similar to that of Theorem 1 [1].
Theorem 1.5. Let \(0<t\in\mathbb{Z}\). If \(S\) is a \(t\)-PTMC in \(\Lambda_n\), then the convex hull in \(\mathbb{R}^n\) of the vertex set \(V(H)\) of each nontrivial component \(H\) of \([S]\) is a parallelotope in \(\mathbb{R}^n\) whose edges are parallel to some or all of the segments \(Oe_i\) in \(E(\Lambda_n)\), where \(i\in[n]\).
Let \(H\) be a nontrivial induced subgraph of \(\Lambda_n\) with the convex hull of \(V(H)\) in \(\mathbb{R}^n\) as a parallelotope whose edges are parallel to some or all of the segments \(Oe_i\) in \(E(\Lambda_n)\), (\(i\in[n]\)). If exactly \(r\) elements of \([n]\) are such values of \(i\), then we say that \(H\) is an \(r\)–box. Note that \(H\) is a cartesian product \(\Pi_{i=1}^n P^i\), where \(P^i\) is a finite path, \(\forall i\in[n]\), with exactly \(r\) paths \(P^i\) having positive length.
Let \(W_{n,H,t}\) be the truncated sphere of radius \(t\) around an \(H\) as above, where \(0\le t\in\mathbb{Z}\). Then, \(H\) is the truncated center of \(W_{n,H,t}\). A \(t\)-PTMC \(S\) of \(\Lambda_n\) determines a partition of \(\mathbb{Z}^n\) into spheres \(W_{n,H,t}\) with \(H\) running over the components of \([S]\). Such an \(S\) with the components of \([S]\) obtained by translations from a fixed finite graph \(H\) is said to be a \(t\)-PTMC\([H]\). (This imitates the definition of a \(t\)-PDDS\([H]\) in [1], mentioned in Remark 1.3(I) above). Let \(S\) be a \(t\)-PTMC\([H]\) and let \(H'\) be a component of \([S]\) obtained from \(H\) by means of a translation. Then \(S\) is said to be a lattice \(t\)-PTMC\([H]\) if and only if there is a lattice \(L\subseteq\mathbb{Z}^n\) such that: \(H''\) is a component of \([S]\) \(\Leftrightarrow\) \(H''=H'+z\), for some \(z\in L\).
Remark 1.6. It is relevant to note the connections of \(\rho\) and the \(\ell_p\) metrics [4]: A truncated sphere of truncated radius 1 centered at some vertex \(v\) is a Lee (\(p=1\)) sphere of radius 1, whereas a truncated sphere of truncated radius \(n\) centered at \(v\) is a sphere of radius 1 in the maximum (\(p=\infty\)) distance, namely \(W_{n,\{v\},1}\) (which has an \(n\)-dimensional cube for convex hull). Thus, all truncated spheres in this work are spheres in some \(\ell_p\) metric, and the truncated metrics are a convenient way to consider different \(\ell_p\) metrics for the graph components. This observation allows connections with other previous works such as (for just one \(t\)) perfect codes in the maximum metric and in the \(\ell_p\) metrics [4].
Remark 1.7. We start to rephrase the graph-coloring facts of [11], to be completed in Subsection 1.3. Announced as Theorem 1.11 below, there is a construction of lattice \(n\)-PTMC’s \(S\) whose induced subgraphs \([S]\) in \(\Lambda_n\) have their components \(H\) with:
(i) vertex sets \(V(H)\) whose convex hulls are \(n\)-boxes in \(\mathbb{R}^n\) with distance 3 to \([S]\setminus H\), and representatives (one per component \(H\)) forming a lattice with generators along the coordinate directions;
(ii) each \(V(H)\) contained in a truncated sphere \((H)^{\kappa(\langle H\rangle)}\) whose radius is \(n\).
(We do not know whether similar lattice \(t\)-PTMC’s \(S\) exist with \([S]\) having \(r\)-parallelotopes as their components, for \(r\) fixed such that \(0<r<n\).)
Extending the meaning of the adjective lattice in Subsection 1.2 below, as in [11] we have in Theorems 1.2 and 1.3 that a lattice \(\kappa\)-PTMC \(S\) exists in \(\Lambda_n\) whose induced subgraph \([S]\) has its components \(H\) with vertex sets \(V(H)\):
(i\('\)) having both \((n-1)\)-cubes and \(0\)-cubes as their convex hulls in \(\mathbb{R}^n\);
(ii\('\)) contained in truncated spheres \((H)^{\kappa(\langle H\rangle)}\) whose radii, namely 1 and \((n-2)\), correspond respectively to the \((n-1)\)-cubes and 0-cubes in item (i\('\)).
A set \(S\subset \mathbb{Z}^n=E(\Lambda_n)\) is periodic if and only if there exist \(p_1, \ldots,p_n\) in \(\mathbb{Z}\) such that \(v\in S\) implies \(v\pm p_ie_i\in S, \forall i\in[n]\). Since each lattice \(t\)-PTMC\([H]\) \(S\) is periodic [1], then every canonical projection from \(\Lambda_n\) onto a toroidal grid \(\mathcal T\), i.e. a cartesian product \({\mathcal T}=C_{k_1p_1}\square C_{k_2p_2}\square\cdots\square C_{k_np_n}\) of \(n\) cycles \(C_{k_ip_i}\) (\(0<k_i\in\mathbb{Z}, \forall i\in[n]\)), takes \(S\) onto a \(t\)-PTMC\([H]\) in \(\mathcal T\). This observation adapts to respective situations that complement the statements of Theorems 1.11-1.13 via canonical projections from \(\mathbb{Z}^n\) onto adequate toroidal grids \(\mathcal T\).
Question 1.8. Do lattice \(t\)-PTMC’s \(S\) exist with \([S]\) having \(r\)-parallelotopes as their components, for \(r\) fixed such that \(0<r<n\)?
Given a lattice \(L\) in \(\mathbb{Z}^n\), a subset \(T\subseteq\mathbb{Z}^n\) that contains exactly one vertex in each class mod \(L\) (so that \(T\) is a complete system of coset representatives of \(L\) in \(\Lambda_n\)) is said to be an FR (acronym suggesting “fundamental region”) of \(L\). A partition of \(\mathbb{Z}^n\) into FR’s of \(L\) is said to be a tiling of \(\mathbb{Z}^n\). Those FR’s are said to be its tiles.
We extend the notion of lattice \(\kappa\)-PTMC so that the associated fundamental region (see [3], pg 26), or FR (see above) of every new lattice contains a finite number of (in our applications, just two) members \(H\) of each \(\langle H\rangle\).
In the literature, existing constructions of lattice \(t\)-PTMC’s in \(\Lambda_n\) (\(t<n\)) concern just \(t=1\) (see [1, 2, 9, 13]) but there are not many known lattice \(1\)-PTMC’s. For example, [8] shows that there is only one lattice \(1\)-PTMC\([Q^2_2]\) and no non-lattice \(1\)-PTMC\([Q^2_2]\). In addition, there is a lattice 2-PDDS\([Q^2_1]\) in \(\Lambda_3\) arising from a tiling of Minkowsky cited in [1].
Conjecture 1.9. There is no \(t\)-PTMC lattice in \(\Lambda_n\), for \(1<t<n\).
This conjecture has an analogous form for perfect codes in the \(\ell_p\) metrics in [4], and together with the conjecture mentioned in Remark 1.4(B), produces a contrast with the constructions in Theorems 1.12 and 1.13, below.
If \(S\) is a periodic non-lattice \(t\)-PTMC\([H]\) in \(\Lambda_n\), then there exists \(0<m\in\mathbb{Z}\) and a tiling of \(\Lambda_n\) with tiles that are disjoint copies of the vertex set \(V(H^*)\) of a connected subgraph \(H^*\) induced in \(\Lambda_n\) by the union of:
(a) the vertex sets of \(m\) disjoint copies \(H^1, \ldots,H^m\) of \(H\) (components of \([S]\));
(b) the sets \((H^j)^{\kappa(\langle H\rangle)}\) of vertices \(v\in\mathbb{Z}^n\) with \(\rho(v,H^j)\le t\), for \(j\in[m]\), where
\((H^1)^{\kappa(\langle H\rangle)}, \ldots,(H^m)^{\kappa(\langle H\rangle)}\) are pairwise disjoint copies of \((H)^{\kappa(\langle H\rangle)}\) in \(\mathbb{Z}^n\).
By taking such an \(m\) as small as possible, we say that \(S\) is a \(t\)-PTMC\([H;m]\).
Remark 1.10. In Section 5 [1], a non-lattice \(1\)-PTMC\([Q^2_1;4]\) \(S\) is shown to exist with a lattice \(L_S\) based on it, each of the FR’s of \(L_S\) containing two copies of \(Q^2_2\) parallel to \(Oe_1\) and two more copies of \(Q^2_2\) parallel to \(Oe_2\), these four copies being components of \([S]\), namely generated say by the vertices \((1,0)\), \((2,0)\), \((1,3)\), \((2,3)\), \((0,1)\), \((0,2)\), \((3,1)\) and \((3,2)\).
Thus, even for a non-lattice \(t\)-PTMC \(S\) in a \(\Lambda_n\), a lattice can be recovered and formed by selected vertices \(v_T\) in the corresponding tiles \(T\) associated with \(S\). We say that such set \(S\) is a lattice \(t\)-PTMC\([H;m]\), indicating the number \(m\) of isomorphic components of \([S]\) in a typical tile \(T\) in which to fix a distinguished vertex \(v_T\).
We further specify the developments above as follows. A \(t\)-PTMC \(S\) in \(\Lambda_n\) with the components of \([S]\) obtained by translations from two non-parallel subgraphs \(H_0,H_1\) of \(\Lambda_n\) is said to be a \(t\)-PTMC\([H_0,H_1]\). The case of this in Remark 1.10 is a \(\kappa\)-PTMC, with two translation classes of components of \([S]\) formed by the copies of \(Q^2_2\) parallel to each of the directions coordinates. Here, \(\kappa\) sends those copies onto \(t=1\). Each tile of this \(\kappa\)-PTMC contains two copies of \(Q^2_2\) parallel to \(Oe_1\) and two copies of \(Q^2_2\) parallel to \(Oe_2\), accounting for \(m=4\).
More generally, let \(t_i\in[n]\), for \(i=0,1\). We say that a set \(S\subset V\) is a \((t_0,t_1)\)-PTMC\([H_0,H_1]\) in \(\Lambda_n\) if for each \(v\in V\) there is:
(i\(''\)) a unique index \(i\in\{0,1\}\) and a unique component \(H_v^i\) of \([S]\) obtained by means of a translation from \(H_i\) such that the truncated distance \(\rho(v,H_v^i)\) from \(v\) to \(H_v^i\) satisfies \(\rho(v,H_v^i)\leq t_i\) and
(ii\(''\)) a unique vertex \(w\) in \(H_v^i\) such that \(\rho(v,w)=\rho(v,H_v^i)\).
Even though such a set \(S\) is not lattice as in [13] (or lattice-like [1]), it may happen that there exists a lattice \(L_S\subset\mathbb{Z}^n\) such that for \(0<m_0,m_1\in\mathbb{Z}\) there exists an FR of \(L_S\) in \(\Lambda_n\) given by the union of two disjoint subgraphs \(H^*_0,H^*_1\), where \(H^*_i\) (\(i=0,1\)) is induced in \(\Lambda_n\) by the disjoint union of:
(a\('\)) the vertex sets of \(m_i\) disjoint copies \(H_i^1, \ldots,H_i^{m_i}\) of \(H_i\), (components of \([S]\));
(b\('\)) the sets \((H_i^j)^{\kappa(\langle H\rangle)}\) of vertices \(v\in\mathbb{Z}^n\) for which \(0<\rho(v,H_i^j)\le t_i\) , for \(j\in[m_i]\), where \((H_i^1)^{\kappa(\langle H\rangle)}, \ldots,(H_i^{m_i})^{\kappa(\langle H\rangle)}\) are pairwise disjoint copies of \(H^\kappa(\langle H\rangle))\) in \(\mathbb{Z}^n\).
A particular case of lattice \(t\)-PTMC\([H]\) is that in which \(H\) is an \(n\)-box of \(\Lambda_n\). For each such \(H\), Theorem 1.11 below says that there is a lattice \(n\)-PTMC\([H]\) in \(\Lambda_n\). (In [2], \(n\)-boxes of unit volume in \(\Lambda_n\) are shown to determine \(1\)-PDDS\([H]\)’s if and only if either \(n=2^r-1\) or \(n=3^r-1\)).
From Subsection 1.1 we know that \(S\) determines a partition of \(\mathbb{Z}^n\) into spheres \(W_{n,H',n}\), where \(H'\) runs over the components of \([S[\). In each \(W_{n,H',n}\), let \(b_1b_2\cdots b_n\) be the vertex \(a_1a_2\cdots a_n\) for which \(a_1+a_2+\cdots+a_n\) is minimal. We say that this \(b_1b_2\cdots b_n\) is the anchor of \(W_{n,H',n}\). The anchors of the spheres \(W_{n,H',n}\) form the lattice \(L=L_S\). Without loss of generality we can assume that \(O\) is the anchor of a \(W_{n,H_0,n}\) whose truncated center \(H_0\) is a component of \([S]\). Let \(c_1c_2\cdots c_n\) be the vertex \(a_1a_2\cdots a_n\) in \(W_{n,H_0,n}\) for which \(a_1+a_2+\cdots +a_n\) is maximal. Then \(L_S\) has generating set \(\{(1+c_1)e_1,(1+c_2)e_2,\ldots,(1+c_n)e_n\}\) and is formed by all linear combinations of those \((1+c_i)e_i\), (\(i\in[n]\)).
Theorem 1.11. [11] For each \(i\in[n]\), let \(P_i\) be a path of length \(c_i-2\), parallel to \(Oe_i\), and let \(H=\Pi_{i=1}^nP_i\) be an \(n\)-box in \(\Lambda_n\). Then, there is a lattice \(n\)-PTMC\([H]\) \(S\) of \(\Lambda_n\) with minimum \(\ell_1\)-distance 3 between the components of \([S]\).
Theorem 1.12. [11] There exists a lattice \(1\)–PTMC\([Q^2_2,Q^2_0;2,2]\) (in particular a PDS) \(S\) in \(\Lambda_3\) with minimum \(\ell_1\)-distance 3 between the components of \([S]\).
To state Theorem 1.13, let \(H_0=Q^2_{n-1}\), \(H_1=Q^2_0\), \(m_0=m_1=2\), \(t_0=1\), \(t_1=n-2\).
Theorem 1.13. There exists a lattice \((1,n-2)\)–PTMC\([Q^2_{n-1},Q^2_0;2,2]\) \(S\) in \(\Lambda_n\).
Remark 1.4. From the last observation in Remark 1.7, (just before Question 1.8), it can be deduced that the respective PTMC \(S\) covers (via canonical projections) in Theorems 1.11, 1.12 and 1.3, respectively:
\(\bullet\) an \(n\)-PTMC\([H]\) in \({\mathcal T}=\) \(C_{c_1k_1}\square C_{c_2k_2}\square\cdots\square C_{c_nk_n}, (1<k_i\in\mathbb{Z},\forall i\in[n]);\)
\(\bullet\) a \(1\)–PTMC\([Q^2_2,Q^2_0;2,2]\) in \({\mathcal T}=\) \(C_{6k_1}\square C_{6k_2}\square C_{3k_3}, (0<k_i, \forall i\in[3]);\)
\(\bullet\) a \((1,n-2)\)–PTMC\([Q^2_{n-1},Q^2_0;2,2]\) in \({\mathcal T}=\) \(C_{6k_1}\square\dots\square C_{6k_{n-1}}\square C_{3k_n}, (0<k_i, \forall i\in[n]).\)
Let the 2-tercube, or tersquare, \(Q_2^3\) be denoted \([\emptyset]\), with vertices given by the 2-tuples \(xy\), (\(x,y\in F_3=\{0,1,2\}\)). As a graph, \([\emptyset]=(0,1,2)\square(0,1,2),\) namely the cartesian product of two triangles whose vertex sets are both \(F_3\), is represented at the center of Figure 2 sharing a triangle with each one of 15 tersquares, to be specified below, in respective partially viewable colored backgrounds. The 1-sub-tercubes or triangles \(Q_1^3\) of the 2-tercube \([\emptyset]\) have vertex sets \(\{0y\}_{y\in F_3}\), \(\{1y\}_{y\in F_3}\), \(\{2y\}_{y\in F_3}\), \(\{x0\}_{x\in F_3}\), \(\{x1\}_{x\in F_3}\), \(\{x2\}_{x\in F_3}\). They will be indicated \(x^0\), \(x^1\), \(x^2\), \(y^0\), \(y^1\), \(y^2\), respectively. To each of these triangles \(t^s\) (\(t\in\{x,y\};s\in F_3\)) of \([\emptyset]\) we glue a corresponding tersquare \([^t_s]\) intersecting \([\emptyset]\) exactly in \(t^s\).
This way, six tersquares \([^x_0], \ldots,[^y_2]\) are obtained (to be called subcentral tersquares, colored yellow and light-blue in Figure 2) that intersect \([\emptyset]\) respectively in the triangles \(x^0, \ldots,y^2\). Next, we glue to the remaining new triangles (i.e., other than those already in \([\emptyset]\)), a set of nine new tersquares that we denote \([^{xy}_{00}], \ldots,[^{xy}_{22}]\) (and call corner tersquares, colored green and gray in Figure 2). These nine tersquares share merely a vertex with \([\emptyset]\) and their disposition with respect to the central tersquare \([\emptyset]\) and subcentral tersquares \(x^0, \ldots,y^2\) is specified in Figure 2. In fact, \([^{xy}_{ij}]\) shares a triangle \(y^j\) with \([^x_i]\) and a triangle \(x^i\) with \([^y_j]\), for \(i,j=0,1,2\). Such triangles can be further specified respectively as \(y^j[^x_i]\) and \(x^i[^y_j]\).
The graph \([[\emptyset]]\) resulting from the union of the \(1+6+9=16\) tersquares constructed so far, will be referred to as the 2-hive \([[\emptyset]]\). The central tersquare \([\emptyset]\) of \([[\emptyset]]\) shares just one triangle with each of the six subcentral tercubes and just one vertex with each of the nine corner tersquares. The tersquare \([\emptyset]\), given as a subgraph at the center of Figure 2, also results in the representation at the lower-right quarter of Table 1 by identifying the quadruple of vertices labelled 22, as well as each pair of vertices labelled 20, 21, 02 and 12.
The construction above continues with the iterative glueing of tersquares along free triangles, namely those triangles along which glueing of a new continuing tersquare was not already performed. In the limit of feasible glueings, a total compound graph \(\Gamma_2\) of tersquares, glued in pairs of adjacent tersquares along corresponding triangles, results in an infinite locally finite graph, the ternary square compound graph \(\Gamma_2\), that we also call ternary non-lattice superlattice graph. Notation for all tersquares and triangles of \(\Gamma_2\), continuing the notation of the 16 tersquares and their triangles above, is completed below. The word “superlattice” here corresponds to the fact that, even though \(\Gamma_n\) is not a lattice graph itself, it is such that each of its binary \(n\)-cubes is contained in a unique maximal lattice of \(\Gamma_n\).
Three subgraphs of \(\Gamma_2\) are represented in Table 1, containing just one 4-cycle (of the 9 in \(Q_2^3\)) per participating (but not totally shown) glued tersquare. This yields 9 sub-lattice types in \(\Gamma_2\) (one per 4-cycle of \(Q_2^3\), three partially shown in Table 1), each isomorphic to \(\Lambda_2\). Thus, \(\Gamma_2\) is a superset of each of the copies of \(\Lambda_2\) generated by some 4-cycle of \(\Gamma_2\). We further specify \(\Gamma_2\) after presenting a non-isolated PDS in \([[\emptyset]]\) (Theorem 2.1).
The large connected graph in Figure 2 represents the 2-hive \([[\emptyset]]\), with \([^x_0]\), \([^x_1]\) and \([^x_2]\) in light-blue background, \([^y_0]\), \([^y_1]\) and \([^x_2]\) in yellow background, and the nine tersquares \([^{xy}_{i\,j}]\) in green background if \(y\ne 1\) and light-gray background if \(y=1\), where the apparent colored areas spatial disposition results in the partial hiding of some of these areas. The thick red edges induce a subgraph of \([[\emptyset]]\) whose vertex set is a non-isolated PDS \(S\) (as defined in Remark 1.1) of \([[\emptyset]]\). The dominating edges are drawn in thick black trace, allowing the reader to verify that all vertices of \([[\emptyset]]\) not in \(S\) are dominated as indicated in Remark 1.1. (It is elementary to verify that no isolated PDS in \([[\emptyset]]\) exists). The remaining edges of \([[\emptyset]]\), not in thick trace, are in dashed trace if they are “exterior” edges of \([[\emptyset]]\) (i.e., those shared by 2-hives other than \([[\emptyset]]\) in \(\Gamma_2\)) and in thin trace otherwise (i.e., if they are “interior” edges of \([[\emptyset]]\)). Motivation for pursuing such a non-isolated PDS arose as a palliative remedy for the impossibility of having here a PDS like the Livingston-Stout PDS in the grid \(P_4\square P_4\) [16], which happens to be the only isolated PDS in grid graphs \(P_m\square P_n\), for \(2<min\{m,n\}\) [6].
Theorem 2.1. There exists a non-isolated PDS, or 1-PTMC\([Q_1^2,Q_2^2,Q_1^3\square Q_1^2;4,\) \(1,1]\), in the 2-hive \([[\emptyset]]\subset\Gamma_2\).
Proof. The claimed PDS in \([[\emptyset]]\) is formed by the vertex sets of the following components (of its induced subgraphs):
(a) the edge \((00,01)\) of triangle \((00,01,02)\) shared by tersquares \([^y_2]\) and \([^{xy}_{02}]\);
(b) the edge \((10,20)\) of triangle \((00,10,20)\) shared by tersquares \([^x_0]\) and \([^{xy}_{00}]\);
(c) the edge \((21,22)\) of triangle \((20,21,22)\) shared by tersquares \([^y_0]\) and \([^{xy}_{20}]\);
(d) the edge \((00,02)\) of triangle \((00,02,01)\) shared by tersquares \([^y_1]\) and \([^{xy}_{01}]\);
(e) the 4-cycle \((02,12,11,01)\) of tersquare \([^x_2]\), where its edge \((02,12)\) (of triangle \(\Delta=(02,12,22)\)) is shared (with \(\Delta\)) with tersquare \([^{xy}_{22}]\);
(f) the triangular prism in \([^x_1]\) formed by triangles \((00,01,02)\) and \((20,\) \(21,22)\) and edges \((00,20)\), \((02,22)\) (of triangle \((02,22,12)\), shared by tersquare \([^{xy}_{22}]\)) and \((01,21)\) (of triangle \((01,21,11)\), shared by tersquare \([^{xy}_{11}]\)).
As can be verified in Figure 2, the edges departing from these red-edge components cover all other vertices of \([[\emptyset]]\), proving the theorem. ◻
Figure 2 may be augmented by adding the tersquares \([^{xx\,y}_{i\,j\,k}]\), with \(i\ne j\) in \(F_3\), etc. One may continue by adding tersquares \([^{xx\cdots xx\,yy\cdots yy}_{i\,j\,\cdots kl\,mn\cdots pq}]\) with \(i\ne j\ne\ldots\ne k\ne l\) (resp. \(m\ne n\ne\ldots\ne p\ne q\)), i.e. not two contiguous equal values under the \(x\)’s (resp. \(y\)’s). Taking \(i,j,\ldots,k,l,m,n,\ldots p,q\) in \(F_3\) to be contiguously different with just two values, (e.g. 0,1; resp. 0,2; resp. 1,2, in the upper-left; resp. upper-right; resp. lower-left quarter in Table 1) is a way of obtaining 3 sub-lattices of \(\Gamma_2\), each isomorphic to \(\Lambda_2\), as in Table 1. But there is an infinite family of “parallel” sub-lattices in \(\Gamma_2\) for each of the 9 sublattice types, one per each 4-cycle of a typical tersquare as in the lower-left quarter of Table 1. For example, the type with values 0,2 represents “parallel” sub-lattices having “shortest” tersquares \([\emptyset]\), \([^x_1]\), \([^y_1]\), \([^{xx}_{01}]\), \([^{yy}_{01}]\), \([^{xx}_{21}]\), \([^{yy}_{21}]\), etc., including every \([^{xx\cdots xx}_{i\,j\,\cdots kl}]\), \([^{\,y\,y\cdots y\,y}_{mn\cdots pq}]\) and \([^{xx\cdots xx\,\,yy\cdots yy}_{i\,j\,\cdots kl\,mn\cdots pq}]\).
These sub-lattices can be refined by replacing each edge \(e\) in them by the 2-path closing a triangle with \(e\) and adding more vertices and additional edges out of them to the new vertices obtained by the said replacement, in order to distinguish the glued \(2\)-tercubes in \(\Gamma_2\). In particular, Figure 2 is obtained from such a procedure by starting from a plane containing the upper-right quarter of Table 1. Figure 3 shows a projection of a partial extension of Figure 2 in such a plane, where tersquare colors are kept as in Figure 2, including if they are projected into a 2-path. Colors here still are light-blue, blue, green and light-gray. Each tersquare in Figure 3, represented by four squares with the common central vertex \(11\), is just recognizable by its upper-left vertex denomination presence. Of the four such squares, the lower-right one has the corresponding tersquare denomination. The other tersquare denominations in the three remaining squares correspond to the counterpart denominations in the representation of \([\emptyset]\).
Definition 2.2. A ternary \(n\)-cube compound graph \(\Gamma_n\) is defined as the union of all necessary \(n\)-tercubes that appeared glued along their (codimension 1) ternary \((n-1)\)-subtercubes, for any \(2<n\in\mathbb{Z}\). The vertices of such \(\Gamma_n\) are given in terms of the \(n\)-tercubes. These, that can be denoted \[[^x_0],[^y_0],\ldots,[^z_0],[^x_1],[^y_1],\ldots,[^z_1],[^x_2],[^y_2],\ldots,[^z_2],[^{xy}_{00}],\ldots,\] including all those of the general form \([J]=[^{xx\cdots xx\,yy\cdots yy\,\cdots\cdots\cdots\, zz\cdots zz}_{i\,j\,\cdots kl\,mn\cdots pq\,\cdots\cdots\cdots\,rs\cdots vw}]\), where \(x,y,\ldots,z\) represent the \(n\) (ternary) coordinate directions. Such \(n\)-tercubes are assigned locally by reflection on the \((n-1)\)-subtercubes. Thus the said vertices can be denoted \(x^0[J],\ldots,z^2[J]\), by following the notations above.
Example 2.3. Figure 2 for \(n=2\), represents the 2-hive \([[\emptyset]]\) with \([\emptyset]\) at its center, and its neighboring tersquares \([^x_0]\), \([^x_1]\), \([^x_2]\) in light-blue background, \([^y_0]\), and \([^y_1]\), \([^y_2]\) in yellow background, and the tersquares neighboring those tersquares, namely \([^{xy}_{i\,j}]\), (\(i,j\in F_3\)), in green and light-gray backgrounds. It can be seen that \(\Gamma_n\) may be considered as a superset of \(\Lambda_n\) in three different ways, as was commented above in relation to Table 1 for \(n=2\).
We pose the following.
Question 2.4. Does there exist a non-isolated PDS \(S\) in \(\Gamma_n\), for \(n\ge 2\)? If so, could \(S\) behave like a lattice, for example by restricting itself to a lattice PDS over any sub-lattice of \(\Gamma_n\), as exemplified in Table 1?
In this section, we keep working in \(\Gamma_2\), but slightly modifying the definition of a \(\kappa\)-PTMC by replacing the used Hamming distance \(h\) by the graph distance of \(\Gamma_2\). It is clear that the Hamming distance in our graph-theoretical context is just the graph distance. Then, we have the following result.
Theorem 3.1. There exists 262144 isolated 2-PTMC’s in the 2-hive \([[\emptyset]]\subset\Gamma_2\).
Proof. In Figure 4, the nine copies \([^{xy}_{ij}]\), (\(i,j\in F_3\)), of the tersquare are shown with its edges in thick black trace, against the thin black trace of the remaining edges of the 2-hive \([[\emptyset]]\). These nine copies happen to be the truncated 2-spheres centered at the vertices of an isolated PTMC of \([[\emptyset]]\) constituted as a selection of one vertex per yellow-faced 4-cycle in the figure. We may say that these yellow-faced 4-cycles are the ”external” 4-cycles of \([[\emptyset]]\). So, there are \(4^9=262144\) 2-PTMC’s in \(\Gamma_2\). ◻
Corollary 3.2. There exists a 2-PTMC\([Q_2^2]\) in the 2-hive \([[\emptyset]]\).
Proof. The yellow-faced 4-cycles are copies of \(Q_2^2\) and induce the components of the claimed 2–PTMC-\([Q_2^2]\). ◻
Theorem 3.3. There exists an infinite number of isolated 2-PTMC in \(\Gamma_2\).
Proof. Let us analyze one of the yellow squares in Figure 4, say square (00, 01,11,10) in tersquare \([^{xy}_{22}]\) , as represented in Figure 5; the remaining eight yellow squares have similar properties to those to be described, once the notations of local vertices and neighboring tercubes are updated in each case in place of those in the figure. Besides the “external” 4-cycle \((00,01,11,10)\) in Figure 5, whose edges are in black color, we set in red and blue, (green and hazel) colors those additional edges defining a pair of 4-cycles in the respective tercubes \([^{xxy}_{202}]\) and \([^{xxy}_{212}]\), (\([^{xyy}_{220}]\) and \([^{xyy}_{221}]\)), namely \(\{(00,02,12,10),(01,02,12,11)\}\), (\(\{(00,20,21,01),(10,20,21,11)\}\)), equally denoted but pertaining to different tersquares, as shown.
Since it is seen that the maximum truncated distance in Figure 5 is 2, we conclude that any one of the four vertices of the black 4-cycle dominates the remaining vertices in the other 4-cycles in the figure, in positions in their tersquares similar to those of the yellow cycles in Figure 4, namely the four just mentioned tersquares as well as the “opposite” tersquares \([^{xxyy}_{2020}]\),\([^{xxyy}_{2021}]\), \([^{xxyy}_{2120}]\) and \([^{xxyy}_{2121}]\), where these involved tersquare denominations are set in Figure 5 straddling edges common to two of their 4-cycles, for better reference, twice for the last four mentioned tersquares. This particular case is easily generalized to conclude that each vertex in a yellow square dominates via \(\rho\) in the neighboring tersquares in a form similar to that of \([[\emptyset]]\).
With the same structure as the 2-hive \([[\emptyset]]\), we have the 2-hives of its neighboring 2-hive pair \(\{[[^{xxx}_{010}]], [[^{xxx}_{012}]]\}\), etc., sharing four tersquares with \([[\emptyset]]\), tersquares denoted \((10,11,12)\) , both in \([^{x}_{0}]\) and in \([^{xy}_{00}]\) and \([^{xy}_{01}]\) and \([^{xy}_{02}]\). These four tersquares belong both in \([[^{xxx}_{010}]]\) and \([[^{xxx}_{012}]]\) to the four respective tercubes \([^{xx}_{01}]\), \([^{xxy}_{010}]\), \([^{xxy}_{011}]\) and \([^{xxy}_{012}]\). Moreover, the union of these four tercubes constitutes the intersection \([[^{xxx}_{010}]]\cap[[^{xxx}_{012}]]\). By considering in each of these two 2-hives the equivalent of the yellow squares of \([[\emptyset]]\) in Figure 4, and selecting in each such yellow square a vertex contributing to the construction of an isolated 2-PTMC of \(\Gamma_2\),, iteration of such a procedure eventually allows the completion of such dominating set. Observe that the argument exposed from the 2-hive pair \(\{[[^{xxx}_{010}]], [[^{xxx}_{012}]]\}\) is one of twelve cases arising from the 2-hive \([[\emptyset]]\). Iteration of these twelve cases departing from any 2-hive of \(\Gamma_2\) that is reached in the continuing procedure allows to advance a further step in the construction of such isolated 2-PTMC. ◻
Remark 3.4. The argument of Theorem 3.3 can be modified to ascertain the existence of 2-PTMC\([H]\), where \(H\) is a 4-cycle, or the union of yellow squares with a common vertex in different 2-hives, like the eight squares, in Figure 5, at vertex 10 in the tersquares \([^{xy}_{2,2}]\), \([^{xxy}_{202}]\). \([^{xxy}_{212}]\), \([^{xyy}_{220}]\), \([^{xyy}_{221}]\), \([^{xxyy}_{2020}]\), \(^{xxyy}_{2021}]\) and \([^{xxyy}_{2120}]\).
Conjecture 3.5. There exists an isolated \(n\)-PTMC in \(\Gamma_n\), \(\forall n>2\).
Question 3.6. Does there exist a suitable way of declaring a susbset \(S\subset V(\Gamma_n)\) to be periodic, or periodic-like, that extends the notion of periodicity of \(\Lambda_n\) at the end of Remark 1.7 to one in \(\Gamma_n\)? so that a replacement of the notion of “quotient” or “toroidal” graphs of \(\Lambda_n\) can be found that way for \(\Gamma_n\)?
On the left of Figure 6, an oriented representation of a ternary square is provided. Here, one may take the vertices as decision conditional diamonds, the outgoing arrows as “Yes” or “True” option arrows and the incoming arrows as “No” or “False” option arrows. An elementary flowchart modeled on this oriented ternary square is given as an example on the right of Figure 6, where the root of the flowchart corresponds to vertex 00 and there are four terminators, corresponding to the vertices 01, 02, 11 and 12. The decision conditional diamonds correspond to the vertices 00, 10, 20, 21 and 22. To avoid terminators that are the end of more than one process, as is the case of 11 and 12 in the figure, one may select in \(\Gamma_2\) modeling flowchart continuation in adjacent tercubes to the immediately previous ones, each sharing with the current tercube an already used triangle.
