The time is now - Spring classes are filling up!

MIT PRIMES/Art of Problem Solving

CROWDMATH 2020: Metric Dimension

G
Topic
First Poster
Last Poster
Improvement of corollaries from ressource 4
antoinelab01   35
N Aug 19, 2020 by JGeneson
In Jesse's paper (ressource 4), the following corollaries are stated, as consequences of the pattern avoidance results.
1) The number of edges of a graph on $n$ vertices with metric dimension $k$ is at most $\frac{(3^k-1)n}{2}$
2) The maximum possible chromatic number of a graph of metric dimension $\le k$ is between $2^k$ and $3^k$
3) The maximum possible degeneracy of a graph of metric dimension $\le k$ is between $2^{k-1}$ and $3^k-1$

I can show that the bound for 1) is (asymptotically) tight when $n$ is large with respect to $k$, I can close the range for 2) and narrow it for 3).

For 1), consider the graph $G_k(N,M)$ defined as follow:
The vertices are the points $(x_1,\cdots,x_k)$ of $\mathbb{Z}^k$ in the hypercube defined by the inequalities $|x_i-N|\le x_j$ for all $i\ne j$ and $\sum_{i=1}^k x_i \le M$ (the last inequality ensuring it is finite) and there is an edge between two points if and only if they differ by at most $1$ in each coordinate.

This graph has metric dimension $k$: if we let $v_i$ be the point with $i$'th coordinate $0$ and all others $m$, then the distance vector of each point $x$ with respect to the set of landmarks consisting of the $v_i$'s is exactly $x$.

Moreover, if we take $N$ and $M$ large, most points have the maximal degree $3^k-1$. Indeed, if all the stronger inequalities $|x_i-m|\le x_j-2$ and $\sum_{i=1}^k x_i \le M-k$ holds, then all the $3^k-1$ possible neighbours of $x$ satisfy the inequalities necessary for being in the graph (let's call such points interior vertices). It is clear that, by taking $M$ and $N$ sufficiently large, the proportion of vertices that are interior can get arbitrarily close to $1$and there are then at least $\frac{rn(3^k-1)}{2}$ edges (since the number of edges is the sum of the degrees over $2$). This show that the maximal number of edges $e_k(n)$ in a graph on $n$ vertices with metric dimension $k$ satisifies $e_k(n)\sim \frac{n(3^k-1)}{2}$ as $n \to \infty$.


For 2), we can show that the maximal chromatic number is exactly $2^k$. We already know that it is at least $2^k$. For the upper bound, note that we can assign a color to each point of $(\mathbb{Z}/2\mathbb{Z})^k$ and color each vertex with the color corresponding to its distance vector modulo $2$. This gives a valid coloring of the graph, since if two vertices are adjacent their distance vectors differ by at most $1$ in each coordinate.

For 3), the maximal degeneracy is at most $\frac{3^k-1}{2}$. Indeed, suppose that $G$ has metric dimension $k$ and let $D_k$ be the graph on $\mathbb{Z}_{\ge 0}^k$ where we have edges between points that differ by at most one in each coordinate. We can embed $G$ as a subgraph of $D_k$ by sending each point to its distance vector. However, $D_k$ has degeneracy at most $\frac{3^k-1}{2}$: for any subgraph $H$ of $D_k$, the minimal point of $H$ with respect to the lexicographical order has degree at most $\frac{3^k-1}{2}$ (in $H$). Thus $G$ also has degeneracy at most $\frac{3^k-1}{2}$.
I think that we can prove that $\frac{3^k-1}{2}$ is also a lower bound, which would completely close the range. For this, we only need to construct a subgraph of $D_k$ such that each vertex has degree at most $\frac{3^k-1}{2}$. This graph will probably have the form of the integer points in a convex polytope, and then the lower degrees will be reached at the vertices. Thus, we only need to construct a polytope such that, in some sense, each vertex in not too sharp (almost flat actually in order to reach $\frac{3^k-1}{2}$ neighbors). For $k=2$ we can take the octagon with vertices $(0,1),(0,2),(1,3),(2,3),(3,2),(3,1),(2,0),(2,1)$, but, for now, I'm not sure how it generalizes to higher dimensions. Any ideas for this?

By the way, it seems like thinking of graphs of metric dimension $k$ as embedded in $D_k$ is a very useful technique and give a strong intuition. It is also what allowed me to find the example of graphs with metric dimension $2$ and large edge metric dimension in another topic. Maybe it can still be useful for other problems about metric dimension (it doesn't work so well for edim though...).
35 replies
antoinelab01
Aug 6, 2020
JGeneson
Aug 19, 2020
No more topics!
a