MIT PRIMES/Art of Problem Solving
CROWDMATH 2020: Metric Dimension
No tags match your search
MMetric 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
i first crowdmath 2020 paper
JGeneson 0
Oct 25, 2020
https://arxiv.org/abs/2008.13302
We will write a second crowdmath 2020 paper later, and we will include all contributors to the results in the second paper as authors, like the first paper.
We will write a second crowdmath 2020 paper later, and we will include all contributors to the results in the second paper as authors, like the first paper.
0 replies
I need help!
nvaenushan 0
Oct 17, 2024
"What is the maximum value of n for which a graph of edge metric dimension at most k can contain the complete graph K_n as a subgraph?" So guys. i need help with the steps? Anyone have hints. I don't know how to approach this.
0 replies
Maximum K_n in Bounded edim Graph
ChocolateMangoes 7
N
Dec 3, 2023
by checkmate2021
Here is a construction for a graph with metric dimension which contains a .
Start with a , and label each vertex with a binary coordinate of length . Then for each pair , we construct new vertices as follows.
Given some :
- is an edge if and
- is an edge if and
- is an edge if and
- is an edge if and
Then we claim that the set of all 's is an edge metric basis for .
Let be the set of new vertices and supposed that for edges . If is adjacent to some new vertex, then must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of be , and the other endpoint of be . For each pair , and are distance 1 from exactly one of the 's, meaning and for all pairs . Thus, .
If are not adjacent to some new vertex, then write
.
Lemma: For each pair , if the pairs and are not identical, then must be adjacent to two of the 's. Then must also be adjacent to the same ones, so we have either and , or the other way around: and
For to be an edge, there must be some coordinate where . By applying the lemma on and , either or . WLOG let and . Then, for each , we can apply the lemma on and . Since , we must have , and in particular, . Similarly, , so .
Thus, and , meaning .
This construction means that a graph with edim can at a minimum contain a with on the order of .
Note: I think the vertices might not be necessary?
Start with a , and label each vertex with a binary coordinate of length . Then for each pair , we construct new vertices as follows.
Given some :
- is an edge if and
- is an edge if and
- is an edge if and
- is an edge if and
Then we claim that the set of all 's is an edge metric basis for .
Let be the set of new vertices and supposed that for edges . If is adjacent to some new vertex, then must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of be , and the other endpoint of be . For each pair , and are distance 1 from exactly one of the 's, meaning and for all pairs . Thus, .
If are not adjacent to some new vertex, then write
.
Lemma: For each pair , if the pairs and are not identical, then must be adjacent to two of the 's. Then must also be adjacent to the same ones, so we have either and , or the other way around: and
For to be an edge, there must be some coordinate where . By applying the lemma on and , either or . WLOG let and . Then, for each , we can apply the lemma on and . Since , we must have , and in particular, . Similarly, , so .
Thus, and , meaning .
This construction means that a graph with edim can at a minimum contain a with on the order of .
Note: I think the vertices might not be necessary?
7 replies
Welcome to CrowdMath
CrowdMath 3
N
Jul 2, 2021
by uptownmath
CrowdMath is an open project that gives all high school students the opportunity to collaborate on a large research project with top-tier research mentors and an exceptional peer group. MIT PRIMES and Art of Problem Solving are working together to create a place for students to experience research mathematics and discover ideas that did not exist before.
Below we've tried to unpack and explain the things you will find on the CrowdMath page:
Resources and Problems
The problems in the CrowdMath project are open, unsolved problems in mathematics. We will be discovering new truths that were unknown before. The problems will become available in early 2020. Until then, we expect participants to be studying the readings in our Resources section of the CrowdMath page.
The Resources for this project are background ideas that you will need to understand and make progress on the CrowdMath problems. We've chosen resources that are directly relevant to the project: the problems are defined explicitly in terms of ideas that you will find in our resources. All of the problems we will pose are thematically linked and all of the resources we post will be as well. We will be releasing the resources roughly in the order that you should be reading them.
Each resource also has exercises to help clarify the key ideas and give practice with them. You can discuss the exercises by clicking either the "View Discussions" or "Start New Topic" button.
Eligibility
CrowdMath is designed to give very well-prepared high school and college students (as of 1/1/20) experience with math research. Very advanced middle school students are also welcome to participate. We know that the problems will be interesting to a broader range of people, but we want to create a specific opportunity for the upcoming generation of math and science researchers.
Be polite and constructive
This rule is simple, but important. The goal here is to learn to collaborate. Be nice!
Make your comments as easy to understand as possible
Polymath is a conversation. Assume that many people will be reading anything you write. Take a little time to make sure you write as clearly as possible and all of your collaborators will appreciate it.
Dissemination of results and intellectual property
Polymath projects are inherently massively collaborative. Done correctly, it should be impossible to determine the lines between one person's work and the rest of the group. As such, we agree that the results created must be attributed to all CrowdMath contributors.
Below we've tried to unpack and explain the things you will find on the CrowdMath page:
Resources and Problems
The problems in the CrowdMath project are open, unsolved problems in mathematics. We will be discovering new truths that were unknown before. The problems will become available in early 2020. Until then, we expect participants to be studying the readings in our Resources section of the CrowdMath page.
The Resources for this project are background ideas that you will need to understand and make progress on the CrowdMath problems. We've chosen resources that are directly relevant to the project: the problems are defined explicitly in terms of ideas that you will find in our resources. All of the problems we will pose are thematically linked and all of the resources we post will be as well. We will be releasing the resources roughly in the order that you should be reading them.
Each resource also has exercises to help clarify the key ideas and give practice with them. You can discuss the exercises by clicking either the "View Discussions" or "Start New Topic" button.
Eligibility
CrowdMath is designed to give very well-prepared high school and college students (as of 1/1/20) experience with math research. Very advanced middle school students are also welcome to participate. We know that the problems will be interesting to a broader range of people, but we want to create a specific opportunity for the upcoming generation of math and science researchers.
Be polite and constructive
This rule is simple, but important. The goal here is to learn to collaborate. Be nice!
Make your comments as easy to understand as possible
Polymath is a conversation. Assume that many people will be reading anything you write. Take a little time to make sure you write as clearly as possible and all of your collaborators will appreciate it.
Dissemination of results and intellectual property
Polymath projects are inherently massively collaborative. Done correctly, it should be impossible to determine the lines between one person's work and the rest of the group. As such, we agree that the results created must be attributed to all CrowdMath contributors.
3 replies
Dim of P_n^d grid when n is large with respect to d
Mathotsav 7
N
May 17, 2021
by JacobGallager1
We will show that if , then . It is known that for all we have by forming the obvious coordinate system and choosing landmarks at gives a metric basis of size . Now we can note that has vertices and it's diameter is . By using PHP as is done in Paper , we note that if the then is the maximum possible number of vertices. Thus . So if is less than , it is atmost , thus . But if then we can see that and the is negligible, so we get while we need , contradiction. Thus if , we have . Also, we can apply a similar logic to the inequality to get that for general we have .
7 replies
complete bipartite extremal problems for edge metric dimension
JGeneson 1
N
Oct 25, 2020
by JGeneson
Claim: the maximum for which contains over all graph of edge metric dimension at most is .
Anyone see a proof or counterexample?
Anyone see what the answer should be if we replace with ?
Anyone see a proof or counterexample?
Anyone see what the answer should be if we replace with ?
1 reply
Fan graph (3,2)
Aser 4
N
Oct 25, 2020
by JGeneson
In this research paper, https://mp.feri.um.si/osebne/peterin/clanki/edimproduct5.pdf
Theorem 1: For any non trivial graphs G and H,
edim(G ∨ H) = { |V (G)| + |V (H)| − 1, if G ∈ G or H ∈ G,
|V (G)| + |V (H)| − 2, if G, H /∈ G.
As a corollary based on this theorem, a complete bipartite graph G2,2 has edim (G) = 2, and any multipartite graph G(,ri,r2,...rn) with k larger than 2 will have edim(G) = ∑(ri-1) with i = [1,n]. This implies that the tripartite G(1,1,3) will have edim(G)=2, and this tripartite graph is also a fan graph (3,2). The rules for fan graphs in resource 3 are only for fan graphs (1,n), so I am not sure of my undertaking.
P.S. Because I can't write mathematical notations here, I would prefer you read it from the original research paper. The theorem is in page 3 and the corollary is in page 4
Theorem 1: For any non trivial graphs G and H,
edim(G ∨ H) = { |V (G)| + |V (H)| − 1, if G ∈ G or H ∈ G,
|V (G)| + |V (H)| − 2, if G, H /∈ G.
As a corollary based on this theorem, a complete bipartite graph G2,2 has edim (G) = 2, and any multipartite graph G(,ri,r2,...rn) with k larger than 2 will have edim(G) = ∑(ri-1) with i = [1,n]. This implies that the tripartite G(1,1,3) will have edim(G)=2, and this tripartite graph is also a fan graph (3,2). The rules for fan graphs in resource 3 are only for fan graphs (1,n), so I am not sure of my undertaking.
P.S. Because I can't write mathematical notations here, I would prefer you read it from the original research paper. The theorem is in page 3 and the corollary is in page 4
4 replies
No edges?
MathPotato222 1
N
Oct 3, 2020
by JGeneson
Hi, I'm new to CrowdMath but find this really cool!
Is this problem the graphs with no edges?
No edges means if there are 2 vertices with no landmarks, they both have distance infinity to all others, so there can only be one vertex with no landmark.
This can be constructed with n vertices, n-1 of them have a landmark.
Case 1:
The robot's distance to some landmark is 0, so it knows where it is.
Case 2:
The robot's distance to every landmark is infinity, so it must be on the one node without a landmark.
Is this correct? I know this must be one of the simpler problems but during this pandemic I've really been missing my college problem solving group and I'd love to join this! : )
Is this problem the graphs with no edges?
No edges means if there are 2 vertices with no landmarks, they both have distance infinity to all others, so there can only be one vertex with no landmark.
This can be constructed with n vertices, n-1 of them have a landmark.
Case 1:
The robot's distance to some landmark is 0, so it knows where it is.
Case 2:
The robot's distance to every landmark is infinity, so it must be on the one node without a landmark.
Is this correct? I know this must be one of the simpler problems but during this pandemic I've really been missing my college problem solving group and I'd love to join this! : )
1 reply
big dim/edim open problem
JGeneson 13
N
Aug 27, 2020
by Mathotsav
We solved problem 2, showing there exists a family of graphs with . The family we found has .
I think this is the most interesting remaining open problem about and :
Does there exist a constant such that for all graphs ?
I think this is the most interesting remaining open problem about and :
Does there exist a constant such that for all graphs ?
13 replies
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 edges?
MathPotato222 1
N
Oct 3, 2020
by JGeneson
Hi, I'm new to CrowdMath but find this really cool!
Is this problem the graphs with no edges?
No edges means if there are 2 vertices with no landmarks, they both have distance infinity to all others, so there can only be one vertex with no landmark.
This can be constructed with n vertices, n-1 of them have a landmark.
Case 1:
The robot's distance to some landmark is 0, so it knows where it is.
Case 2:
The robot's distance to every landmark is infinity, so it must be on the one node without a landmark.
Is this correct? I know this must be one of the simpler problems but during this pandemic I've really been missing my college problem solving group and I'd love to join this! : )
Is this problem the graphs with no edges?
No edges means if there are 2 vertices with no landmarks, they both have distance infinity to all others, so there can only be one vertex with no landmark.
This can be constructed with n vertices, n-1 of them have a landmark.
Case 1:
The robot's distance to some landmark is 0, so it knows where it is.
Case 2:
The robot's distance to every landmark is infinity, so it must be on the one node without a landmark.
Is this correct? I know this must be one of the simpler problems but during this pandemic I've really been missing my college problem solving group and I'd love to join this! : )
1 reply