Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije
SI | EN
natisni

Kiss György, UP & Eötvös Loránd University, Hungary

Title: Resolving sets in finite geometries

Abstract:

A \emph{resolving set} for a graph is a collection of its vertices such that all vertices are uniquely determined by their distances to the chosen vertices. The \emph{metric dimension} of a graph $G$ is the smallest size of a resolving set for $G.$ The resolving sets are interestingobjects in their own right, but their study is also motivated by the straightforward inequality stating that the metric dimension of a graph gives an upper bound on the base size of its automorphism group.
In the talk we consider resolving sets for the incidence graphs of various symmetric designs, in particular projective, affine and biaffine planes and generalized quadrangles. We give lower estimates on their metric dimensions and construct several different resolving sets. The estimates come from nontrivial double counting arguments and from deep theorems about the sizes of double blocking sets, while the constructions are based on the geometric properties of the designs.
This is a joint work with D. Bartoli, T. H\'eger and M. Tak\'ats.