Carla Groenland

Date: 16:00-17:00, Thursday, 24.03.2022
Location: Minnaert – 2.02& MS Teams ICS Colloquium

Title: Graph reconstruction
Abstract: Can you reconstruct a network from a set of its pieces? Given a graph G, we obtain a ‘card’ of the graph by removing one vertex and all incident edges. The graph reconstruction conjecture states that each graph G on at least 3 vertices can be reconstructed from the multiset of its cards (i.e. the 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. Moreover, some graphs with extra structure can be reconstructed, such as trees. We study a set-up with smaller induced subgraphs (‘small cards’). We use a surprising algebraic tool and introduce several counting techniques.This is based on joint work with Tom Johnston, Alex Scott and Jane Tan.