Logotyp: till Uppsala universitets webbplats

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.