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
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.
0 replies
JGeneson
Oct 25, 2020
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
nvaenushan
Oct 17, 2024
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 \(4 {k\choose 2}\) which contains a \(K_{2^k}\).

Start with a \(K_{2^k}\), and label each vertex \(v\) with a binary coordinate of length \(k\). Then for each pair \((i,j), 1 \le i < j \le k\), we construct new vertices \(u^0_{i,j}, u^1_{i,j}, u^2_{i,j}, u^3_{i,j}\) as follows.
Given some \(v = (a_1,a_2, \dots, a_k)\):
- \(vu^0_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 0.\)
- \(vu^1_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 1.\)
- \(vu^2_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 0.\)
- \(vu^3_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 1.\)
Then we claim that the set of all \(u\)'s is an edge metric basis for \(G\).

Let \(S\) be the set of new vertices and supposed that \(d_{e,S} = d_{f,S}\) for edges \(e,f \in E(G)\). If \(e\) is adjacent to some new vertex, then \(f\) must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of \(e\) be \((a_1, \dots, a_k)\), and the other endpoint of \(f\) be \((c_1, \dots, c_k)\). For each pair \((i,j)\), \(e\) and \(f\) are distance 1 from exactly one of the \(u_{i,j}\)'s, meaning \(a_i = c_i\) and \(a_j = c_j\) for all pairs \(i,j\). Thus, \(e = f\).

If \(e,f\) are not adjacent to some new vertex, then write
\(e = (a_1, \dots ,a_k)(b_1, \dots, b_k), f = (c_1, \dots ,c_k)(d_1, \dots, d_k)\).

Lemma: For each pair \((i,j)\), if the pairs \((a_i, a_j)\) and \((b_i, b_j)\) are not identical, then \(e\) must be adjacent to two of the \(u_{i,j}\)'s. Then \(f\) must also be adjacent to the same ones, so we have either \((a_i, a_j) = (c_i, c_j)\) and \((b_i, b_j) = (d_i, d_j)\), or the other way around: \((a_i, a_j) = (d_i, d_j)\) and \((b_i, b_j) = (c_i, c_j).\)

For \(e\) to be an edge, there must be some coordinate \(x\) where \(a_x \neq b_x\). By applying the lemma on \((a_1, a_x)\) and \((b_1, b_x)\), either \(a_x = c_x\) or \(a_x = d_x\). WLOG let \(a_x = c_x\) and \(b_x = d_x\). Then, for each \(i \neq x\), we can apply the lemma on \((a_i, a_x)\) and \((b_i, b_x)\). Since \(a_x \neq d_x\), we must have \((a_i, a_x) = (c_i, c_x)\), and in particular, \(a_i = c_i\). Similarly, \((b_i, b_x) = (d_i, d_x)\), so \(b_i = d_i\).
Thus, \((a_1, \dots, a_k) = (c_1, \dots, c_k)\) and \((b_1, \dots, b_k) = (d_1, \dots, d_k)\), meaning \(e = f\).

This construction means that a graph with edim \(k\) can at a minimum contain a \(K_n\) with \(n\) on the order of \(2^{\sqrt{k}}\).
Note: I think the \(u^3_{i.j}\) vertices might not be necessary?
7 replies
ChocolateMangoes
Feb 2, 2020
checkmate2021
Dec 3, 2023
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.
3 replies
CrowdMath
Jan 3, 2020
uptownmath
Jul 2, 2021
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 $n \geq d^{d-1}$, then $dim(P_n^d)=d$. It is known that for all $d,n$ we have $dim(P_n^d) \leq d$ by forming the obvious coordinate system and choosing landmarks at $(0,0,0,....0),(1,0,0,....0),(0,1,0,.....0),(0,0,0,....,1,0)$ gives a metric basis of size $d$. Now we can note that $dim(P_n^d)$ has $n^d$ vertices and it's diameter is $(n-1)d$. By using PHP as is done in Paper $3$, we note that if the $dim(P_n^d)=k$ then $k+((n-1)d)^k$ is the maximum possible number of vertices. Thus $k+((n-1)d)^k \geq n^d$. So if $dim(P_n^d)$ is less than $d$, it is atmost $d-1$, thus $(d-1)+((n-1)d)^{d-1} \geq n^d$. But if $n>d^{d-1}$ then we can see that $(n-1)d<n^\frac{d}{d-1}$ and the $+(d-1)$ is negligible, so we get $LHS<RHS$ while we need $LHS \geq RHS$, contradiction. Thus if $n \geq d^{d-1}$, we have $dim(P_n^d)=d$. Also, we can apply a similar logic to the inequality to get that for general $n,d$ we have $dim(P_n^d) \geq \frac{d \ln{n}}{\ln{(n-1)}+\ln{d}}$.
7 replies
Mathotsav
Jul 25, 2020
JacobGallager1
May 17, 2021
complete bipartite extremal problems for edge metric dimension
JGeneson   1
N Oct 25, 2020 by JGeneson
Claim: the maximum $n$ for which $G$ contains $K_{n,n}$ over all graph $G$ of edge metric dimension at most $2k$ is $2^k$.

Anyone see a proof or counterexample?

Anyone see what the answer should be if we replace $2k$ with $2k+1$?
1 reply
JGeneson
Oct 25, 2020
JGeneson
Oct 25, 2020
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
4 replies
Aser
Oct 10, 2020
JGeneson
Oct 25, 2020
Is the program still alive?
Aser   3
N Oct 23, 2020 by JGeneson
Can I start from now it?
3 replies
Aser
Aug 23, 2020
JGeneson
Oct 23, 2020
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! : )
1 reply
MathPotato222
Sep 30, 2020
JGeneson
Oct 3, 2020
big dim/edim open problem
JGeneson   13
N Aug 27, 2020 by Mathotsav
We solved problem 2, showing there exists a family of graphs $G$ with $edim(G) = \omega(2^{dim(G)})$. The family we found has $edim(G) = (1-o(1)) 3^{dim(G)}$.

I think this is the most interesting remaining open problem about $dim$ and $edim$:

Does there exist a constant $c$ such that $edim(G) < c^{dim(G)}$ for all graphs $G$?
13 replies
JGeneson
Jul 27, 2020
Mathotsav
Aug 27, 2020
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
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 \(4 {k\choose 2}\) which contains a \(K_{2^k}\).

Start with a \(K_{2^k}\), and label each vertex \(v\) with a binary coordinate of length \(k\). Then for each pair \((i,j), 1 \le i < j \le k\), we construct new vertices \(u^0_{i,j}, u^1_{i,j}, u^2_{i,j}, u^3_{i,j}\) as follows.
Given some \(v = (a_1,a_2, \dots, a_k)\):
- \(vu^0_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 0.\)
- \(vu^1_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 1.\)
- \(vu^2_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 0.\)
- \(vu^3_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 1.\)
Then we claim that the set of all \(u\)'s is an edge metric basis for \(G\).

Let \(S\) be the set of new vertices and supposed that \(d_{e,S} = d_{f,S}\) for edges \(e,f \in E(G)\). If \(e\) is adjacent to some new vertex, then \(f\) must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of \(e\) be \((a_1, \dots, a_k)\), and the other endpoint of \(f\) be \((c_1, \dots, c_k)\). For each pair \((i,j)\), \(e\) and \(f\) are distance 1 from exactly one of the \(u_{i,j}\)'s, meaning \(a_i = c_i\) and \(a_j = c_j\) for all pairs \(i,j\). Thus, \(e = f\).

If \(e,f\) are not adjacent to some new vertex, then write
\(e = (a_1, \dots ,a_k)(b_1, \dots, b_k), f = (c_1, \dots ,c_k)(d_1, \dots, d_k)\).

Lemma: For each pair \((i,j)\), if the pairs \((a_i, a_j)\) and \((b_i, b_j)\) are not identical, then \(e\) must be adjacent to two of the \(u_{i,j}\)'s. Then \(f\) must also be adjacent to the same ones, so we have either \((a_i, a_j) = (c_i, c_j)\) and \((b_i, b_j) = (d_i, d_j)\), or the other way around: \((a_i, a_j) = (d_i, d_j)\) and \((b_i, b_j) = (c_i, c_j).\)

For \(e\) to be an edge, there must be some coordinate \(x\) where \(a_x \neq b_x\). By applying the lemma on \((a_1, a_x)\) and \((b_1, b_x)\), either \(a_x = c_x\) or \(a_x = d_x\). WLOG let \(a_x = c_x\) and \(b_x = d_x\). Then, for each \(i \neq x\), we can apply the lemma on \((a_i, a_x)\) and \((b_i, b_x)\). Since \(a_x \neq d_x\), we must have \((a_i, a_x) = (c_i, c_x)\), and in particular, \(a_i = c_i\). Similarly, \((b_i, b_x) = (d_i, d_x)\), so \(b_i = d_i\).
Thus, \((a_1, \dots, a_k) = (c_1, \dots, c_k)\) and \((b_1, \dots, b_k) = (d_1, \dots, d_k)\), meaning \(e = f\).

This construction means that a graph with edim \(k\) can at a minimum contain a \(K_n\) with \(n\) on the order of \(2^{\sqrt{k}}\).
Note: I think the \(u^3_{i.j}\) vertices might not be necessary?
7 replies
ChocolateMangoes
Feb 2, 2020
checkmate2021
Dec 3, 2023
Maximum K_n in Bounded edim Graph
G H J
G H BBookmark kLocked kLocked NReply
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ChocolateMangoes
10 posts
#1 • 1 Y
Y by Adventure10
Here is a construction for a graph with metric dimension \(4 {k\choose 2}\) which contains a \(K_{2^k}\).

Start with a \(K_{2^k}\), and label each vertex \(v\) with a binary coordinate of length \(k\). Then for each pair \((i,j), 1 \le i < j \le k\), we construct new vertices \(u^0_{i,j}, u^1_{i,j}, u^2_{i,j}, u^3_{i,j}\) as follows.
Given some \(v = (a_1,a_2, \dots, a_k)\):
- \(vu^0_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 0.\)
- \(vu^1_{i,j}\) is an edge if \(a_i = 0\) and \(a_j = 1.\)
- \(vu^2_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 0.\)
- \(vu^3_{i,j}\) is an edge if \(a_i = 1\) and \(a_j = 1.\)
Then we claim that the set of all \(u\)'s is an edge metric basis for \(G\).

Let \(S\) be the set of new vertices and supposed that \(d_{e,S} = d_{f,S}\) for edges \(e,f \in E(G)\). If \(e\) is adjacent to some new vertex, then \(f\) must be adjacent to the same vertex, and we consider their other endpoints. Let the other endpoint of \(e\) be \((a_1, \dots, a_k)\), and the other endpoint of \(f\) be \((c_1, \dots, c_k)\). For each pair \((i,j)\), \(e\) and \(f\) are distance 1 from exactly one of the \(u_{i,j}\)'s, meaning \(a_i = c_i\) and \(a_j = c_j\) for all pairs \(i,j\). Thus, \(e = f\).

If \(e,f\) are not adjacent to some new vertex, then write
\(e = (a_1, \dots ,a_k)(b_1, \dots, b_k), f = (c_1, \dots ,c_k)(d_1, \dots, d_k)\).

Lemma: For each pair \((i,j)\), if the pairs \((a_i, a_j)\) and \((b_i, b_j)\) are not identical, then \(e\) must be adjacent to two of the \(u_{i,j}\)'s. Then \(f\) must also be adjacent to the same ones, so we have either \((a_i, a_j) = (c_i, c_j)\) and \((b_i, b_j) = (d_i, d_j)\), or the other way around: \((a_i, a_j) = (d_i, d_j)\) and \((b_i, b_j) = (c_i, c_j).\)

For \(e\) to be an edge, there must be some coordinate \(x\) where \(a_x \neq b_x\). By applying the lemma on \((a_1, a_x)\) and \((b_1, b_x)\), either \(a_x = c_x\) or \(a_x = d_x\). WLOG let \(a_x = c_x\) and \(b_x = d_x\). Then, for each \(i \neq x\), we can apply the lemma on \((a_i, a_x)\) and \((b_i, b_x)\). Since \(a_x \neq d_x\), we must have \((a_i, a_x) = (c_i, c_x)\), and in particular, \(a_i = c_i\). Similarly, \((b_i, b_x) = (d_i, d_x)\), so \(b_i = d_i\).
Thus, \((a_1, \dots, a_k) = (c_1, \dots, c_k)\) and \((b_1, \dots, b_k) = (d_1, \dots, d_k)\), meaning \(e = f\).

This construction means that a graph with edim \(k\) can at a minimum contain a \(K_n\) with \(n\) on the order of \(2^{\sqrt{k}}\).
Note: I think the \(u^3_{i.j}\) vertices might not be necessary?
This post has been edited 1 time. Last edited by ChocolateMangoes, Feb 6, 2020, 5:51 AM
Z K Y
G
H
=
a