Resolving sets for higher dimensional projective spaces (Q1994933)

In this paper, the authors continue the study the metric dimension of certain incidence graphs, started in [\textit{T. Héger} et al., Australas. J. Comb. 78, Part 3, 352--375 (2020; Zbl 1453.05027); \textit{T. Héger} and \textit{M. Takáts}, Electron. J. Comb. 19, No. 4, Research Paper P30, 21 p. (2012; Zbl 1266.05020)]. Let \(\Gamma(n,q)\) denote incidence graph of points and hyperplanes in \(\mathrm{PG}(n,q)\). The \textit{metric dimension} of a graph is the size of the smallest \textit{resolving set} in it. A \textit{resolving set} for a graph \(\Gamma\) is a set \(S\) of vertices such that for any two vertices \(x,y\) in \(\Gamma\), there is a vertex \(s\in S\) such \(d(x,s)\neq d(y,s)\). It is known from [Héger et al., loc. cit.; Héger and Takáts, loc. cit.] that the metric dimension of the projective plane is \(4q-4\). Generalising this result, the authors first show that if \(q\) is large enough, then the size of a resolving set of \(\Gamma(n,q)\) is at least \[2nq-2\frac{n^{n-1}}{(n-1)!}.\] This bound is not believed to be sharp for \(n>2\). The main part of the paper is devoted to constructing resolving sets for \(n>2\). The authors first show that one can construct a resolving set of \(\Gamma(n,q)\) of size \(2kq\) from a set of \(k\) lines in \(\mathrm{PG}(n,q)\) in so-called \textit{higgledy-piggledy} arrangement (a term introduced in [\textit{T. Héger} et al., Des. Codes Cryptography 76, No. 2, 207--216 (2015; Zbl 1329.68091)]). The main lemma then proceeds to show that if \(q\) is large enough, there exist a set of \(6\) lines in \(\mathrm{PG}(4,q)\) in higgledy-piggledy arrangement. This is done by associating an algebraic surface to general coordinates of such lines, and reducing the problem of being in higgledy-piggledy arrangement to the problem of finding enough rational points on a curve. The existence of these rational points then follows from applying the Hasse-Weil bound. It follows from the authors' main lemma that the graph \(\Gamma(4,q)\) has a resolving set of size \(12q\). Finally, the authors use an induction argument to show that \(\Gamma(n,q)\) has a resolving set of size \((n^2+n-8)q\).