Resolving sets for higher dimensional projective spaces
type: Item
instance of: scholarly article
title: Resolving sets for higher dimensional projective spaces
zbMATH Open document ID: 1464.51008
author: Daniele Bartoli
author: Stefano Marcugini
author: Fernanda Pambianco
author: Gy. Kiss
published in: Finite Fields and their Applications
publication date: 2021-02-18T00:00:00Z
full work available at URL: PH-resolving FFAsubmitted.pdf
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)\) ha…
reviewed by: Geertrui Van de Voorde
Mathematics Subject Classification ID: 51E20
Mathematics Subject Classification ID: 05B25
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 7312704
zbMATH Keywords: point-hyperplane incidence graph
zbMATH Keywords: resolving sets
zbMATH Keywords: finite projective spaces
describes a project that uses: Magma
MaRDI profile type: Publication
OpenAlex ID: W3046141504
cites work: Base size, metric dimension and other invariants of groups and graphs
cites work: On the metric dimension of affine planes, biaffine planes and generalized quadrangles
cites work: The Magma algebra system. I: The user language
cites work: Lines in higgledy-piggledy arrangement
cites work: Search problems in vector spaces
cites work: Q5139710
cites work: Resolving sets and semi-resolving sets in finite projective planes
cites work: Extremal graph theory for metric dimension and diameter
cites work: Q4003762
cites work: Q5666716
cites work: Algebraic Function Fields and Codes
DOI: 10.1016/J.FFA.2020.101723
Recommended article: Q5139710
Recommended article: On resolving sets in the point-line incidence graph of PG(n, q)
Recommended article: On the metric dimension of affine planes, biaffine planes and generalized quadrangles
Recommended article: Resolving sets and semi-resolving sets in finite projective planes
Recommended article: Partition dimension of projective planes
Recommended article: The metric dimension for resolving several objects
Recommended article: Q4898130
Recommended article: Metric dimension of maximal outerplanar graphs
Recommended article: Q4898144
Recommended article: On the metric dimension of Grassmann graphs
description: scientific article; zbMATH DE number 7312704