Logo: to the web site of Uppsala University

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. 

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.