Identifying codes of Archimedean grids

Introduction

Let $G=(V,E)$ be a graph and let $N[v]$ denote the closed neighborhood of a vertex $v$. A set $C \subseteq V$ is an identifying code (idcode for short) of $G$ if the sets $I(v)=N[v] \cap C$ are nonempty and pairwise distinct for $v \in V$. Identifying codes were introduced by Karpovsky, Chakrabarty and Levitin [14], motivated by fault diagnosis in multiprocessor networks, and have been studied extensively since; see the survey [13] and the references therein.

For infinite grids, the relevant parameter is the minimum density of an identifying code. Among the three regular planar grids, it is known exactly for the triangular grid [14] (equal to $1/4$), and for the square grid [2, 4] (equal to $7/20$). The hexagonal grid is a well-known open case: the best known lower bound is $5/12$ [9] (see also [6, 8, 19]) and the best known upper bound is $53/126$ [15]. The minimum density is also known for the king grid, where it equals $2/9$ [3, 5], and grids with finitely many rows were studied in [10, 11, 17].

The triangular, square and hexagonal grids are the three regular members of the family of the eleven Archimedean grids, the graphs of the edge-to-edge tilings of the plane by regular polygons whose symmetry group acts transitively on the vertices (§ 2). Domination-type parameters of the Archimedean grids have been studied, for instance perfect domination in [20].

However, to the best of our knowledge, among the eight non-regular Archimedean grids the only one for which identifying codes have been considered is the snub hexagonal grid $3^{4}.6$: an undergraduate thesis [1] proved that its minimum density lies between $3/10$ and $1/3$. Thus the minimum density of an identifying code was known for only two of the eleven Archimedean grids.

In this paper we start a systematic study of identifying codes of the Archimedean grids: we determine the minimum density for five of the nine remaining ones, and we give bounds for the other three.

In each case, the upper bound is given by an explicit periodic code, and the lower bound is proved by the discharging method, in the framework for infinite graphs with the slow growth property developed in [17]. The lower bounds have very different levels of difficulty. For the kagome grid, the general lower bound $2/(\Delta+ 2)$ of [17] (which comes from the simplest discharging rule, the share argument) already gives the exact value. For the truncated hexagonal grid, the general bound is only $2/5$, but the value $2/3$ follows from a very simple discharging rule, which also gives the lower bound $2/3$ for every cubic graph in which every vertex lies on exactly one triangle. For the truncated square grid, the proof is a short case analysis, which also gives the lower bound $3/7$ for every cubic graph in which every vertex lies on exactly one 4-cycle. For the elongated triangular grid, the case analysis is longer, but still done by hand. Finally, for the snub hexagonal grid, the discharging rules and the case analysis were found and checked with the help of a computer, and the case analysis is given in full as a certificate whose rows can be checked by hand. A program that checks the certificate of § 7 is available at [16].

The paper is organized as follows. In § 2 we recall the Archimedean grids, the notion of density and the discharging method for infinite graphs. Theorem 1 is the union of Theorems 3, 5, 7, 8, 9 and 10, which are stated and proved in Sections 3, 4, 5, 6, 7 and 8, respectively. For the three grids of Section 8, the upper bounds come from the best periodic codes we found with a computer search. Table 1 summarizes what is known about the eleven Archimedean grids.

Configuration	Name	$\Delta$	Minimum density
$3^{6}$	triangular	6	1/4 [14]
$4^{4}$	square	4	7/20 [4, 2]
$6^{3}$	hexagonal	3	5/12 [9] to 53/126 [15]
3.6.3.6	trihexagonal (kagome)	4	1/3 (Thm. 3)
3.12.12	truncated hexagonal	3	2/3 (Thm. 5)
4.8.8	truncated square	3	3/7 (Thm. 7)
$3^{3}.4^{2}$	elongated triangular	5	1/3 (Thm. 8)
$3^{4}.6$	snub hexagonal	5	1/3 (Thm. 9)
4.6.12	truncated trihexagonal	3	3/7 (Thm. 6) to 13/30 (Thm. 10)
3.4.6.4	rhombitrihexagonal	4	1/3 [17] to 11/30 (Thm. 10)
$3^{2}.4.3.4$	snub square	5	2/7 [17] to 9/28 (Thm. 10)

Preliminaries

A tiling of the plane by polygons is edge-to-edge if any two tiles are disjoint or meet in a common vertex or a common edge. An Archimedean tiling is an edge-to-edge tiling of the plane by regular polygons whose symmetry group acts transitively on its vertices. In such a tiling, the cyclic sequence of the numbers of sides of the polygons around a vertex, its vertex configuration, is the same at every vertex up to rotation and reflection; it is written as a sequence separated by dots, with exponents denoting repetition, so that 4.8.8 means a square and two octagons and $3^{3}.4^{2}=3.3.3.4.4$ means three triangles followed by two squares. There are exactly eleven Archimedean tilings [12 Section 2.1], including the three regular tilings by triangles, squares and hexagons. The Archimedean grid of an Archimedean tiling is the infinite graph formed by its vertices and edges. It is planar, vertex-transitive, and $\Delta$-regular, where $\Delta$ is the number of polygons around a vertex. The eleven Archimedean grids are listed in Table 1 and shown in Figure 1, together with what is known about the minimum density of their idcodes.

All Archimedean tilings except the elongated triangular tiling $3^{3}.4^{2}$ can be obtained from the regular tilings by Wythoff’s construction [7], which uses five operations: truncation, rectification, cantellation, omnitruncation and the snub operation. Truncation gives 3.12.12 and 4.8.8, rectification gives 3.6.3.6, cantellation gives 3.4.6.4, omnitruncation gives 4.6.12 and 4.8.8, and the snub operation gives $3^{4}.6$ and $3^{2}.4.3.4$.

Truncation, in particular, can be defined for every graph: the truncation $\operatorname{tr}(H)$ of a graph $H$ is obtained by replacing every vertex $v$ of degree $d$ by a cycle of length $d$, each vertex of which receives one of the edges of $v$; when $H$ is a plane graph, the edges are taken in the cyclic order around $v$. Thus $\operatorname{tr}(H)$ is cubic, and every vertex of $\operatorname{tr}(H)$ lies on exactly one of these new cycles. For instance, 3.12.12 = $\operatorname{tr}(6^{3})$, 4.8.8 = $\operatorname{tr}(4^{4})$ and 4.6.12 = $\operatorname{tr}(3.6.3.6)$.

We define the density of a set of vertices of an infinite graph as in [17]. For a vertex $w$, let $N_{r}[w]$ be the set of vertices at distance at most $r$ from $w$. The density of $C \subseteq V$ is $\mathrm{d}(C)=\inf_{w} \mathrm{d}_{w}(C)$, where $\mathrm{d}_{w}(C)=\limsup_{r\to\infty}|C\cap N_{r}[w]|/|N_{r}[w]|$. In an arbitrary infinite graph this definition must be handled with care. For instance, Slater [18] stated in 2002 that every locating-dominating set of a countably infinite $d$-regular graph has density at least $2/(d+3)$. As shown in [17], this is false for the infinite 3-regular tree, which has a locatingdominating set of density at most $5/16 < 1/3$; in this tree, the value $d_w(C)$ may moreover depend on the vertex $w$. The property that makes density arguments valid is the following one.

A connected graph has the slow growth property [17] if it has a vertex $s$ such that

If this holds for one vertex $s$, then $\lim_{r\to\infty}|N_{r+t}[w]|/|N_r[w]|=1$ for every vertex $w$ and every integer $t$, and $d_w(C)=d_s(C)$ for every vertex $w$, so that the density of $C$ may be computed from an arbitrary vertex [17]. Since $|N_r[w]|$ grows quadratically in $r$ in every Archimedean grid, all of them have the slow growth property.

A graph admits an idcode if and only if it is twin-free, that is, $N[u]\ne N[v]$ for all distinct vertices $u,v$. It is easy to check that the eleven Archimedean grids are twin-free: two adjacent vertices have at most two common neighbors, and at most one in the cubic grids. The minimum density of an idcode of a twin-free graph $G$ is the infimum of $d(C)$ over all idcodes $C$ of $G$; for the five grids whose minimum density we determine, it is attained by periodic codes.

All our lower bounds are proved by the discharging method, which we explain now. In a charging phase, a charge, which is a rational number, is assigned to every vertex; in a discharging phase, charge is moved between vertices according to discharging rules, which preserve the total charge. The rules are designed so that, at the end, every vertex has charge at least some value $q$. In a finite graph, if every codeword starts with charge $1$ and all other vertices with charge $0$, this immediately gives $|C|\ge q|V|$. In an infinite graph, the total charge is infinite and one has to argue on balls $N_r[w]$, whose boundary may receive charge from outside or send charge outside. The slow growth property is exactly what makes the contribution of the boundary negligible, provided that charge only travels a bounded distance. This is the content of the following theorem.

no vertex sends charge to a vertex at distance greater than $d$, for a fixed integer $d$. If at the end every vertex $v$ has final charge $\operatorname{chg}(v)$ with $q \le\operatorname{chg}(v) \le q'$, where $q$ and $q'$ are rational numbers, then $q \le d(C) \le q'.$

In our proofs, codewords may start with a charge larger than 1, which only multiplies all charges by a constant, and charge only moves between vertices at distance at most 2, so the final charges are bounded. The general lower bound $2/(\Delta+2)$ for twin-free infinite graphs with the slow growth property and maximum degree $\Delta$, mentioned in the introduction, is proved in [17 Theorem 4.1] using Theorem 2 with the most basic discharging rule, often called the share argument in the literature: every vertex $v$ receives $1/|I(v)|$ from each codeword of $I(v)$. A codeword $c$ then gives 1 to at most one vertex of $N[c]$, namely the vertex $v$ with $I(v)=\{c\}$ if it exists, and at most $1/2$ to each other vertex of $N[c]$, hence at most $1+\Delta/2$ in total.

The trihexagonal grid

The trihexagonal tiling, whose vertices all have configuration $3.6.3.6$, is the Archimedean grid also known as the kagome grid. It is 4-regular, so the general lower bound of [17] gives $2/(4+2)=1/3$. We show that this bound is attained, which proves item (a) of Theorem 1.

Note that the trihexagonal grid is an induced subgraph of the triangular grid. Its edges lie on three families of parallel straight lines, and every vertex lies on exactly two of these lines, which belong to different families. In Figure 2, these families are formed by the horizontal lines and by the lines making angles of $60^\circ$ and $-60^\circ$ with them. We call the lines of the first family horizontal, and the vertices lying on no horizontal line middle vertices, since each of them lies between two consecutive horizontal lines. Two adjacent vertices in a horizontal line are called consecutive. Every vertex of a horizontal line has two (consecutive) neighbors on this line and two middle neighbors, one above and one below the line. Every middle vertex is adjacent to two consecutive vertices of the horizontal line just below it and to two consecutive vertices of the horizontal line just above it. Since every middle vertex has four neighbors on horizontal lines and every vertex of a horizontal line has two middle neighbors, $2/3$ of the vertices lie on horizontal lines.

Proof. The trihexagonal grid is 4-regular, twin-free, and has the slow growth property, so every idcode has density at least $2/(4+2)=1/3$ by [17 Theorem 4.1]. Conversely, let $C$ be a set of vertices containing no middle vertex and such that codewords and non-codewords alternate along each horizontal line, as in Figure 2. If $v \in C$, then $I(v)=\{v\}$. If $v \notin C$ lies on a horizontal line, then $I(v)$ consists of the two neighbors of $v$ on this line, and $v$ is their only common neighbor, since a middle vertex is adjacent only to consecutive vertices of a line. If $v$ is a middle vertex, then $I(v)$ consists of one codeword on the horizontal line just below $v$ and one on the line just above $v$, and again $v$ is their only common neighbor. Hence the sets $I(v)$ are nonempty and pairwise distinct, and $C$ is an idcode. Its density is $1/3$, since $C$ contains half of the vertices of the horizontal lines, which are $2/3$ of all vertices. $\square$

The general bound is tight here, in contrast with the other grids treated in this paper. In the codes of the proof of Theorem 3, every codeword $c$ has $I(c)=\{c\}$ and every vertex $v \notin C$ has $|I(v)|=2$, so every codeword gives exactly $1+4/2=3$ in the share argument. Since the choice of the parity class on each horizontal line is free, there are uncountably many idcodes of density $1/3$. Note also that the code of Figure 2 is not an idcode of the triangular grid (which has an extra vertex at the center of every hexagon of Figure 2): every such center has the same set $I$ as one of its middle neighbors.

The truncated hexagonal grid

The truncated hexagonal tiling has vertex configuration $3.12.12$ (see Figure 3). It is the truncation $\operatorname{tr}(6^3)$: every vertex of the hexagonal grid is replaced by a triangle. The grid is cubic, so the general lower bound is only $2/5$. In this section we prove that the minimum density is $2/3$, which is item (b) of Theorem 1.

We first prove a general lower bound for every cubic graph in which every vertex lies on exactly one triangle, such as the truncation of any cubic graph. In such a graph, every vertex $v$ lies on exactly one triangle $T(v)$ and has exactly one neighbor outside it, its bridge neighbor $\beta(v)$, and $\beta(\beta(v))=v$. The bridge neighbors of the three vertices of a triangle are distinct, since a common bridge neighbor would form a second triangle. Such a graph is twin-free, since $N[u]=N[v]$ for distinct vertices $u,v$ would put $u$ on two triangles.

Proof. Let $C$ be an idcode, and let $T=\{u,v,w\}$ be a triangle. Since $N[u]\mathbin{\triangle}N[v]$ is the set $\{\beta(u),\beta(v)\}$, the code $C$ contains $\beta(u)$ or $\beta(v)$, and similarly for the pairs $u,w$ and $v,w$. Hence at least two of $\beta(u),\beta(v),\beta(w)$ are codewords. Every codeword starts with charge 1 and all other vertices with charge 0, and every codeword $c$ sends $1/3$ to each vertex of the triangle $T(\beta(c))$, which is at distance at most 2 from $c$. Every vertex $v$ then receives $1/3$ for every codeword among the bridge neighbors of the vertices of $T(v)$, hence at least $2/3$, and Theorem 2 gives $d(C)\ge2/3$.

For example, Theorem 4 applies to the truncation $\operatorname{tr}(4.8.8)$, a non-Archimedean cubic grid in which every vertex lies on exactly one triangle and has configuration $3.8.16$ or $3.16.16$. We now turn to the truncated hexagonal grid $3.12.12$. We draw the grid so that one third of the edges $\beta(v)$ are vertical (see Figure 3). Then every triangle has one vertex $z$ with $z\beta(z)$ vertical, one vertex $x$ with $\beta(x)$ to its left and one vertex $y$ with $\beta(y)$ to its right. We call $x$ the exit of the triangle.

Proof. The truncated hexagonal grid is cubic, and every vertex lies on exactly one triangle, so Theorem 4 gives the lower bound. Conversely, let $C$ be the set of all vertices that are not exits, as in Figure 3. Every triangle contains exactly one exit, so $C$ has density $2/3$. Let $T = \{x,y,z\}$ be a triangle, named as above. Then $x$ is the exit of $T$ and $\beta(y)$ is the exit of the triangle to the right of $T$, while $\beta(x)$ and $\beta(z)$ are not exits. Hence

These sets are nonempty and pairwise distinct, since $\beta(x) \ne\beta(z)$. Every set $I(v)$ contains two vertices of $T(v)$, and the only vertices adjacent to two vertices of a triangle $T$ are the vertices of $T$, since the bridge neighbors of the vertices of $T$ are distinct. Hence $I(v)$ determines $T(v)$, and therefore $v$, and $C$ is an idcode.

The bound $2/3$ is much larger than the general bound $2/5$: the triangles force many codewords, and the argument above only uses the separation of adjacent vertices.

The truncated square grid

The truncated square tiling has vertex configuration $4.8.8$ (see Figure 4). It is the truncation $\operatorname{tr}(4^4)$: every vertex of the square grid is replaced by a 4-cycle. The grid is cubic, so the general lower bound is only 2/5. In this section we prove that the minimum density is 3/7, which is item (c) of Theorem 1.

We first prove a general lower bound for every twin-free cubic graph in which every vertex lies on exactly one 4-cycle, such as the truncation of any 4-regular graph; in Section 8 we also apply it to the truncated trihexagonal grid 4.6.12 = tr(3.6.3.6). In such a graph, the square of a vertex $v$ is the 4-cycle containing it. A square has no chord, since a chord $v_1v_3$ of a square $v_1, v_2, v_3, v_4$ would give $N[v_1] = N[v_3]$. Thus the two neighbors of $v$ on its square are its square neighbors, and the third neighbor of $v$ is its bridge neighbor $\beta(v)$. The edge $v\beta(v)$ lies on no 4-cycle, and $\beta(\beta(v)) = v$. If $v_1, v_2, v_3, v_4$ is a square in cyclic order, then the square neighbors of $v_1$ and $v_3$ are $v_2$ and $v_4$, and vice versa.

Proof. Let $G$ be such a graph and let $C$ be an idcode of $G$. Every codeword starts with charge 7 and all other vertices with charge 0. For a vertex $v$, let $S(v)$ be the set of square neighbors of $v$ that belong to $C$. In the discharging phase, each codeword $u$ sends charge to its neighbors according to the following rules.

(R1) If $b = \beta(u) \notin C$, the codeword $u$ sends charge 3 or 2 to $b$, depending on whether $S(b) = \varnothing$ or not.

(R2) Let $s$ be a square neighbor of $u$, and let $\ell= |S(s)| \ge1$. If $s \notin C$, then $u$ sends $1/\ell$ or $3/\ell$ to $s$, depending on whether $\beta(s) \in C$ or not. If $s \in C$ and $\beta(s) \notin C$, then $u$ sends $1/\ell$ to $s$.

In words, a vertex is served first by itself, then by its bridge neighbor, and its square neighbors complete what is missing in equal parts. A codeword $u$ receives nothing if $\beta(u) \in C$ or $S(u) = \varnothing$. Otherwise it receives $1/|S(u)|$ from each vertex of $S(u)$, hence 1 in total. A vertex $v \notin C$ receives exactly 3. Indeed, if $\beta(v) \in C$, it receives 3 from $\beta(v)$ when $S(v) = \varnothing$, and otherwise 2 from $\beta(v)$ and $1/|S(v)|$ from each vertex of $S(v)$, hence $2 + 1 = 3$ in total. If $\beta(v) \notin C$, it receives $3/|S(v)|$ from each vertex of $S(v)$, which is nonempty because $C$ is dominating.

It remains to show that every codeword ends with charge at least 3. Let $u \in C$, let $u, s_1, w, s_2$ be its square in cyclic order, let $b = \beta(u)$ and $b_i = \beta(s_i)$ for $i = 1, 2$. Denote by $q_b, q_1, q_2$ the charges that $u$ sends to $b, s_1, s_2$. The final charge of $u$ is $7 - q_b - q_1 - q_2 + \delta$, where $\delta= 1$ if $b \notin C$ and at least one of $s_1, s_2$ is in $C$, and $\delta= 0$ otherwise. So we must show that $q_b + q_1 + q_2 \le4 + \delta$.

By (R1), $q_b = 0$ if $b \in C$. If $b \notin C$, then $q_b = 3$ when $I(b) = \{u\}$ and $q_b = 2$ otherwise. The square neighbors of $s_i$ are $u$ and $w$. If $s_i \in C$, rule (R2) gives $q_i = 0$ when $b_i \in C$ and $q_i \le1$ in any case. If $s_i \notin C$, rule (R2) gives $q_i = 3, 3/2, 1$ or $1/2$ according to whether $I(s_i)$ is $\{u\}$, $\{u,w\}$, $\{u,b_i\}$ or $\{u,w,b_i\}$. Thus $q_i \le3$ always, $q_i \le3/2$ when $w \in C$, and $q_i \le1$ when $b_i \in C$.

Suppose first that $b \in C$, so that $\delta= q_b = 0$ and we must show $q_1 + q_2 \le4$. If some $s_i$ is a codeword, then $q_i \le1$ and $q_{3-i} \le3$. If $s_1, s_2 \notin C$ and $w \in C$, then $q_1 + q_2 \le3$. If $s_1, s_2, w \notin C$, then $I(s_i) = \{u\} \cup(\{b_i\} \cap C)$, and $I(s_1) \ne I(s_2)$ puts one of $b_1, b_2$ in $C$, so $q_1 + q_2 \le3 + 1$.

Suppose now that $b \notin C$. If $s_1, s_2 \in C$, then $\delta= 1$ and $q_b + q_1 + q_2 \le3 + 1 + 1 = 5$. If $s_1, s_2 \notin C$, then $\delta= 0$ and $I(u) = \{u\}$, so $I(b) \ne I(u)$ gives $q_b = 2$. When $w \notin C$ we have $I(s_i) = \{u\} \cup(\{b_i\} \cap C)$, and $I(s_i) \ne I(u)$ forces $b_i \in C$, so $q_1 = q_2 = 1$. When $w \in C$ we have $I(s_i) = \{u,w\} \cup(\{b_i\} \cap C)$, and $I(s_1) \ne I(s_2)$ puts one of $b_1,b_2$ in $C$, so $q_1 + q_2 \le3/2 + 1/2$. In both cases the sum is at most 4.

It remains the case where exactly one of $s_1,s_2$, say $s_1$, is a codeword. Then $\delta= 1$ and $I(u) = \{u,s_1\}$, and we must show that the sum is at most 5. If $w \in C$, then $q_1 \le1/2$ and $q_2 \le3/2$, and the sum is at most $3 + 1/2 + 3/2 = 5$. If $w \notin C$ and $b_2 \in C$, then $q_1,q_2 \le1$ and the sum is at most 5. Finally, suppose $w,b_2 \notin C$. Then $I(s_2) = \{u\}$, so $q_2 = 3$, and $I(b) \ne I(s_2)$ gives $q_b = 2$. Moreover $I(s_1) = \{u,s_1\} \cup(\{b_1\} \cap C)$, and $I(s_1) \ne I(u)$ forces $b_1 \in C$, so $q_1 = 0$ and the sum is exactly 5.

Hence every vertex ends with charge at least 3. Every codeword started with charge 7 and charge only moves between adjacent vertices, so Theorem 2 gives density at least 3/7.

For example, Theorem 6 applies to the truncation tr(3.4.6.4), a non-Archimedean cubic grid in which every vertex lies on exactly one 4-cycle and has configuration 4.6.8 or 4.8.12. We now turn to the truncated square grid 4.8.8.

Proof. The truncated square grid is twin-free and cubic, and every vertex lies on exactly one 4-cycle, so Theorem 6 gives the lower bound. Conversely, the black vertices of Figure 4 form a periodic set of density $12/28 = 3/7$. Since two vertices at distance at least 3 have disjoint closed neighborhoods, by periodicity it suffices to check that $I(u) \ne\varnothing$ and $I(u) \ne I(v)$ for every vertex $u$ of the dashed rectangle and every vertex $v$ with $d(u,v) \le2$, which is a routine verification with Figure 4.

Every codeword of the code of Figure 4 ends with charge exactly 3, so this code is perfectly balanced for the rules (R1) and (R2). Note also that the proof of Theorem 6 only uses that the four vertices of $N[u]$ are pairwise separated and that $C$ is dominating. It would be interesting to know whether rules of this kind give good bounds for the hexagonal grid, which has a structure similar to the truncated square grid.

The elongated triangular grid

The elongated triangular tiling has vertex configuration $3^3.4^2$ (see Figure 5). Its graph is 5-regular, so the general lower bound of [17] gives only 2/7. In this section we prove that the minimum density is 1/3, which is item (d) of Theorem 1.

The horizontal lines of the tiling bound alternately a row of squares and a row of triangles. We draw the grid as the square grid in which the squares of alternate rows are cut by a diagonal at 45°, so that these rows become the rows of triangles. Every edge lies on two faces, and there are three kinds of edges: the vertical edges of the rows of squares lie on two squares, the horizontal edges lie on a square and a triangle, and the other edges, in the rows of triangles, lie on two triangles. Accordingly, every vertex $v$ has exactly one neighbor joined to it by an edge lying on two squares, which we call its bridge neighbor $\beta(v)$, two outer neighbors, which are its neighbors on its row, and two inner neighbors, joined to it by edges lying on two triangles. Since the kind of an edge does not depend on the endpoint, $\beta(\beta(v))=v$, and $v$ is an outer (inner) neighbor of each of its outer (inner) neighbors. Around $v$ the faces are two squares and three triangles, so the neighbors of $v$ appear in the cyclic order $\beta(v)$, outer, inner, inner, outer, and the three triangles containing $v$ are formed by $v$ with each consecutive pair among the last four. Hence the two inner neighbors of $v$ are adjacent, each outer neighbor of $v$ is adjacent to exactly one inner neighbor of $v$, and these are the only edges among the neighbors of $v$.

Proof. It is easy to check that the two sets of Figure 5 are periodic idcodes of density 1/3. Conversely, let $C$ be an idcode. Every codeword starts with charge 3 and all other vertices with charge 0. In the discharging phase every vertex $v \notin C$ receives exactly 1 in total from the codewords of $I(v)$, and every codeword receives 1/2 or nothing, according to the following rules.

(R1) If $v \in C$ and $\beta(v) \notin C$, then $v$ sends 1 to $\beta(v)$. Moreover, $v$ receives $1/2$ from a codeword $x$ in the following two situations: $x$ is the unique codeword neighbor of $v$, or $x$ is the unique inner neighbor of $v$ in $C$ and the outer neighbor of $v$ adjacent to $x$ is in $C$. In all other cases, a codeword receives nothing.

(R2) If $v \notin C$, $\beta(v) \notin C$ and $|I(v)| \ge3$, then $v$ receives equal amounts (summing to 1) from the inner neighbors of $v$ in $C$ that are adjacent to an outer neighbor of $v$ in $C$, and nothing from the other codewords. Such inner neighbors exist, since $I(v)$ contains three of the four outer and inner neighbors of $v$, and any three of them contain an outer neighbor together with its adjacent inner neighbor.

(R3) If $v \notin C$, $\beta(v) \notin C$ and $|I(v)| \le2$, then $v$ receives $1/|I(v)|$ from each codeword of $I(v)$.

Every vertex outside $C$ ends with charge 1, so it suffices to show that every codeword also ends with charge at least 1. Let $u$ be a codeword, let $q$ be the total amount given by $u$ to its neighbors, and let $r \in\{0, \frac{1}{2}\}$ be the amount that $u$ receives. Then $u$ ends with charge $3-q+r$, so we must show that $q \le2+r$.

Let $b=\beta(u)$, and let $u_1,u_2,u_3,u_4$ be the other neighbors of $u$, in the cyclic order around $u$ starting after $b$. Thus the outer neighbors of $u$ are $u_1,u_4$ and its inner neighbors are $u_2,u_3$, and $u_1u_2u_3u_4$ is a path (see Figure 6). Let $P=\{u_1,u_2,u_3,u_4\}$. Also, the inner neighbors of $u_2$ are $u$ and $u_1$, and its outer neighbors are $u_3$ and a vertex $z_1$ adjacent to $u_1$; the vertex $z_1$ is the inner neighbor of $u_1$ other than $u_2$, and the outer neighbors of $u_1$ are $u$ and a vertex $u_0$. Symmetrically we define $z_4$ and $u_5$, so that $u_0,u_1,u,u_4,u_5$ are consecutive vertices of the horizontal line of $u$.

For $w \in N(u)$ we write $q_w$ for the amount that $u$ sends to $w$, so that $q=\sum_{w\in N(u)}q_w$. Every amount sent in the rules is $1/2$ or 1, since in (R2) the charge is split among at most two inner neighbors and in (R3) we have $|I(v)| \le2$. Hence $q_w \in\{0,1/2,1\}$ for every $w \in N(u)$. By (R1), we have $q_b=1$ and $r \le1/2$ if $b \notin C$, and $q_b=r=0$ if $b \in C$.

By the rules, the values $q_{u_1}$ and $q_{u_2}$ are described as follows. Symmetrically, the values $q_{u_4}$ and $q_{u_3}$ are obtained by exchanging $u_i$ with $u_{5-i}$, and $z_1$ with $z_4$.

• $q_{u_1}=1$ if and only if $I(u_1)=\{u\}$.

• $q_{u_2}=1$ if and only if $I(u_2)=\{u\}$, or $u_2,\beta(u_2)\notin C$, $u_3\in C$ and $I(u_2)$ is $\{u,u_3,u_1\}$ or $\{u,u_3,z_1\}$.

• $q_{u_1}>0$ if and only if $\beta(u_1)\notin C$ and either $u_1\in C$ and $I(u_1)=\{u_1,u\}$, or $u_1\notin C$ and $|I(u_1)|\le2$.

• $q_{u_2}>0$ if and only if $\beta(u_2)\notin C$ and either $u_2\in C$ and $(I(u_2)=\{u_2,u\}$, or $u_1\notin C$ and $u_3\in C$), or $u_2\notin C$ and $(|I(u_2)|\le2$ or $u_3\in C)$.

Indeed, if $w\in P$ is a codeword, then by (R1) we have $q_w\le1/2$, and $q_w>0$ exactly when $\beta(w)\notin C$ and either $u$ is the unique codeword neighbor of $w$, or $w=u_2$, $u_1\notin C$ and $u_3\in C$; this is because $u$ is an outer neighbor of $u_1$, while $u$ is an inner neighbor of $u_2$ and $u_3$ is the outer neighbor of $u_2$ adjacent to $u$. If $w\notin C$ and $\beta(w)\in C$, then $q_w=0$. If $w\notin C$, $\beta(w)\notin C$ and $|I(w)|\le2$, then $q_w=1/|I(w)|$ by (R3). Finally, suppose that $w\notin C$, $\beta(w)\notin C$ and $|I(w)|\ge3$, so that (R2) applies. If $w=u_1$, then $q_w=0$, since $u$ is an outer neighbor of $u_1$. If $w=u_2$, then $I(u_2)\subseteq\{u,u_1,u_3,z_1\}$, so $q_{u_2}=0$ if $u_3\notin C$, while if $u_3\in C$ the vertex $u_2$ receives from $u$, and also from $u_1$ exactly when $u_1,z_1\in C$; thus $q_{u_2}=1/2$ if $I(u_2)=\{u,u_1,u_3,z_1\}$, and $q_{u_2}=1$ otherwise.

We use two consequences of this description. First, $q_w=1$ for at most one vertex $w\in P$. Indeed, at most one vertex $v$ of $N[u]$ satisfies $I(v)=\{u\}$, since $C$ is identifying. So if $q_w=1$ for two vertices $w\in P$, one of them would be, by symmetry, $u_2$ with $u_2\notin C$, $u_3\in C$ and $I(u_2)\in\{\{u,u_3,u_1\},\{u,u_3,z_1\}\}$. The other one is neither the codeword $u_3$ nor $u_4$, whose set $I(u_4)$ contains $u_3$, so it is $u_1$ with $I(u_1)=\{u\}$. But then $u_1\notin C$ and $z_1\notin C$, as $z_1$ is adjacent to $u_1$, which contradicts the form of $I(u_2)$. Second, if $u_1,u_2\in C$, then $q_{u_1}=q_{u_2}=0$, since $u_2\in I(u_1)$ and $u_1\in I(u_2)$.

We now distinguish cases according to $b$ and to the set $C\cap P$, up to the symmetry exchanging $u_i$ with $u_{5-i}$. We must show that $\sum_{w\in P}q_w\le2+r-q_b$.

Suppose first that $b\in C$, so that $q_b=r=0$, and we must show that $\sum_{w\in P}q_w\le2$. Since $q_w=1$ for at most one $w\in P$, this holds unless $q_w>0$ for all four vertices $w\in P$ and $q_w=1$ for one of them, and we show that this is impossible. If $u_1,u_2\in C$ or $u_3,u_4\in C$, this follows from the second consequence above. If $C\cap P$ is $\{u_1,u_4\}$ or $\{u_2,u_3\}$, then no $q_w$ equals $1$: every $w\in P$ is a codeword or has a codeword neighbor in $P$, the exceptional case for $q_{u_2}=1$ requires $u_2\notin C$ and $u_3\in C$, and the one for $q_{u_3}=1$ requires $u_3\notin C$ and $u_2\in C$. Up to symmetry, the remaining sets are the following.

• $C\cap P=\varnothing$. Since $u_3\notin C$, $q_{u_2}>0$ gives $\beta(u_2)\notin C$ and $|I(u_2)|\le2$, so $I(u_2)$ is $\{u\}$ or $\{u,z_1\}$. The latter would give $z_1\in I(u_1)$, and $q_{u_1}>0$ would give $I(u_1)=\{u,z_1\}=I(u_2)$. Hence $I(u_2)=\{u\}$, and symmetrically $I(u_3)=\{u\}$, which is impossible.

• $C\cap P=\{u_1\}$. Then $q_{u_1}>0$ gives $I(u_1)=\{u_1,u\}$. Since $u_3\notin C$, $q_{u_2}>0$ gives $\beta(u_2)\notin C$ and $|I(u_2)|\le2$, so $I(u_2)=\{u,u_1\}=I(u_1)$, which is impossible.

• $C\cap P=\{u_2\}$. Then $q_{u_1}>0$ gives $|I(u_1)|\le2$, so $I(u_1)=\{u,u_2\}$. Since $u_3\notin C$, $q_{u_2}>0$ gives $I(u_2)=\{u_2,u\}=I(u_1)$, which is impossible.

• $C\cap P=\{u_1,u_3\}$. Since $u_2\notin C$, $q_{u_3}>0$ gives $I(u_3)=\{u_3,u\}$, and $q_{u_4}>0$ gives $|I(u_4)|\le2$, so $I(u_4)=\{u,u_3\}=I(u_3)$, which is impossible.

Suppose now that $b\notin C$, so that $q_b=1$ and $I(u)=\{u\}\cup(C\cap P)$, and we must show that $\sum_{w\in P}q_w\le1+r$. If $u_1,u_2\in C$, then $q_{u_1}=q_{u_2}=0$. If moreover $u_3\notin C$, then $r=1/2$ by (R1), and $q_{u_3}+q_{u_4}\le3/2$, since at most one of them equals $1$. If $u_3\in C$, then $q_{u_3}\le1/2$, and $q_{u_4}\le1/2$ since $u_3\in I(u_4)$, so the sum is at most $1$. Up to symmetry, the remaining sets are the following.

• $C \cap P = \varnothing$. Then $r = 0$ and $I(u) = \{u\}$, so no $w \in P$ satisfies $I(w) = \{u\}$, and $q_w \le1/2$ for all $w \in P$. As in the case $b \in C$, if $q_{u_1} > 0$ and $q_{u_2} > 0$, then $I(u_2) = \{u\}$, which is impossible. Hence $q_w > 0$ for at most one of $u_1,u_2$ and at most one of $u_3,u_4$, and the sum is at most 1.

• $C \cap P = \{u_1\}$. Then $r = 1/2$ by (R1), and $I(u) = \{u,u_1\}$. We have $q_{u_1} = 0$, since otherwise $I(u_1) = \{u_1,u\} = I(u)$, and $q_{u_2} = 0$, since otherwise $\beta(u_2) \notin C$ and $|I(u_2)| \le2$, which gives $I(u_2) = \{u,u_1\} = I(u)$. As at most one of $q_{u_3},q_{u_4}$ equals 1, the sum is at most $3/2$.

• $C \cap P = \{u_2\}$. Then $r = 1/2$ by (R1), and $I(u) = \{u,u_2\}$. We have $q_{u_2} = 0$, since otherwise $I(u_2) = \{u_2,u\} = I(u)$, and $q_{u_1} = 0$, since otherwise $I(u_1) = \{u,u_2\} = I(u)$. As before, the sum is at most $3/2$.

• $C \cap P = \{u_1,u_3\}$. Then $r = 0$ and $I(u) = \{u,u_1,u_3\}$. Every $q_w$ is at most $1/2$: this is clear for the codewords $u_1,u_3$ and for $u_4$, whose set $I(u_4)$ contains $u_3$, and $q_{u_2} = 1$ would give $I(u_2) = \{u,u_3,u_1\} = I(u)$. If $q_{u_1} > 0$, then $I(u_1) = \{u_1,u\}$, so $z_1 \notin C$; if moreover $q_{u_2} > 0$, then $\beta(u_2) \notin C$ and $I(u_2) = \{u,u_1,u_3\} = I(u)$, which is impossible. If $q_{u_3} > 0$ and $q_{u_4} > 0$, then $I(u_3) = \{u_3,u\} = I(u_4)$, as in the case $b \in C$. Hence the sum is at most 1.

• $C \cap P = \{u_1,u_4\}$. Then $r = 0$, and every $q_w$ is at most $1/2$. If $q_{u_1} > 0$ and $q_{u_2} > 0$, then $I(u_1) = \{u_1,u\}$, and, since $u_3 \notin C$, $I(u_2) = \{u,u_1\} = I(u_1)$, which is impossible. By symmetry, the sum is at most 1.

• $C \cap P = \{u_2,u_3\}$. Then $r = 0$ and $I(u) = \{u,u_2,u_3\}$, and every $q_w$ is at most $1/2$. If $q_{u_1} > 0$ and $q_{u_2} > 0$, then $I(u_1) = \{u,u_2\}$, so $z_1 \notin C$, and $\beta(u_2) \notin C$, so $I(u_2) = \{u_2,u,u_3\} = I(u)$, which is impossible. By symmetry, the sum is at most 1.

In all cases $q \le2 + r$.

Hence every vertex ends with charge at least 1. Every codeword started with charge 3 and charge only moves between adjacent vertices, so Theorem 2 gives $d(C) \ge1/3$.

The snub hexagonal grid

The snub hexagonal tiling is the only chiral Archimedean tiling, that is, the only one that cannot be mapped onto its mirror image by an isometry; all its vertices have configuration $3^4.6$ (see Figure 8). Its graph is 5-regular, so the general lower bound of [17] gives $2/7$. Its minimum density was previously known to lie in the interval $(3/10,1/3]$ [1]. In this section we prove that it equals $1/3$, which is item (e) of Theorem 1.

Every vertex of the snub hexagonal grid lies on exactly one hexagon, and its four other faces are triangles. Two hexagons are adjacent if an edge joins them. Every hexagon is adjacent to six others, and with this adjacency the hexagons form a triangular grid (see Figure 8).

For a vertex $v$, we list the five neighbors of $v$ counterclockwise, starting just after the hexagon of $v$, as $v_1,v_2,v_3,v_4,v_5$ (Figure 7), and we call $v_i$ the $i$-th neighbor of $v$. The following facts can be checked in Figure 7 and Figure 8. Since the symmetries of the tiling act transitively on the vertices and preserve the orientation, it suffices to check them for one vertex.

!The ball $N_2[u]$ of radius two around a vertex $u$ of the snub hexagonal grid bbox=0.34,0.11,0.66,0.35

(F1) The edges among the neighbors of $v$ are exactly $v_1v_2$, $v_2v_3$, $v_3v_4$ and $v_4v_5$.

(F2) The vertices $v_1,v_5$ lie on the hexagon of $v$, the vertices $v_3,v_4$ lie on a second hexagon, and $v_2$ lies on a third one; these three hexagons are pairwise adjacent.

(F3) The vertex $v$ is the fifth, third, second, fourth and first neighbor of $v_1,v_2,v_3,v_4,v_5$, respectively.

Proof. The upper bound is given by a code made of whole hexagons. The triangular grid formed by the hexagons has a unique proper 3-coloring, up to permutation of the colors, since the colors of one triangle determine all the others. This coloring is periodic, and each color class contains one third of the hexagons. Let $C$ be the union of the hexagons of one color class, as shown in Figure 8. Since the hexagons partition the vertex set and have six vertices each, the density of $C$ is $1/3$, and it is easy to check with Figure 8 that $C$ is an idcode.

Conversely, let $C$ be an idcode. We use a scheme similar to the one in § 6: every codeword starts with charge 3 and all other vertices with charge 0, and in the discharging phase every vertex $v \notin C$ receives exactly 1 in total from the codewords of $I(v)$, and every codeword receives $1/2$ or nothing. For a vertex $v$, let $I'(v)=I(v)\setminus\{v\}=N(v)\cap C$ be the set of codeword neighbors of $v$. The amounts received by a vertex $v$ depend only on $I(v)$ and are given by the following rules, in which the codewords of $N(v)$ are designated by their names $v_1,\ldots,v_5$ relative to $v$.

(R1) If $v\notin C$, then $v$ receives $1/|I(v)|$ from each codeword of $I(v)$, except when $I'(v)$ is one of the seventeen sets of Table 2(a); in that case $v$ receives equal amounts (summing to 1) from the codewords listed in the second column, and nothing from the other codewords of $I(v)$.

(a) $v \notin C$		(b) $v \in C$
$I'(v)$	receives from	$I'(v)$	receives $1/2$ from
$\{v_2,v_5\}$	$v_5$	$\{v_1\}$	$v_1$
$\{v_2,v_3\}$	$v_2$	$\{v_3\}$	$v_3$
$\{v_1,v_3\}$	$v_1$	$\{v_4\}$	$v_4$
$\{v_1,v_2,v_5\}$	$v_1,v_5$	$\{v_1,v_2\}$	$v_2$
$\{v_1,v_2,v_3\}$	$v_1,v_2$	$\{v_2,v_4\}$	$v_4$
$\{v_1,v_2,v_4\}$	$v_1,v_2$	$\{v_4,v_5\}$	$v_5$
$\{v_1,v_3,v_4\}$	$v_1,v_3$	$\{v_1,v_2,v_5\}$	$v_2$
$\{v_1,v_3,v_5\}$	$v_1,v_5$
$\{v_2,v_3,v_4\}$	$v_2,v_3$
$\{v_2,v_3,v_5\}$	$v_2,v_5$
$\{v_2,v_4,v_5\}$	$v_4,v_5$
$\{v_3,v_4,v_5\}$	$v_3,v_4$
$\{v_1,v_2,v_3,v_4\}$	$v_2,v_3$
$\{v_1,v_2,v_3,v_5\}$	$v_2,v_5$
$\{v_1,v_3,v_4,v_5\}$	$v_3,v_4$
$\{v_2,v_3,v_4,v_5\}$	$v_3,v_4$
$\{v_1,v_2,v_3,v_4,v_5\}$	$v_2,v_3,v_4$

(R2) If $v \in C$ and $I'(v)$ is one of the seven sets of Table 2(b), then $v$ receives $1/2$ from the codeword listed in the second column. Otherwise a codeword receives nothing.

Every vertex outside $C$ ends with charge 1, so it suffices to show that every codeword also ends with charge at least 1. Let $u$ be a codeword, let $q$ be the total amount given by $u$ to its neighbors, and let $r \in\left\{0,\frac{1}{2}\right\}$ be the amount that $u$ receives. Then $u$ ends with charge $3-q+r$, so we must show that $q \le2+r$.

For $w \in N(u)$, let $q_w$ be the amount that $u$ sends to $w$, so that $q=\sum_{w\in N(u)}q_w$. We name the vertices of $N_2[u]$ as in Figure 7: $u_1,\ldots,u_5$ are the neighbors of $u$, and $z_1,\ldots,z_9$ are the vertices at distance two. By (F3), $u$ is the fifth, third, second, fourth and first neighbor of $u_1,u_2,u_3,u_4,u_5$, respectively, and this is how $u$ appears in the rules applied by these vertices.

We first record what the rules give. Clearly $r \in\left\{0,\frac{1}{2}\right\}$. Let $w \in N(u)$. If $w \in C$, then $q_w$ is $\frac{1}{2}$ in the seven situations of Table 2(b) in which the listed codeword is $u$, and 0 otherwise. If $w \notin C$, then $q_w=1$ when $I(w)=\{u\}$, and also in the three exceptional cases with $\lvert I(w)\rvert=2$ of Table 2(a) in which $u$ is the listed codeword; in all other cases $q_w \le\frac{1}{2}$. Thus $q_w \le1$ always, and $q_w \in\left\{0,\frac{1}{2},1\right\}$ unless $\lvert I(w)\rvert\ge3$.

The value $q_w$ depends only on $N[w]\cap C$, and $N[w]\subseteq N_2[u]$. Table 3 is a case analysis. First, the cases are separated according to the set $I'(u)$ of codeword neighbors of $u$. Then, for some sets $I'(u)$, each case is subdivided according to whether some further vertices of $N_2[u]$ are in $C$. In each case, these further assumptions, together with $I'(u)$ and $u\in C$, determine whether some vertices of $N_2[u]$ are in $C$. Each row of the table gives:

• a lower bound for $r$;

• for each $w\in N(u)$, the maximum possible value of $q_w$, over all ways of deciding which vertices of $N[w]$ not determined by the row are in $C$, subject only to the following two conditions, which every idcode satisfies: $I(x)\ne\varnothing$ for every $x$ with $N[x]\subseteq N_2[u]$, and $I(x)\ne I(y)$, that is, $N[x]\mathbin{\triangle}N[y]$ contains a codeword, for all $x\in N_2[u]$ and $y\ne x$ with $N[x]\mathbin{\triangle}N[y]\subseteq N_2[u]$.

These maxima are obtained by reading Table 2 together with the observations of the previous paragraph. For instance, in the first row with $I'(u)=\varnothing$ that is not impossible, the vertex $u_2$ receives nothing from $u$: its codeword neighbors are $u$ and $z_4$, which are its third and first neighbors, so $I(u_2)=\{v_1,v_3\}$ in the names relative to $v=u_2$, and by Table 2(a) the vertex $u_2$ receives everything from $z_4$. The rows marked impossible are those in which the fixed vertices already violate one of the two conditions: for instance, if $I'(u)=\varnothing$ and $z_3,z_4\notin C$, then $I(u_2)=\{u\}=I(u)$. In all the other rows the upper bounds add up to at most 2 plus the lower bound for $r$, and the rows cover all possibilities for $I'(u)$ and the further vertices. Hence $q\leq2+r$ in all cases, and every vertex ends with charge at least 1. Every codeword started with charge 3 and charge only moves between adjacent vertices, so Theorem 2 gives $d(C)\geq1/3$.

In the code of Figure 8, every codeword has exactly its two hexagon neighbors as codeword neighbors, and the sets $I(v)$ have sizes 1, 2 and 3 in equal proportions; every codeword ends with charge exactly 1. The rules (R1) and (R2) and the case analysis of Table 3 were found and checked with the help of a computer [16], but the verification of each row only requires reading Table 2. Unlike the other grids treated here, the snub hexagonal grid does not seem to admit a short discharging argument: no rule in which every vertex simply splits its charge according to fixed priorities among the positions $v_1,\ldots,v_5$ achieves the bound $1/3$.

Table 3: Certificate for the proof of Theorem 9. The first column is $I'(u)=I(u)\setminus\{u\}$, the next two columns list further assumptions on $N_2[u]$, namely the vertices assumed to be in $C$ and those assumed not to be in $C$, the next five columns give upper bounds for $q_{u_1},\ldots,q_{u_5}$, the next one their sum, and the last one a lower bound for $r$. In every possible row, the sum is at most $2+r$.

$I'(u)$	further assumptions $\in C$	further assumptions $\notin C$	$u_1$	$u_2$	$u_3$	$u_4$	$u_5$	sum	$r$
$\varnothing$			impossible: $I(u)=I(u_2)$
	$z_4$	$z_3,z_4$	impossible: $I(u_2)=I(u_3)$
	$z_4,z_5$	$z_3,z_8,z_9$	$1$	$0$	$0$	$0$	$1$	$2$	$0$
	$z_4,z_5,z_8$	$z_3,z_9$	$1$	$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
	$z_4,z_5,z_9$	$z_3$	$1$	$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
	$z_3$	$z_4,z_5$	impossible: $I(u)=I(u_3)$
	$z_3,z_5$	$z_4,z_8,z_9$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$0$	$1$	$2$	$0$
	$z_3,z_5,z_8$	$z_4,z_9$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
	$z_3,z_5,z_9$	$z_4$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
	$z_3,z_4$	$z_8,z_9$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$0$	$1$	$2$	$0$
	$z_3,z_4,z_8$	$z_9$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
	$z_3,z_4,z_9$		$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
$u_5$		$z_3$	$1$	$1$	$0$	$0$	$0$	$2$	$0$
	$z_3$		$\frac{1}{2}$	$\frac{1}{2}$	$1$	$0$	$0$	$2$	$0$
$u_4$		$z_4,z_6$	$1$	$1$	$0$	$\frac{1}{2}$	$0$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6$	$z_4$	$1$	$1$	$0$	$0$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_4$		$1$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
$u_4,u_5$	—	—	$1$	$1$	$\frac{1}{2}$	$0$	$0$	$\frac{5}{2}$	$\frac{1}{2}$
$u_3$	—	—	$1$	$0$	$0$	$\frac{1}{2}$	$1$	$\frac{5}{2}$	$\frac{1}{2}$
$u_3,u_5$	—	—	$1$	$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
$u_3,u_4$	—	—	$1$	$0$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$2$	$0$
$u_3,u_4,u_5$	—	—	$1$	$0$	$\frac{1}{2}$	$0$	$0$	$\frac{3}{2}$	$0$
$u_2$		$z_3,z_6$	$\frac{1}{2}$	$0$	$0$	$1$	$\frac{1}{2}$	$2$	$0$
	$z_3$	$z_6$	$0$	$0$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$2$	$0$
	$z_6$	$z_3$	$\frac{1}{2}$	$0$	$0$	$\frac{1}{2}$	$1$	$2$	$0$
	$z_3,z_6$		$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$1$	$2$	$0$
$u_2,u_5$		$z_3,z_6$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$2$	$0$
	$z_6$	$z_3$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$2$	$0$
	$z_3$		$0$	$0$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
$u_2,u_4$	—	—	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
$u_2,u_4,u_5$	—	—	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$0$	$\frac{3}{2}$	$0$
$u_2,u_3$	—	—	$\frac{1}{2}$	$0$	$0$	$\frac{1}{2}$	$1$	$2$	$0$
$u_2,u_3,u_5$	—	—	$\frac{1}{2}$	$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{3}{2}$	$0$
$u_2,u_3,u_4$	—	—	$\frac{1}{2}$	$0$	$0$	$0$	$\frac{1}{2}$	$1$	$0$
$u_2,u_3,u_4,u_5$	—	—	$\frac{1}{2}$	$0$	$0$	$0$	$0$	$\frac{1}{2}$	$0$
$u_1$		$z_5,z_6,z_7$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_7$	$z_5,z_6$	$0$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6$	$z_5,z_7,z_8,z_9$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$1$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6,z_7$	$z_5,z_8,z_9$	$0$	$\frac{1}{2}$	$1$	$0$	$1$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6,z_8$	$z_5,z_9$	$0$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6,z_9$	$z_5$	$0$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_5$		$0$	$\frac{1}{2}$	$0$	$1$	$1$	$\frac{5}{2}$	$\frac{1}{2}$

The remaining grids

Together with the triangular and square grids, Theorem 1 settles seven of the eleven Archimedean grids. Besides the hexagonal grid, the problem remains open for the rhombitrihexagonal grid $3.4.6.4$, the truncated trihexagonal grid $4.6.12$ and the snub square grid $3^2.4.3.4$. For these

$I'(u)$	further assumptions $\in C$	further assumptions $\notin C$	$u_1$	$u_2$	$u_3$	$u_4$	$u_5$	sum	$r$
$u_1,u_5$		$z_6$	$0$	$\frac{1}{2}$	$1$	$\frac{1}{2}$	$0$	$2$	$0$
	$z_6$		$0$	$\frac{1}{2}$	$1$	$0$	$\frac{1}{2}$	$2$	$0$
			$0$	$\frac{1}{2}$	$1$	$1$	$\frac{1}{2}$	$2$	$0$
$u_1,u_4$	—	—	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
$u_1,u_4,u_5$	—	—	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$0$	$1$	$0$
$u_1,u_3$	—	—	$0$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$1$	$2$	$0$
$u_1,u_3,u_5$	—	—	$0$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{3}{2}$	$0$
$u_1,u_3,u_4$	—	—	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{3}{2}$	$0$
$u_1,u_3,u_4,u_5$	—	—	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$0$	$0$	$1$	$0$
$u_1,u_2$		$z_6$	$0$	$0$	$1$	$1$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
	$z_6$		$0$	$0$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$\frac{1}{2}$
			$\frac{1}{2}$	$0$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
$u_1,u_2,u_5$	—	—	$\frac{1}{2}$	$0$	$1$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{5}{2}$	$\frac{1}{2}$
$u_1,u_2,u_4$	—	—	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{2}$	$2$	$0$
$u_1,u_2,u_4,u_5$	—	—	$\frac{1}{2}$	$0$	$\frac{1}{2}$	$0$	$0$	$1$	$0$
$u_1,u_2,u_3$	—	—	$\frac{1}{2}$	$0$	$0$	$\frac{1}{2}$	$1$	$2$	$0$
$u_1,u_2,u_3,u_5$	—	—	$\frac{1}{2}$	$0$	$0$	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{3}{2}$	$0$
$u_1,u_2,u_3,u_4$	—	—	$\frac{1}{2}$	$0$	$0$	$0$	$\frac{1}{2}$	$1$	$0$
$u_1,u_2,u_3,u_4,u_5$	—	—	$\frac{1}{2}$	$0$	$0$	$0$	$0$	$\frac{1}{2}$	$0$

three grids we searched for periodic idcodes of minimum density with a constraint solver, over the period lattices with fundamental domains of up to about 100 to 150 vertices, with a time limit for each lattice. The best codes we found give the upper bounds of the following result, which is items (f)–(h) of Theorem 1.

Proof. The truncated trihexagonal grid is twin-free and cubic, and every vertex lies on exactly one 4-cycle, so Theorem 6 gives the lower bound $3/7$. The rhombitrihexagonal and snub square grids are 4-regular and 5-regular, respectively, so the general bound $2/(\Delta+2)$ of [17 Theorem 4.1] gives $1/3$ and $2/7$. The upper bounds are given by the periodic codes shown in Figure 10, Figure 9 and Figure 11, which have densities $13/30$, $11/30$ and $9/28$, respectively. Since two vertices at distance at least 3 have disjoint closed neighborhoods, by periodicity it suffices to check that $I(u) \ne\varnothing$ and $I(u) \ne I(v)$ for every vertex $u$ of a fundamental domain of the period lattice and every vertex $v$ with $d(u,v) \le2$. This is a routine verification with Figure 9, Figure 10 and Figure 11.

For the truncated trihexagonal grid, the gap is small: $3/7 \approx0.4286$ and $13/30 \approx0.4333$. For the rhombitrihexagonal and snub square grids, the lower bounds of Theorem 10 are only the general bounds of [17]. Note that the snub square grid, which is 5-regular and whose faces are triangles and squares, has idcodes of density smaller than $1/3$, in contrast with the elongated triangular and snub hexagonal grids. Our attempts suggest that discharging rules of the kind used in this paper, in which the amount that a vertex $v$ receives from each codeword depends only on $N[v]\cap C$, are unlikely to give lower bounds larger than $1/3$ for the rhombitrihexagonal grid and $3/10$ for the snub square grid, so new ideas seem to be needed for these two grids.

Acknowledgments

The author used the AI assistant Claude (Anthropic, Claude Opus 5.5) to draw the figures, and to check all proofs, including exhaustive computer verification of the local case analyses. With the help of linear and integer programming, it also suggested the discharging rules for the truncated square, elongated triangular and snub hexagonal grids; its computer searches produced some codes of this paper; and it generated the certificate of § 7 and the program that verifies it [16]. The research directions, the structure of the paper, the writing and style of the proofs and the notation are due to the author, who checked all results and takes full responsibility for the paper.