TL;DR
This paper significantly improves the known lower bound for the size of disjoint homometric sets in trees, showing that any tree with $n$ vertices contains such sets of size at least $\sqrt{n/2} - 1$. For a specific type of tree called "haircomb trees," they achieve an even better bound of $cn^{2/3}$. This work advances our understanding of graph structures with identical distance profiles.
What Problem Does This Paper Address?
The paper tackles the problem of finding "homometric sets" within graphs, specifically trees. Two disjoint subsets of vertices in a graph are considered homometric if the multiset of distances between all pairs of vertices within the first subset is identical to the multiset of distances within the second subset. This concept has roots in fields like crystallography and coding theory, where identifying structures with similar "distance fingerprints" is important.
While previous work established that any graph with $n$ vertices contains homometric sets of size at least $c \log n / \log \log n$, and specifically for trees, a lower bound of roughly $n^{1/3}$ was known, there was a significant gap between these bounds and the trivial upper bound of $n/2$. The authors aim to close this gap by providing a tighter lower bound for general trees and an even stronger one for a particular class of trees (haircomb trees).
Methods
The core of the paper's approach for general trees involves a recursive strategy applied to rooted trees. They define a function, $f(T)$, that recursively calculates a lower bound for the size of homometric sets within a tree $T$. This function leverages the structure of the tree by considering its children subtrees and their heights. The proof then proceeds by induction on the height of the tree, carefully analyzing cases based on the sum of subtree heights.
For haircomb trees, a more specialized construction is employed. They represent the tree vertices as points on a 2D integer lattice and consider various "drawings" (embeddings) of the tree. By analyzing the overlaps between these drawings, specifically how vertices from different parts of the haircomb tree align, they construct homometric sets. The proof involves bounding the total number of overlaps across a family of drawings and then averaging to find a drawing with a significant overlap, which translates to large homometric sets.
Datasets
Not discussed in the paper. The paper focuses on theoretical graph properties and constructions rather than empirical evaluation on datasets.
Key Insights and Ideas
- Improved Tree Bound: The most significant insight is the improvement of the general lower bound for homometric sets in trees from $n^{1/3}$ to $\sqrt{n/2} - 1$. This suggests that trees are "richer" in homometric structures than previously thought.
- Haircomb Tree Specialization: The paper demonstrates that by exploiting the specific structure of haircomb trees (a spine with attached paths), a much stronger bound of $cn^{2/3}$ can be achieved. This highlights how structural properties can lead to better results.
- Recursive Bounding Function: The introduction of the recursive function $f(T)$ provides a systematic way to derive lower bounds for homometric sets in trees, making the proof more structured and generalizable.
- Lattice Embeddings for Haircombs: The novel use of 2D lattice embeddings for haircomb trees to find homometric sets is a clever geometric approach to a combinatorial problem. Analyzing overlaps in these embeddings directly leads to the size of the homometric sets.
- Tightness of Bounds: The paper provides constructions of binary trees that demonstrate the tightness of their general bound for binary trees, suggesting that their $\sqrt{n/2}-1$ bound is close to optimal for this class.
Key Results
- General Trees: Any tree on $n$ vertices contains a pair of disjoint homometric sets of size at least $\sqrt{n/2} - 1$. This is a significant improvement over the previous $n^{1/3}$ bound.
- Haircomb Trees: Any haircomb tree on $n$ vertices contains a pair of disjoint homometric sets of size at least $cn^{2/3}$ for some constant $c > 0$.
- Binary Tree Bound Tightness: The paper shows that for binary trees, the bound $\sqrt{n}-1$ is tight, meaning there exist binary trees where the largest homometric sets are precisely of this size.
Limitations and Future Work
- General Graphs: The paper focuses on trees and haircomb trees. The question of finding similar tight bounds for more general graphs remains open. The authors suggest that trees, due to their simple structure, might be a good starting point for improving upper bounds on homometric sets in general graphs.
- Sublinear Upper Bounds: The authors ponder whether a tree witnessing a sublinear upper bound on homometric sets exists, but they are "prone to believe that the right bound in case of trees is linear in n." This suggests that further investigation into the structure of trees that might limit homometric set sizes could be fruitful.
- More General Homometric Sets: The constructions in this paper focus on homometric sets that induce isomorphic forests (specifically, disjoint unions of paths). The authors acknowledge that considering more general types of homometric sets could potentially lead to even better bounds.
Summary updated