My research focused on answering what the typical metric dimension of a network is by probabilistic methods. Networks are structures constructed of points connected by lines. We formally refer these points and lines as “vertices” and “edges” respectively. Networks throughout the years have proven themselves to be incredibly useful at modelling computer networks and flow structures. But what does it mean to determine the dimension of a structure like networks? We certainly have an understanding of what it means for geometric objects, such as triangles and spheres, to have a dimension, so let’s begin there.
Imagining a line, we can assign a single number to each point on the line. The most intuitive way to do this is simply to label the points in the same way we would the number line giving each point a unique number. However, geometric shapes like planes and discs require points to be labelled by a two-number coordinate system while cubes and other 3-dimensional shapes require a three-number coordinate system.
We extend this same idea to networks. Say we consider some arbitrary vertex of a connected network as a “locating” vertex. From this, we can assign each vertex a number based on how many steps along edges it is away from this locating vertex. Multiple locating vertices mean that each vertex is assigned an n-number coordinate where n is the number of locating vertices. The “metric dimension” of a network then is simply the minimum number of locating vertices required to give each vertex a unique coordinate.
In general, finding the metric dimension of a network is not easy and so we elected to only study 3-regular networks (networks where each vertex has exactly three edges) with the hope that this would give us an advantage in determining the metric dimension of a network. Likewise, by using probabilistic methods, we hope to determine a bound on the metric dimension of a network that we might not have otherwise been able to obtain.
My research is based on studying sets called Si which are defined relative to some arbitrary vertex v of the network. These sets are defined as the set of vertices that have distance i from v. For example, S3 is the set of vertices that have distance 3 from v. These Si groups tend to grow bigger as we explore further from v. We can do the same for two arbitrary vertices u and v of the network and again, explore their Si sets. Eventually, the Si groups from each vertex must intersect to form a set we call C, which is simply all the vertices that are the same distance from u and v. The key idea is realising that any locating vertex in C would be unable to distinguished u and v since they must be the same distance away. Hence, my research is focused on trying to estimate how big this C set is in order to estimate the metric dimension.
Will Veenman
Monash University
