Graph reconstruction from partial information

Speaker: Carla Groenland (Utrecht University)

Abstract: 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 consider when such information can still be reconstructed when we have access to less induced subgraphs (a 'partial deck') or smaller induced subgraphs ('small cards'). We use a surprising algebraic tool as well as counting and integer rounding techniques. This is based on joint work with Hannah Guggiari, Tom Johnston, Andrey Kupavskii, Kitty Meeks, Alex Scott and Jane Tan.

Date and time: 25/03/2021 at 14:30 (Paris time)

Link to the talk: https://bbb-temp.grenet.fr/b/lou-9x7-69p