Tom Johnston

Reconstructing trees from small cards

The $\ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $\ell$ vertices, and a graph is said to be reconstructible from its $\ell$-desk if no other graph has the same $\ell$-deck. The first major result on reconstruction was due to Kelly in 1957 who showed that trees can be reconstructed from their $(n-1)$-deck, and this was later improved to their $(n-2)$-deck by Giles in 1976. I will talk about recent work which shows that trees can be reconstructed from their $8n/9 + o(n)$ deck, where a constant fraction of the vertices have been removed. We will also consider the related problems of reconstructing the degree sequence and whether the graph is connected.

Joint work with Carla Groenland, Alex Scott and Jane Tan.