Logo: to the web site of Uppsala University

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.

This thesis studies subtree statistics in trees and graphs, organized around two complementary themes: extremal questions on deterministic finite trees, and asymptotic questions on sequences of trees and dense graphs. The starting point is a list of open problems and a conjecture of Jamison from the 1980s, which together set the agenda for much of the subsequent literature on the mean subtree order and the subtree density.

The first half of the thesis concerns extremal subtree statistics. Article I settles Jamison's edge-contraction conjecture in full: contracting any edge of a finite tree decreases the mean subtree order by at least 1/3​, with equality if and only if the tree is a path. Combined with earlier work of Luo, Xu, Wagner, and H.Wang on the pendant-edge case, this completes a problem that had been open for four decades. Article II investigates the structure of subtrees that maximize or minimize the local mean among subtrees of a fixed order, introducing an index that measures the change of local mean under elementary operations. As a normalization that allows comparison across orders, the article also introduces the local density and establishes a sharp lower bound, 1/2​, attained precisely by subtrees containing the body of the tree.

The second half turns to asymptotics. Article III studies subtree statistics under Benjamini–Schramm convergence and shows that the subtree entropy per site converges along every locally convergent sequence of finite trees, and that the subtree density does so under a natural condition that rules out long paths in the limit. Article IV proves that, in any graph with minimum degree linear in the number of vertices, the high-degree coefficients of the subtree polynomial satisfy a Poisson-type limit law and the complex roots cluster near the origin, in stark contrast to the tree case.

Given a tree T, a subtree in T is a subgraph that is a tree itself. The set of subtrees in a tree is related to many important graph parameters, one of which is the mean subtree order. Jamison initiated and laid the groundwork of the study of mean subtree order in the early 1980s and raised in total seven conjectures and open questions, on which the first two projects in the licentiate are based. In the first project, we will give a descrip- tion of the subtrees that achieve maximal/minimal local mean among all the subtrees of the same order. In the second project, we provide a proof that the mean subtree order decreases at least 1/3 in contracting an edge of a tree, which closed one of two conjectures that had remained open. Lastly, we study the asymptotic behavior of the number of subtrees for a sequence of trees that converges in the Benjamini–Schramm sense. 

Given a tree T of order n , one can contract any edge and obtain a new tree T & lowast; of order n - 1. In 1983, Jamison made a conjecture that the mean subtree order, i.e., the average order of all subtrees, decreases at least 31 in contracting an edge of a tree. In 2023, Luo, Xu, Wagner and Wang proved the case when the edge to be contracted is a pendant edge. In this article, we prove that the conjecture is true in general. (c) 2024 The Author. Published by Elsevier Inc. This is an open access article under the CC BY license (http:// creativecommons.org/licenses/by/4.0/).