Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture

2026/04/17 by Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel +2 · 1 voice
Mathematics · #math.CO #math.AC

paper · pdf

Abstract

The graph reconstruction conjecture asserts that every simple graph on at least three vertices is uniquely determined by its deck of vertex-deleted subgraphs. In this expository article we survey the conjecture and present an invariant-theoretic approach to studying it. The aim is to be able to show that polynomials that distinguish between decks also distinguish between original graphs, thus translating a graph-theoretic problem into an algebraic one.

Citations

• Reconstructing the degree sequence of a sparse graph from a partial deck
• Reconstruction of small graphs and digraphs
• On reconstruction of graphs from the multiset of subgraphs obtained by\n deleting \ℓ vertices

Discussions

• New expository article surveying the graph reconstruction conjecture and presenting an invariant-theoretic approach to studying it, translating a graph-theoretic problem into an algebraic one. arxiv.o [bsky, 3 points, 0 comments]

Related

• The Reconstruction of Graphs
• A Simple Explanation for the Reconstruction of Graphs
• An algebraic formulation of the graph reconstruction conjecture
• Reconstruction from smaller cards
• Reconstructibility of the K_r-count from n-1 cards