# Explicit, small resolving sets for Hamming graphs

Definition. Let $$G = (V;E)$$ be a finite, undirected graph. $$R = \{r_1, \ldots, r_k \} \subseteq V$$. $$R$$ resolves $$G$$ if $$V \to [0, \infty]^k, v \mapsto (d_G(v,r_1), \ldots, d_G(v, r_k))$$ is injective (where $$d_G$$ is the graph metric associated to $$G$$).

The metric dimension of $$G$$ is the cardinality of the smallest resolving $$R \subseteq V$$.

Definition. Let $$d,q \in \mathbb N$$. The Hamming graph $$H(d,q)$$ is the graph with vertex set $$\{1, \ldots, q\}^d$$ in which two vertices $$u = (u_1, \ldots, u_d), v = (v_1, \ldots, v_d)$$ are adjacent iff they differ in a single spot, i.e. $$| \{ i \mid v_i \neq u_i \} | = 1$$.

It is known that the metric dimension of $$H(d,q)$$ is $$\frac{(2 + o(1)) \cdot d}{\log_q(d)}$$ (1).

I'm interested in explicit (2) resolving sets for Hamming graphs in the region of $$d \sim 1000$$ that come reasonably close (3) to their dimension metrics.

Unfortunately, since this lies outside of my area of expertise and I wasn't able to come up with an answer in the literature, I don't know whether this is even remotely possible.

(1) Since I'm unfamiliar with some of the notation in the published literature, I'm not 100% sure about this.

(2) as in computable with current day technology -- ideally already known and publicly available

(3) i.e. significantly smaller than $$d$$ as $$\{ (\delta_{i,j})_{i = 1, \ldots, d} \mid j = 1, \ldots, d \}$$ is a trivial resolving set of size $$d$$

• Please give a link to a paper from the literature in the CS setting. Also why does the range of $V$ include $\infty$? – kodlu May 25 '19 at 23:02
• Is choosing a random set with appropriate size considered as "explict"? – LeechLattice May 26 '19 at 4:47
• @Bullet51 Any resolving set of small size that you can make available to me (so that I can actually use it in an algorithm) counts as 'explicit'. – Stefan Mesken May 26 '19 at 9:24
• @kodlu $\infty$ is included since the graph may not be connected. And one relevant paper is chapter 6 of ON THE METRIC DIMENSION OFCARTESIAN PRODUCTS OF GRAPHS. – Stefan Mesken May 26 '19 at 9:28