Seminár z teórie grafov - Gyorgy Kiss (19.5.2016)

vo štvrtok 19.5.2016 o 9:50 hod. v miestnosti M/213

---

Prednášajúci: Gyorgy Kiss, Eotvos Lorand University (ELTE), Budapest

Názov: Resolving sets in finite geometries

Termín: 19.5.2016, 9:50 hod., M/213

Abstrakt:
A 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 metric dimension of a graph G is the smallest size of a resolving set for G. The resolving sets are interesting objects 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. Heger and M. Takats. 

---