Reconstruction puzzles

Question

[Added: This is a follow-up of an earlier post.]

Consider the following "reconstruction puzzle", stated informally:

Given a concrete poset, e.g. the poset of undirected unlabeled finite graphs without isolated vertices, ordered by embeddability (arrow heads, identities and composition omitted in the diagram):

     (source)

Now forget about the inner structure of the objects and consider only the corresponding abstract poset:

     (source)

The "reconstruction puzzle" is to reconstruct the inner structure of the objects unambiguously from their "positions" in the poset.

It's obvious what a solution of this puzzle is and that it can be solved "by hand" for at least some of the smaller objects, just carefully considering the in- and out-arrows.

Question #1: How can such a puzzle be stated formally?

---

Question #2: How can it be solved "algorithmically"?

---

Question #3: What's the mathematics behind this kind of puzzle?

I suppose it's not category theory, since category theory is not concerned with the inner structure of objects.

---

Question #4: Can it be shown - at least for this concrete example - that every object is reconstructible up to isomorphism?

Since for this concrete example there are no isomorphic objects we could have omitted "up to isomorphism".

---

Question #5: What's an obvious way to generalize this kind of puzzles (from posets to what?)

Answer 1

For your question #5, this can be generalized to: given two categories $A$ and $B$, describe the functors $A\to B$. For a closer match, you can restrict to the functors which map irreducible maps (those that cannot be written as a composition of two non-identity maps) to irreducible maps.

You example corresponds to letting $A$ be the poset you drew considered as a category, and $B$ the category of graphs and embeddings. This provides a formal statement of your example.

You can generalize a bit differently by asking: given a category $A$, describe the pairs $(B,F)$ with $B$ a category and $F:A\to B$ a functor (preserving irreducibility of maps, if you want...). It would not be without interest to know of another such functor from your poset to a category which is not graphs---as that would, I think, give a category equivalent to (Finite graphs and embeddings).

From this point of view, we get the following answer to your question #3: this is just representation theory.

It is clear that your puzzle can be solved algorithmically (in so far as infinite puzzles can be...): starting from the root, and proceeding level by level (where levels are defined by counting vertices) just try assigning graphs to vertices, and backtracking when you hit an inconsistency. Provided you know the puzzle is solvable (and in this case you do know!)

As Harrison notes, your question #4 is equivalent to Harary's Set Reconstruction Conjecture: the levels up to 4 vertices you work out by hand, and then use the conjecture to check that a node in a level is determined by those in the level right below it from which there is an arrow coming in.

Answer 2

Question #4: Can it be shown - at least for this concrete example - that every object is reconstructible up to isomorphism?

I don't have time to work through the details at the moment, but it should be the case that assuming the graph reconstruction conjecture, the answer is "yes." (The isolated vertices thing ought not to make a difference.) I would be mildly surprised if this question were not equivalent to graph reconstruction, actually, but I don't see an easy way to prove the other direction.