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
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
No more topics!
a