A resolving set of a graph G is a subset of nodes R such that any two nodes of G is a different distance away from at least one point in R. The Metric Dimension (MD) of G is the minimum cardinality of such a set. The MD and the corresponding resolving set are shown below for some simple graphs.

The MD has been studied for several families of deterministic graphs, and recently for Erdos-Renyi random graphs. An interesting fact about the MD is that it is not a monotone graph property (i.e. adding or removing edges can both increase and decrease the MD), and it in general seams much less robust than other well-studied properties (e.g. max clique size). The goal of this project is to better understand the robustness of MD.

### Tasks

- Become familiar with the existing results on MD
- Analyse theoretically the MD of a deterministic graph (e.g. 2D grid) with small perturbations

### Required skills

- Strong foundations in probability theory and familiarity with graphs
- Enthusiasm for theoretical research problems
- Familiarity with random graphs is useful

Difficulty: hard

This is a high-risk project with high benefits. In particular, it requires a student who is able to take steps independently.

### Applying for the project

This semester project is aimed at one Master's student with strong theory background. For applying please send your relevant courses and CV to Gergely Odor.