Homometric sets in trees

Let G = ( V , E ) denote a simple graph with vertex set V and edge set E . The profile of a vertex set V ′ ⊆ V denotes the multiset of pairwise distances between the vertices of V ′ . Two disjoint subsets of V are homometric if their profiles are the same. If G is a tree on n vertices, we prove that its vertex set contains a pair of disjoint homometric subsets of size at least n / 2 − 1 . Previously it was known that such a pair of size at least roughly n 1 / 3 exists. We get a better result in the case of haircomb trees, in which we are able to find a pair of disjoint homometric sets of size at least c n 2 / 3 for a constant c > 0 .