Tom Johnston

Reconstructing random trees

The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices. We say that a graph $G$ is reconstructible from its $\ell$-deck if any graph that has the same $\ell$-deck as $G$ is isomorphic to $G$. The famous graph reconstruction conjecture asserts that the $(n-1)$-deck suffices for all graphs with at least three vertices, and the very first result on graph reconstruction, due to Kelly in 1957, showed that this conjecture is true for trees. Since then there have been many results on reconstructing trees with less information, and it's now known that one cannot hope to reconstruct all trees with anything less than their $(\lfloor n/2 \rfloor + 1)$-decks. Is this because of a small number of difficult trees, or is this a more general phenomenon?
We will discuss ongoing work which shows that a ``typical'' tree only needs $O(\log(n))$ vertices on each card.
 
Joint work with Louigi Addario-Berry, Serte Donderwinkel, Carla Groenland and Thomas Hughes.