The ℓ-deck of a graph G is the multiset of all induced subgraphs of G on ℓ vertices. We say that a graph is reconstructible from its ℓ-deck if no other graph has the same ℓ-deck. In 1957, Kelly showed that every tree with n ≥ 3 vertices can be reconstructed from its (n − 1)-deck, and Giles strengthened this in 1976, proving that trees on at least 6 vertices can be reconstructed from their (n − 2)-decks. Our main theorem states that trees are reconstructible from their (n − r)-decks for all r ≤ n/9 + o(n), making substantial progress towards a conjecture of Nýdl from 1990. In addition, we can recognise the connectedness of a graph from its ℓ-deck when ℓ ≥ 9n/10, and reconstruct the degree sequence when ℓ≥2nlog(2n). All of these results are significant improvements on previous bounds.

Two permutations σ and π are ℓ-similar if they can be decomposed into subpermutations σ(1), . . . ,σ(ℓ) and π(1), . . . ,π(ℓ) such that σ(i) is order-isomorphic to π(i) for all i ∈[ℓ]. Recently, Dudek, Grytczuk, and Ruciński Variations on twins in permutations, Electron. J. Combin., 28 (2021), P3.19. posed the problem of determining the minimum ℓ for which two permutations chosen independently and uniformly at random are ℓ-similar. We show that two such permutations are O(n1/3 log11/6(n))-similar with high probability, which is tight up to a polylogarithmic factor. Our result also generalizes to simultaneous decompositions of multiple permutations.

The deck of a graph G is the multiset of cards {G−v:v∈V(G)}. Myrvold (1992) showed that the degree sequence of a graph on n≥7 vertices can be reconstructed from any deck missing one card. We prove that the degree sequence of a graph with average degree d can be reconstructed from any deck missing O(n/d³) cards. In particular, in the case of graphs that can be embedded on a fixed surface (e.g. planar graphs), the degree sequence can be reconstructed even when a linear number of the cards are missing.