Emilie Dufresne (University of York) – Invariant Theory and the graph reconstruction conjecture

Abstract - The Graph Reconstruction Conjecture is a long-standing problem in Graph Theory formulated by Kelly (1957) and Ulam (1960). The conjecture states that every graph with at least three vertices can be uniquely reconstructed (up to isomorphism) from their deck one-vertex deleted subgraphs. It is well known that the graph isomorphism problem can be worded using Invariant Theory, although this is not particularly interesting in practice as the computations get quickly out of hand. In this talk, we explore how invariant theory can be used to approach the Graph Reconstruction conjecture. This naturally brings the focus to K-weighted graphs. We focus on the attempt by Thiéry (2000), which led to a disproof of a stronger statement using a computational argument. This also turns out not to be particularly practical, but we'll see how it still brings valuable insight. This talk is based on a survey paper joint with Gabriela Jerónimo, Jenny Kenkel, Haydee Lindo and Nelly Villamizar.