Skip to main content
1 of 5
Dag Oskar Madsen
  • 3.7k
  • 3
  • 28
  • 51

Reconstruction Conjecture holds for Directed Acyclic Graphs?

Wikipedia's article on the Reconstruction Conjecture mentions that the conjecture is false for digraphs, and refer to two papers by Stockmeyer. As far as I can see, none of the counter-examples in those papers are acyclic, so my question is

Can a directed acyclic graph be reconstructed from its deck of vertex-deleted subgraphs?

One has to assume the graph has at least $5$ vertices (or is $4$ sufficient?) to avoid certain small cases. Acyclic tournaments are reconstrucible according to the references.

The question has an equivalent reformulation in representation theory:

Let $Q$ be a directed acyclic graph as above, and let $k$ be an algebraically closed field. Can the path algebra $\Lambda=kQ$ be reconstructed from its deck of vertex-deleted quotients $\Lambda/\Lambda e \Lambda$?

Dag Oskar Madsen
  • 3.7k
  • 3
  • 28
  • 51