17
$\begingroup$

Wikipedia's article on the Reconstruction Conjecture mentions that the conjecture is false for digraphs, and refers 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 to avoid certain small cases. (Edit: For $4$ vertices, see Julian's example below.) Acyclic tournaments are reconstructible 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$?

Improve this question
$\endgroup$
5
  • 5
    $\begingroup$ Nice question. There are actually two questions here, depending in whether the acyclicity is given or has to be inferred from the deck, but that is not an issue: for $n\ge 3$, $G$ is acyclic iff every vertex-deleted subgraph is acyclic and not all of them are paths. $\endgroup$
    – Brendan McKay
    Commented Aug 27, 2012 at 10:18
  • 4
    $\begingroup$ A related question is the reconstruction of posets. See for instance springerlink.com/content/q10314j8j0j721l8. $\endgroup$
    – Richard Stanley
    Commented Aug 27, 2012 at 23:35
  • $\begingroup$ The poset problem translated to the path algebra situation becomes the question whether $\Lambda$ is reconstructible from the deck of subalgebras $(1-e)\Lambda (1-e)$, where $e$ runs over all the trivial paths. $\endgroup$
    – Dag Oskar Madsen
    Commented Aug 28, 2012 at 6:28
  • $\begingroup$ Is there an additional meaning to the use of the word "deck" here that isn't carried by "set" (or maybe "multiset")? $\endgroup$
    – Qiaochu Yuan
    Commented Dec 19, 2014 at 10:12
  • 1
    $\begingroup$ @QiaochuYuan: A deck is just a multiset. If the Deck Reconstruction Conjecture is equivalent to the Set Reconstruction Conjecture I think still is an open question. $\endgroup$
    – Dag Oskar Madsen
    Commented Dec 19, 2014 at 10:22

1 Answer 1

Reset to default
1
$\begingroup$

Brendan McKay's comment suggests that the following is true:

A vertex is a sink iff it is a sink in every vertex-deleted subgraph.

Assuming this, one can proceed as follows:

1) The directed acyclic graph can then be split as $Q'\stackrel{some arrows}{\to} sink $

2) deleting the sink gives you $Q'$

3) if there are at least two neighbours of the sink, you get the arrows between the sink and any neighbour by deleting each of the neighbours

4) if there is only one neighbour, there has to be another vertex (since there are at least 3 vertices), deleting this one, one gets the number of arrows between the neighbour and the sink.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This seems like a strategy, but how do you recognize the sink you have chosen in all subgraphs if there are several sinks? The same goes for recognizing the different neighbours. There is no labelling of the vertices. $\endgroup$
    – Dag Oskar Madsen
    Commented Aug 27, 2012 at 12:14
  • $\begingroup$ I have to think about that, I was assuming a labeling is given. $\endgroup$
    – Julian Kuelshammer
    Commented Aug 27, 2012 at 12:20
  • 4
    $\begingroup$ For 4 vertices it is not possible then, take the square with the two possible non-cyclic orientations. $\endgroup$
    – Julian Kuelshammer
    Commented Aug 27, 2012 at 12:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .