An improved lower bound for (1,<=2)-identifying codes in the king grid

Florent Foucaud, Tero Laihonen, Aline Parreau

This paper provides a tighter mathematical limit on the efficiency of sensor placement in a king grid to uniquely locate up to two objects. By employing a sophisticated combinatorial technique known as the discharging method, the authors establish a new lower bound for the density of (1, ≤ 2)-identifying codes.

The Problem: Identifying Codes in King Grids

The study of identifying codes models fault diagnosis and object location in networks. In a grid of sensors, each sensor can "see" its own location and all adjacent locations. When an object appears, all sensors capable of seeing it trigger an alarm. An identifying code is a set of sensor locations such that the unique combination of triggered alarms identifies the exact location of up to $\ell$ objects.

This research specifically focuses on the king grid—a square grid where each vertex is connected to its eight immediate neighbors—and the case where up to two objects ($\ell \le 2$) must be identified simultaneously. The primary goal is to determine the minimum density: the smallest fraction of grid squares required to host sensors while maintaining unique identification.

Methodology: The Discharging Method

To improve the lower bound, the authors use the discharging method, a technique famously used in the proof of the Four Color Theorem. This method analyzes the local structure of the grid to derive global density requirements.

  1. Frames: The authors define a "frame" as a $3 \times 3$ set of vertices. Any valid identifying code must satisfy specific structural conditions within these frames.
A 3x3 frame in the king grid used for the discharging analysis.
  1. Initial Charge: Each frame in the infinite grid is assigned an initial "charge" based on the number of sensors (codewords) it contains.
  2. Discharging Rules: Complex rules are established to redistribute charge from "rich" frames (those with many sensors) to "poor" frames (those with few).
  3. Local Configuration Analysis: By categorizing frames based on their sensor counts and neighborhood structures, the authors prove that after redistribution, every frame maintains a minimum charge.
A specific sensor configuration (C1) within a frame, illustrating the local constraints analyzed during discharging.

Key Results and Insights

The core contribution of this work is the refinement of the lower bound for sensor density.

  • New Lower Bound: The authors prove that the optimal density $d$ for a $(1, \le 2)$-identifying code in the king grid satisfies: $$d \ge \frac{47}{111} \approx 0.4234$$
  • Narrowed Gap: Previously, the known lower bound was $5/12 \approx 0.4166$, while the best known construction had a density of $3/7 \approx 0.4286$. This new result significantly narrows the gap, showing that the $3/7$ construction is remarkably close to optimal.
  • Cascading Constraints: The analysis reveals that local requirements for identifying two objects create global constraints. A lack of sensors in one area must be compensated for by higher density in surrounding areas, or the code fails to maintain its identifying properties.

Conclusion and Future Work

While this paper provides a much tighter bound, a small gap remains between the theoretical floor ($47/111$) and the best known ceiling ($3/7$). The complexity of the discharging method used here—involving 18 lemmas—suggests that further improvements would require even more intricate case-by-case analysis. Future research may extend these techniques to larger neighborhoods or higher numbers of simultaneous objects ($\ell \le 3$), though each grid type requires a custom-tailored discharging scheme.

Summary updated

Abstract

We call a subset $C$ of vertices of a graph $G$ a $(1,\leq \ell)$-identifying code if for all subsets $X$ of vertices with size at most $\ell$, the sets $\{c\in C |\exists u \in X, d(u,c)\leq 1\}$ are distinct. The concept of identifying codes was introduced in 1998 by Karpovsky, Chakrabarty and Levitin. Identifying codes have been studied in various grids. In particular, it has been shown that there exists a $(1,\leq 2)$-identifying code in the king grid with density 3/7 and that there are no such identifying codes with density smaller than 5/12. Using a suitable frame and a discharging procedure, we improve the lower bound by showing that any $(1,\leq 2)$-identifying code of the king grid has density at least 47/111.
BibTeX
@inproceedings{foucaud2014improved,
  author = {Florent Foucaud and Tero Laihonen and Aline Parreau},
  title = {{An improved lower bound for (1,<=2)-identifying codes in the king grid}},
  booktitle = {Adv. Math. Commun},
  year = {2014},
  url = {https://openreview.net/forum?id=EWhpCNqQi0},
}
Figure