Resolving sets for higher dimensional projective spaces

DOI10.1016/J.FFA.2020.101723MaRDI QIDQ1994933zbMATH OpenOpenAlexFDO

Authors Daniele Bartoli, Stefano Marcugini, Fernanda Pambianco, Gy. Kiss

Publication date 18 February 2021

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL http://real.mtak.hu/126409/1/PH-resolving_FFAsubmitted.pdf

finite projective spaces point-hyperplane incidence graph resolving sets

Combinatorial aspects of finite geometries (05B25) Distance in graphs (05C12) Combinatorial structures in finite projective spaces (51E20)

Review text

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\).

Recommendations

Cites work

Cited in

(12)

Describes a project that uses

Uses Software

Magma

This page was built for publication: Resolving sets for higher dimensional projective spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994933)