2021/03/24 by Groenland, Carla, Johnston, Tom, Scott, Alex +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2103.13359
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.