The threshold phenomenon around stretch 2 observed in the non-Steiner tree cover problem can be explained from a more fundamental perspective based on the properties of tree metrics and the structure of the tree cover construction.
At stretch 2, the goal is to preserve the distances between points in the tree metric with minimal additional trees in the cover. The lower bound of Ω(n) trees for stretch 2 indicates that a linear number of trees is necessary to achieve this stretch factor. This can be attributed to the inherent complexity of the tree metric and the need for multiple trees to accurately represent the distances between points.
On the other hand, the upper bound of O(log n) trees being both necessary and sufficient for stretch 2 suggests a trade-off between the number of trees and the stretch factor. This trade-off is likely influenced by the hierarchical structure of the tree metric and the way in which distances are preserved through the tree cover construction process.
The transition from requiring Ω(n) trees for stretch 2 - ϵ to O(log n) trees for stretch 2 can be seen as a critical point where the complexity of the tree cover construction changes significantly. This threshold phenomenon highlights the delicate balance between the number of trees in the cover and the stretch factor, shedding light on the fundamental properties of tree metrics and their representations.