Tech & AI 5.1

Mathematicians solve decades-old puzzle about network structure optimization

Researchers have cracked a 40-year-old problem about how to identify the most efficient parts of complex networks. The findings could improve how engineers design systems ranging from supply chains to communication networks, by revealing which structural patterns minimize or maximize performance at different scales.

Originaltitel: Extrema of local mean and local density in a tree

Abstrakt

Given a tree T and a subtree S of T, one can define the local mean at S, μT(S),to be the average order of the subtrees of T containing S. In 1983, Jamison showed that μT(S)< μT(S′) if S ⊂ S′ as subtrees of T. Therefore, it is natural to ask the following question. Among all the k-subtrees (subtrees of order k), which one achieves the maximal/minimal local mean and what properties does it have? We call such k-subtrees k-maximal/k-minimal. Wagner and H. Wang showed in 2016t hat a 1-maximal subtree has degree 1 or 2. In this paper, we show that if T is not a path, a 1-minimal subtree of T has degree at least 3. For k≥2, we show that a k-maximal subtree has at most one leaf whose degree in T is greater than 2, and that such a leaf can only occur when all other leaves in S are also leaves in T. Parallel results hold for k-minimal subtrees. Roughly speaking, the leaves of a k-maximal subtree tend to have degree 1 or 2 in T, while the leaves of a k-minimal subtree tend to have degree at least 3 in T. In the second part, this paper introduces the local density as a normalization oflocal means, for the sake of comparing subtrees of different orders. We show that the local density at subtree S is lower-bounded by 1/2 with equality if and only if S contains all the vertices of degree at least 3 in T. On the other hand, local density can be arbitrarily close to 1.

Generera ett redaktionellt utkast på svenska