[DMO] Carla Groenland: Graph reconstruction from small cards

17 november 2023 14:00 t/m 15:00 - Locatie: Lecture Hall H, 36.LH.01.340 | Zet in mijn agenda

The graph reconstruction conjecture states that each graph G on at least 3 vertices can be reconstructed from the multiset of all induced subgraphs on n-1 vertices. Although this conjecture is notoriously difficult, it is easy to reconstruct some information about the graph, e.g. the degree sequence of G and whether G is connected. We study a set-up with smaller induced subgraphs ('small cards'). Using a theorem about the number of positive real roots of a complex polynomial, we show the induced subgraphs on 0.9n vertices determine whether an n-vertex graph is connected and we also develop counting techniques to reconstruct trees from subgraphs of size about 8n/9.
This is based on joint work with Tom Johnston, Alex Scott and Jane Tan.