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