pith. sign in

arxiv: 2604.16567 · v1 · submitted 2026-04-17 · 🧮 math.CO · math.AC

Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecture

Emilie Dufresne , Gabriela Jeronimo , Jenny Kenkel , Haydee Lindo , Nelly Villamizar This is my paper

Pith reviewed 2026-05-10 08:20 UTC · model grok-4.3

classification 🧮 math.CO math.AC MSC 05C6013A50
keywords graph reconstruction conjectureinvariant theorydeck of subgraphspolynomial invariantsgraph isomorphism
0
0 comments X

The pith

Polynomials that distinguish graph decks also distinguish the graphs themselves, turning the reconstruction conjecture algebraic.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The graph reconstruction conjecture states that any simple graph on three or more vertices is uniquely determined by its deck, the multiset of all subgraphs formed by deleting one vertex. This paper surveys the conjecture and develops an invariant-theoretic framework whose goal is to produce polynomials that separate different decks and then prove those same polynomials separate the original graphs. If the transfer holds, the long-standing combinatorial question reduces to locating suitable algebraic invariants. A reader would care because this shifts the problem into commutative algebra and invariant theory, where existing tools for rings and group actions might apply directly.

Core claim

The central claim is that an invariant-theoretic setup can be built so that any polynomial distinguishing two decks must also distinguish the two underlying graphs, thereby converting the reconstruction conjecture into a question about separation in an appropriate ring of invariants.

What carries the argument

The ring of polynomials invariant under the natural action that preserves deck structure, used to separate distinct decks and hence the graphs.

If this is right

  • Existence of a complete set of such polynomials would prove the reconstruction conjecture.
  • Algebraic algorithms for computing invariants could be applied to test whether two decks come from isomorphic graphs.
  • The framework links the conjecture to classical questions about separating invariants under group actions on graph adjacency data.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same technique might apply to reconstruction problems for other combinatorial objects such as hypergraphs.
  • Computer algebra packages could search for low-degree separating polynomials on small vertex counts.
  • If the transfer works, one could test candidate polynomials on known non-reconstructible pairs if any are discovered.

Load-bearing premise

That polynomials capable of distinguishing decks can be constructed so their distinguishing power passes directly to the original graphs with no loss of information.

What would settle it

Two non-isomorphic graphs whose decks receive different values from some polynomial yet the graphs themselves receive the same value from every such polynomial.

Figures

Figures reproduced from arXiv: 2604.16567 by Emilie Dufresne, Gabriela Jeronimo, Haydee Lindo, Jenny Kenkel, Nelly Villamizar.

Figure 1
Figure 1. Figure 1: The deck of cards for the unknown graph. [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: The four vertex deleted subgraphs of the [PITH_FULL_IMAGE:figures/full_fig_p002_3.png] view at source ↗
Figure 5
Figure 5. Figure 5: Nonisomorphic graphs with two vertices which have the same decks. , [PITH_FULL_IMAGE:figures/full_fig_p002_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The deck of both graphs with two vertices. [PITH_FULL_IMAGE:figures/full_fig_p002_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Each vertex is labeled with its degree. In [PITH_FULL_IMAGE:figures/full_fig_p003_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Two non-isomorphic directed graphs with isomorphic decks. , , , [PITH_FULL_IMAGE:figures/full_fig_p005_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The directed deck of the graphs in Figure 8. [PITH_FULL_IMAGE:figures/full_fig_p005_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: An R-weighted graph on four vertices viewed as a weighted graph with all the edges as￾signed the same weight, and any counterexample to the original conjecture would yield a counterexample to the weighted conjecture. Conversely, any counterexample to the weighted reconstruction conjecture would involve only finitely many distinct edge weights. By relabeling these weights injectively, one could therefore o… view at source ↗
Figure 11
Figure 11. Figure 11: The graph M corresponding to the mono￾mial xM = x{1,2}x{2,3} in Example 6.1. Orbit sums therefore provide natural invariants of graphs, since they depend only on the isomor￾phism class of the underlying graph. The polyno￾mials OSn (xM) are invariant by construction, and in fact they form a basis for k[Vn] Sn as a k-vector space. Indeed, every invariant polynomial f ∈ k[Vn] Sn can be written as a finite k-… view at source ↗
Figure 12
Figure 12. Figure 12: Graphs on three vertices corresponding to [PITH_FULL_IMAGE:figures/full_fig_p009_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: Note that G′ is not a subgraph of G when the labels are preserved, but G has two subgraphs that are isomorphic to G′ when the labels are re￾moved. These observations also suggest an algorithmic viewpoint. A well-known problem in graph theory is the subgraph isomorphism problem: given graphs G and G′ , what’s the quickest procedure to deter￾mine whether G has a subgraph that is isomorphic to G′ ? We have j… view at source ↗
Figure 14
Figure 14. Figure 14: The secret graph from the introduction. 11 [PITH_FULL_IMAGE:figures/full_fig_p011_14.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 0 minor

Summary. The manuscript is an expository article that surveys the graph reconstruction conjecture asserting that every simple graph on at least three vertices is uniquely determined by its deck of vertex-deleted subgraphs. It outlines an invariant-theoretic strategy whose stated goal is to translate the problem by showing that polynomials distinguishing decks also distinguish the original graphs.

Significance. If the outlined invariant-theoretic framework can be carried through to produce polynomials whose deck-distinguishing power lifts without loss to the graphs, the translation would supply a new algebraic route to the reconstruction conjecture and related questions in graph theory. The paper's explicit credit to prior surveys and its framing as a research direction rather than a completed reduction are strengths that could usefully guide subsequent work.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, including the recognition of its expository nature, the framing as a research direction rather than a completed proof, and the potential value of the invariant-theoretic approach to the reconstruction conjecture. We appreciate the recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity in expository survey

full rationale

The manuscript is explicitly expository: it surveys the reconstruction conjecture and outlines an invariant-theoretic strategy whose stated goal is to translate deck distinction into graph distinction. No theorem is asserted that constructs separating polynomials on decks and proves they lift without loss to the original graphs. The central aim is a research direction rather than a finished reduction, so no load-bearing step reduces to its own inputs by construction, fitted parameters, or self-citation chains. The derivation is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard results from graph theory and invariant theory without introducing new fitted parameters or postulated entities.

axioms (2)
  • standard math Standard properties of polynomial rings and group actions in invariant theory
    Invoked when translating deck distinctions into polynomial distinctions
  • domain assumption Basic facts about vertex-deleted subgraphs and decks in graph theory
    Used throughout the survey of the reconstruction conjecture

pith-pipeline@v0.9.0 · 5365 in / 1105 out tokens · 32728 ms · 2026-05-10T08:20:07.780438+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

4 extracted references · 4 canonical work pages

  1. [1]

    Derksen and G

    MR1037416 [DK15] H. Derksen and G. Kemper,Computational in- variant theory, Encyclopaedia of Mathematical Sciences, vol. 130, Springer, Heidelberg, 2015. MR3445218 [Duf09] E. Dufresne,Separating invariants and finite reflec- tion groups, Adv. Math.221(2009), no. 6, 1979–

    work page 2015

  2. [2]

    Groenland, T

    MR2522833 [GJK+22] C. Groenland, T. Johnston, A. Kupavskii, K. Meeks, A. Scott, and J. Tan,Reconstructing the degree sequence of a sparse graph from a partial deck, J. Combin. Theory Ser. B157(2022), 283–

    work page 2022

  3. [3]

    Gupta, P

    MR4463034 [GMP03] S. Gupta, P. Mangal, and V. Paliwal,Some work towards the proof of the reconstruction conjec- ture, Discrete Math.272(2003), no. 2-3, 291–296. MR2009550 [Gre71] D. Greenwell,Reconstructing graphs, Proc. Amer. Math. Soc.30(1971), 431–433. MR286699 [Har64] F. Harary,On the reconstruction of a graph from a collection of subgraphs, Theory of...

    work page 2003

  4. [4]

    Kelly,A congruence theorem for trees, Pacific J

    MR890233 [Kel57] P. Kelly,A congruence theorem for trees, Pacific J. Math.7(1957), 961–968. MR87949 [KW21] A. Kostochka and D. West,On reconstruction of graphs from the multiset of subgraphs obtained by deletingℓvertices, IEEE Trans. Inform. Theory67 (2021), no. 6, 3278–3286. MR4289319 [M¨ u76] V. M¨ uller,Probabilistic reconstruction from sub- graphs, Co...

    work page 1957