MIT PRIMES/Art of Problem Solving
CROWDMATH 2020: Metric Dimension
No tags match your search
Mdegeneracy
Metric dimension
pattern avoidance
Edge metric dimension
landmarks
edim2
linear algebra
matrix
graph theory
Binary tree
d-grid
hypercube
landmarks - pn
triples
wheels
3D geometry
analytic geometry
Bipartite
Chromatic number
connected
counting
degeneracy
dgrid
edim2 - maxedim
edimkn
geometry
landmarks - cn
landmarks - falsedim
landmarks - grid
mdapa
mdapa - kn
number of edges
Problem4
stars
subgraphs
vector
No tags match your search
MG
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 vertices with metric dimension is at most
2) The maximum possible chromatic number of a graph of metric dimension is between and
3) The maximum possible degeneracy of a graph of metric dimension is between and
I can show that the bound for 1) is (asymptotically) tight when is large with respect to , I can close the range for 2) and narrow it for 3).
For 1), consider the graph defined as follow:
The vertices are the points of in the hypercube defined by the inequalities for all and (the last inequality ensuring it is finite) and there is an edge between two points if and only if they differ by at most in each coordinate.
This graph has metric dimension : if we let be the point with 'th coordinate and all others , then the distance vector of each point with respect to the set of landmarks consisting of the 's is exactly .
Moreover, if we take and large, most points have the maximal degree . Indeed, if all the stronger inequalities and holds, then all the possible neighbours of satisfy the inequalities necessary for being in the graph (let's call such points interior vertices). It is clear that, by taking and sufficiently large, the proportion of vertices that are interior can get arbitrarily close to and there are then at least edges (since the number of edges is the sum of the degrees over ). This show that the maximal number of edges in a graph on vertices with metric dimension satisifies as .
For 2), we can show that the maximal chromatic number is exactly . We already know that it is at least . For the upper bound, note that we can assign a color to each point of and color each vertex with the color corresponding to its distance vector modulo . This gives a valid coloring of the graph, since if two vertices are adjacent their distance vectors differ by at most in each coordinate.
For 3), the maximal degeneracy is at most . Indeed, suppose that has metric dimension and let be the graph on where we have edges between points that differ by at most one in each coordinate. We can embed as a subgraph of by sending each point to its distance vector. However, has degeneracy at most : for any subgraph of , the minimal point of with respect to the lexicographical order has degree at most (in ). Thus also has degeneracy at most .
I think that we can prove that is also a lower bound, which would completely close the range. For this, we only need to construct a subgraph of such that each vertex has degree at most . 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 neighbors). For we can take the octagon with vertices , 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 as embedded in 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 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...).
1) The number of edges of a graph on vertices with metric dimension is at most
2) The maximum possible chromatic number of a graph of metric dimension is between and
3) The maximum possible degeneracy of a graph of metric dimension is between and
I can show that the bound for 1) is (asymptotically) tight when is large with respect to , I can close the range for 2) and narrow it for 3).
For 1), consider the graph defined as follow:
The vertices are the points of in the hypercube defined by the inequalities for all and (the last inequality ensuring it is finite) and there is an edge between two points if and only if they differ by at most in each coordinate.
This graph has metric dimension : if we let be the point with 'th coordinate and all others , then the distance vector of each point with respect to the set of landmarks consisting of the 's is exactly .
Moreover, if we take and large, most points have the maximal degree . Indeed, if all the stronger inequalities and holds, then all the possible neighbours of satisfy the inequalities necessary for being in the graph (let's call such points interior vertices). It is clear that, by taking and sufficiently large, the proportion of vertices that are interior can get arbitrarily close to and there are then at least edges (since the number of edges is the sum of the degrees over ). This show that the maximal number of edges in a graph on vertices with metric dimension satisifies as .
For 2), we can show that the maximal chromatic number is exactly . We already know that it is at least . For the upper bound, note that we can assign a color to each point of and color each vertex with the color corresponding to its distance vector modulo . This gives a valid coloring of the graph, since if two vertices are adjacent their distance vectors differ by at most in each coordinate.
For 3), the maximal degeneracy is at most . Indeed, suppose that has metric dimension and let be the graph on where we have edges between points that differ by at most one in each coordinate. We can embed as a subgraph of by sending each point to its distance vector. However, has degeneracy at most : for any subgraph of , the minimal point of with respect to the lexicographical order has degree at most (in ). Thus also has degeneracy at most .
I think that we can prove that is also a lower bound, which would completely close the range. For this, we only need to construct a subgraph of such that each vertex has degree at most . 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 neighbors). For we can take the octagon with vertices , 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 as embedded in 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 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
No more topics!