← All problems

The token-reconstruction-family conjecture

3 years old · documented by

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

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

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

References
  1. 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).

Progress summary

Refreshed
Open

The reformulated conjecture remains open; known results cover only restricted graph classes or almost all random graphs, not every graph.

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

Known results

  • Connected induced-(C4,diamond)(C_4,\mathrm{diamond})-free graphs: reconstruction from Fk(G)F_k(G) is established in the stated range (2022).
  • The same paper describes relevant automorphism groups for k≠n/2k\ne n/2 and k=n/2k=n/2, but does not prove the family assertion for arbitrary graphs.

August 2026 almost-every-graph result

Yuanming Luo proves that the ordinary token-graph reconstruction conjecture holds for almost every finite graph, with probability tending to 11 for random graphs. This is related progress, not a proof or counterexample for the token-reconstruction-family conjecture.

Current status (as of November 2026): The token-reconstruction-family conjecture remains open; special graph classes and an almost-every-graph theorem are known, but the exact family-automorphism assertion has no recorded resolution.

Sources

Solutions 1

the rank 2 case of the conjecture is provedSee full solutionHide full solution