אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A set of vertices S resolves a graph if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph is the minimum cardinality of a resolving set of the graph. Fix a connected graph G on q ≥ 2 vertices, and let M be the distance matrix of G. We prove that if there exists w ∈ Z q such that \sum_i w_i =0 and the vector Mw, after sorting its coordinates, is an arithmetic progression with nonzero common difference, then the metric dimension of the Cartesian product of n copies of G is (2+o(1))n/ log_q(n). In the special case that G is a complete graph, our results close the gap between the lower bound attributed to Erd˝os and R´enyi and the upper bound by Chv´atal. The main tool is the M¨obius function of a certain partially ordered set on N.