The token-reconstruction-family conjecture

At least 3 years old · documented by 2022

Let $G$ be a graph, let $F_k(G)$ denote its $k$ -token graph, and let a $k$ -token reconstruction family of $F_k(G)$ be a family of subsets as defined in the source. Let $cmathcal{R}$ and $cmathcal{R}'$ be two such reconstruction families, and let $cmathrm{Aut}(F_k(G))$ denote the automorphism group of $F_k(G)$ . Token-reconstruction-family conjecture. There exists $cpsicincmathrm{Aut}(F_k(G))$ such that

cmathcal{R}'=\{cpsi(X):X\incmathcal{R}_\varphi,\}

The source presents this as a reformulation of the preceding reconstruction conjecture using a proposition about $k$ -token reconstructions. The supplied excerpt does not establish whether this reformulated conjecture has been resolved.

References

Primary source

Ruy Fabila-Monroy and Ana Laura Trujillo-Negrete, “Connected (C_4,Diamond)-free Graphs Are Uniquely Reconstructible from Their Token Graphs”, arXiv:2207.12336 (2022).

graph-reconstruction token-graphs

Posted 1 month ago · edited 1 week ago

Progress summary

Refreshed 1 week ago

Open

The conjecture remains open: a recent result settles the related reconstruction question for almost all graphs, but not this stronger reformulation.

The conjecture asks whether any two reconstruction families of the same token graph are related by an automorphism of that graph. A 2022 paper presents it as a reformulation of the token-reconstruction conjecture, without resolving it.

Known results

Connected $(C_4,\mathrm{diamond})$ -free graphs: a $k$ -token reconstruction can be computed in polynomial time for $k\le n/2$ , and the token graph is uniquely reconstructible (2022).
For these graphs, the results support the reformulation but do not prove it for arbitrary graphs.

Almost-every-graph result, September 2026

A later paper proves the ordinary token-graph reconstruction conjecture for almost every graph: if $F_k(G)\cong F_k(H)$ , then $G\cong H$ with probability tending to $1$ for random graphs. The supplied account does not prove the token-reconstruction-family conjecture itself, so this is relevant partial progress rather than a resolution.

Current status (as of September 2026): The token-reconstruction-family conjecture remains open; special graph classes and almost-every-graph results are known, but no proof, counterexample, or verified progress for the exact reformulation has been recorded.

Sources

Partial progressthe rank 2 case of the conjecture is proved and formalizedSee full solutionHide full solution

https://github.gatech.edu/yluo387/TwoTokenReconstruction see this repo