Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
5  
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. –  Brendan McKay Aug 27 '12 at 10:18
4  
A related question is the reconstruction of posets. See for instance springerlink.com/content/q10314j8j0j721l8. –  Richard Stanley Aug 27 '12 at 23:35
    
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. –  Dag Oskar Madsen Aug 28 '12 at 6:28
    
Is there an additional meaning to the use of the word "deck" here that isn't carried by "set" (or maybe "multiset")? –  Qiaochu Yuan Dec 19 at 10:12
1  
@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. –  Dag Oskar Madsen Dec 19 at 10:22

1 Answer 1

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.

share|improve this answer
    
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. –  Dag Oskar Madsen Aug 27 '12 at 12:14
    
I have to think about that, I was assuming a labeling is given. –  Julian Kuelshammer Aug 27 '12 at 12:20
3  
For 4 vertices it is not possible then, take the square with the two possible non-cyclic orientations. –  Julian Kuelshammer Aug 27 '12 at 12:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.