13
$\begingroup$

The Reconstruction Conjecture for simple graphs remains unresolved. Most attempts I've seen at resolving the conjecture aim at proving it to be true (or partially true). I don't believe there is a compelling reason for it to be true, so I'm brainstorming how to generate a counterexample.

Bollobás showed that almost all graphs have reconstruction number 3, which means that there exist three cards in their deck that uniquely determine the graph. This essentially thwarts any obvious attempt at generating random graphs to find a counterexample.

On the other hand, the Reconstruction Conjecture for digraphs is false (there are known families of counterexamples). It might also be similarly impractical to generate random counterexamples to the Reconstruction Conjecture for digraphs, despite knowing it is false.

Hence my question:

Question: Are almost all digraphs reconstructible?

$\endgroup$

1 Answer 1

3
$\begingroup$

I'm thinking the answer is yes. In the undirected case, Bollobas proves that any 3 cards determine the graph. So given a random directed graph $D(n,p)$, ignore orientations and collapse the resulting multi-edges. This gives an undirected random graph $G(n,q) $ with $q = 1 - (1-p)^2$. This graph can be reconstructed with any 3 cards, so revealing the orientations on the cards should give back the original directed graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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