Reconstructing a $d$-polytope from its $k$-skeleton ($k\le d-2$) amounts to determining the face lattice of the polytope from the dimension and skeleton. For each $d\ge 4$, there are $d$-polytopes that have isomorphic $(d-3)$-skeleta and yet are not combinatorially isomorphic. But every $d$-polytope is reconstructible from its $(d-2)$-skeleton. Section 5.2 focusses on reconstructions from 2-skeletons and 1-skeletons. It presents an algorithm that reconstructs a $d$-polytope with at most $d-2$ nonsimple vertices from its dimension and 2-skeleton. This result is tight: there are pairs of nonisomorphic $d$-polytopes with $d-1$ nonsimple vertices and isomorphic $(d-3)$-skeleta for each $d\ge 4$.Blind and Mani-Levitska (1987), and later Kalai (1988), showed that a simple polytope can be reconstructed from its dimension and graph. We present a slight generalisation of this result and briefly discuss the theorem of Friedman (2009) stating that the reconstruction can be done in time polynomial in the number of vertices. The chapter ends with variations on the reconstruction problem.

Branching processes, which are the focus of this chapter, arise naturally in the study of stochastic processes on trees and locally tree-like graphs. Similarly to martingales, finding a hidden branching process within a probabilistic model can lead to useful bounds and insights into asymptotic behavior. After a review of the extinction theory of branching processes and of a fruitful random-walk perspective, we give a couple examples of applications in discrete probability. In particular we analyze the height of a binary search tree, a standard data structure in computer science. We also give an introduction to phylogenetics, where a “multitype” variant of the Galton–Watson branching process plays an important role; we use the techniques derived in this chapter to establish a phase transition in the reconstruction of ancestral molecular sequences. We end this chapter with a detailed look into the phase transition of the Erdos–Renyi graph model. The random-walk perspective mentioned above allows one to analyze the “exploration” of a largest connected component, leading to information about the “evolution” of its size as edge density increases.