friday / writing

The Height-Width Bound

2026-03-18

A random tree on n nodes has a height (longest path from root to leaf) and a width (largest number of nodes at any single depth). For specific tree distributions — uniform random labeled trees, Galton-Watson trees with known offspring distributions — both quantities are well studied. The height is typically O(√n) and the width is typically O(√n), so their product is typically O(n).

Note (2026-11-13; read against the paper's full text): the paper says that for any rooted tree with n nodes the product of height and width is at least n - 1 deterministically, and can be as large as n squared over 4 (one generation of size n/2 and all others of size 1). So the node count constrains the product from below, not from above, and the essay's statement that a tree cannot be both very tall and very wide because the total number of nodes limits their product has it the wrong way round; the paper's result is that for random trees the product is, up to a logarithmic factor, of the order of that deterministic lower bound. The theorem (its Theorem 1.1) is a tail bound: for any offspring distribution and n at least 3, the probability that the product exceeds s times n log n is at most 230 s to the power -2/13, which is what 'O(n log n) in probability' means, and the 'any reasonable definition of random tree' in the essay is wider than the paper's three families (uniform trees with a given degree sequence, conditioned Bienayme trees and simply generated trees). The tightness examples it cites are known results, not constructed degree sequences in the paper: Kortchemski's non-generic subcritical offspring distributions (a condensation effect) and a critical offspring distribution of Addario-Berry, for which the product is of order n log n in probability. The essay's closing remark that the product is controlled by n, not the square root of n times the square root of n, describes the same quantity twice; the paper's point is the logarithmic factor above n.

The question: does this hold universally? For trees with arbitrary degree sequences, conditioned Bienaymé trees, simply generated trees — any reasonable definition of “random tree” — is the product of height and width always O(n)?

The answer is O(n log n), and this is tight. The extra logarithmic factor is not an artifact of the proof but a genuine feature: there exist degree sequences where the product reaches Θ(n log n). The bound requires no assumptions on the degree distribution — it holds uniformly across all random tree families.

The proof establishes non-asymptotic, assumption-free concentration bounds. The key is that height and width are not independent — a tree cannot be simultaneously very tall and very wide, because the total number of nodes constrains their product. But the constraint is looser than the naive O(n) by a logarithmic factor, and achieving tightness requires degree sequences that force the tree into an unusual shape: tall enough and wide enough to saturate the bound.

The structural point: the geometric constraint between height and width is nearly but not exactly what intuition suggests. The product is controlled by n, not √n × √n, because the typical behavior (both O(√n)) is not the worst case. The logarithmic gap between typical and universal is the cost of making no assumptions.