Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 1–4
Disjoint homometric sets in graphs
Michael O. Albertson ∗
Smith College, Northampton, MA 01063, USA
Janos Pach †
City College, CUNY and Courant Institute, NYU, New York, NY 10012, USA
Michael E. Young ‡
Iowa State University, Ames, IA 50010, USA
Received 28 June 2010, accepted 24 August 2010, published online 18 October 2010
Abstract
Two subsets of vertices in a graph are called homometric if the multisets of distances
determined by them are the same. Let h(n) denote the largest number h such that any
connected graph of n vertices contains two disjoint homometric subsets of size h. It is
shown that c lognlog logn < h(n) <
n
4 , for n > 3.
Keywords: Graph distances, homometric subsets, Golumb ruler.
Math. Subj. Class.: 05C12, 05C70
1 Introduction
It has been a well known fact in crystallography for over eighty years that the x-ray diffrac-
tion picture of a crystal depends on the set of vectors between its atoms [5]. As Pauling and
Shapell found in 1930, the x-ray diffraction picture of the mineral bixbyite is consistent
with two noncongruent atomic structures [8]. This motivated an interesting mathematical
question: under what circumstances can a set be retrieved from its difference set. On the
line, a partial answer was found by Piccard [9] in 1939. She claimed to prove that if two
n-element sets of integers, S and T , determine the same set of distinct differences, then
S and T are congruent to each other. (A set that determines distinct differences is called
∗Written posthumously.
†Work completed as Neilson Visiting Professor of Smith College, 2008.
‡Work completed while a Mellon Fellow at Smith College, corresponding author.
E-mail addresses: pach@cims.nyu.edu (Janos Pach), myoung@iastate.edu (Michael E. Young)
Copyright c© 2011 DMFA Slovenije
2 Ars Math. Contemp. 4 (2011) 1–4
a Golomb ruler [6].) It came as a big surprise that Bloom [4] found a counterexample to
Piccard’s theorem. The 6-element sets
S = {0, 1, 4, 10, 12, 17} T = {0, 1, 8, 11, 13, 17}
determine the same set of differences. It is still not known whether there exist arbitrarily
large sets with this property. If we allow repetition in the difference set, all pairs of sets
with the same difference set were characterized by Rosenblatt and Seymour [10], using
algebraic techniques.
Let G = (V,E) be a simple connected graph on n vertices. The distance between a
pair of vertices u, v ∈ V (G), denoted by dist(u, v) is the length of the shortest path from
u to v in G. Let S, T ⊆ V (G). The distance list of S is the multiset of
(|S|
2
)
pairwise
distances of the vertices of S in G. We say that S and T are homometric if their distance
lists are equal.
In the special case when G = C2n, a cycle of length 2n, Lemke, Skiena, and Smith [7]
proved that every n-element subset of the vertex set is homometric to its complement. In
music theory, for n = 6, this statement had been known for a long time as the Hexachordal
Theorem. In the twelve-tone scale, any set of six notes determines the same multiset of
differences. (For a historical account, consult [3], [2].) It is also known that the above
theorem generalizes to vertex-transitive graphs [1].
Here we consider the following problem. What is the largest number h such that any
connected graph on n vertices contains two disjoint homometric subsets, each of size h?
We denote this largest number h(n). In this paper we prove an upper and lower bound for
h(n).
2 Bounds
Theorem 2.1. c lognlog logn ≤ h(n) ≤
n
4 , for n > 3.
Proof. We will prove the lower bound first. Let G be a graph on n vertices. Assume that
there exists a vertex v ∈ V (G), such that the degree of v is at least (log n)3. Let k = log n.
All logarithms are base 2 in this proof. Partition the neighbors of v into sets of size k.
Each set has a distance list composed of 1s and 2s. Therefore, there are at most
(
k
2
)
+ 1
possibilities for each of the k2 distance lists. Since
(
k
2
)
+1 < k2, at least two of the distance
lists must be the same. Hence, k = 2 log n ≤ h(n).
If it is the case that every vertex in G has degree smaller than d = (log n)3, we will look
to the diameter of G to create our disjoint homometric sets. Letting D denote the diameter
of G, we have n ≤ dD. Thus, D ≥ lognlog d =
logn
3 log logn . Since D is the diameter, there exists
an induced path in G that has length D. Therefore, there exist two disjoint paths in G, both
of which have length dD−12 e; hence, h(n) ≥ d
D−1
2 e.
For our upper bound we begin by defining a class of graphs called kites. We define an
(n,m)− kite as the graph constructed by taking a copy of Kn and a path of length m and
adding an edge between a vertex in Kn to a leaf vertex in the path.
Claim: Let n = 2(m− 1), where m is odd. An (m,m− 2)− kite has no homometric
sets of size larger than n4 .
We prove this by contradiction. Assume there exists homometric sets H1, H2 ⊂ V (G)
such that |H1|+ |H2| > n2 = m−1. We know that |H1|+ |H2| ≥ m+1 since |H1|+ |H2|
must be even. Therefore there exists a vertex in H1 ∪H2 that is in the path and there exist
M. O. Albertson et al.: Disjoint homometric sets in graphs 3
Figure 1: A (5, 3)− kite.
at least 3 vertices in H1∪H2 that are in the complete graph. Let v ∈ H1∪H2 be the vertex
in the path that has the greatest distance to the complete graph. Without loss of generality
we will assume that v ∈ H1.
The only possible vertex that is in both H1 and the complete graph is the vertex of the
complete graph that is adjacent to the path. If there were another, say u, then it would not
be adjacent to the path and in order to have a pair of vertices, x, y ∈ H2 with dist(u, v) =
dist(x, y), either x or y will have a greater distance than v to the complete graph.
This implies that there are at least 2 vertices that are in both H2 and the complete graph,
where neither is adjacent to the path of G. Since v is on the path, there must exist a vertex
in H2 that is also on the path. Therefore the largest distance in the distance list of H2 will
appear at least twice. The largest distance in H1 is dist(v, w) where w is the vertex in
H1 with the shortest distance to the complete graph. Since v has the greatest distance to
the complete graph, there can not be another pair of vertices whose distance is dist(v, w).
Therefore, no such H1 and H2 exists. Hence, h(n) ≤ n4 .
References
[1] T. A. Althuis and F. Göbel, Graph theoretic aspects of music theory, University of Twente,
Dept. of Applied Math, Memoranda 1573, 2001.
[2] B. Ballinger, N. Benbernou, F. Gomez, J. O’Rourke and G. Toussaint, The Continuous Hexa-
chordal Theorem, in: E. Chew, A. Childs and C-H. Chuan (eds.), Mathematics and Computa-
tion in Music, Second Internat’l Conf., MCM 2009, Springer-Verlag, Berlin, 2009, 11–20.
[3] S. K. Blau, The Hexachordal Theorem: A mathematical look at interval relations in twelve-tone
composition, Math. Mag. 72 (1999), 310–313.
[4] G. S. Bloom, A Counterexample to a Theorem of S. Piccard, J. Comb. Theory Ser. A 22 (1977),
378–379.
[5] J. M. Cowley, Diffraction Physics, 2nd ed., North-Holland, Amsterdam, 1986.
[6] P. Gilbert and E. Postpischil, There Are No New Homometric Golomb Ruler Pairs with 12
Marks or Less, Journal of Experimental Mathematics 3 (1994), 147–152.
4 Ars Math. Contemp. 4 (2011) 1–4
[7] P. Lemke, S. S. Skiena and W. D. Smith, Reconstructing sets from interpoint distances, Dis-
crete and Computational Geometry: The Goodman-Pollack Festschrift, vol. 25 of Algorithms
Combin., Springer, Berlin, 2003, 597–631.
[8] L. Pauling and M. D. Shappell, Zeits. Krist. 75 (1930), 128–142.
[9] S. Piccard, Sur les ensembles des distances des ensembles des points d’un espace euclidien,
Mém. Univ. Neuchátel 13 (1939), 78.
[10] J. Rosenblatt and P. D. Seymour, The structure of homometric sets, SIAM Journal of Algorithms
and Discrete Mathematics 3 (1982), 343–350.