# Reconstruction puzzles

[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):

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

The "reconstruction puzzle" is to reconstruct the inner structure of the objects unambigously 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?)

-
Why is this 'mathematics-education'? –  Mariano Suárez-Alvarez Jan 21 '10 at 17:46
I don't follow. Why do you have any reason to suspect that this can be done uniquely? –  Qiaochu Yuan Jan 21 '10 at 17:58
As I have pointed out: it can be done uniquely at least up to 4 edges (as can be seen) and Harrison points out, that in this special case it can be done in general if the graph reconstruction conjecture is true. –  Hans Stricker Jan 21 '10 at 18:04
You said "forget the inner structure of the objects." Are we fixing a category in which these objects are to reside? Are you fixing this to be the category of graphs? I can't tell what choices you do and do not want to make. –  Qiaochu Yuan Jan 21 '10 at 18:13
Isn't there an edge missing between 3 (||) and 7 (|\|) :) –  t3suji Jan 21 '10 at 18:49

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.

-
Wikipedia says, "representation theory is a branch of mathematics that studies abstract algebraic structures by representing their elements as linear transformations of vector spaces". Is this an obsolete definition? Where is representation theory introduced in a more general way? –  Hans Stricker Jan 21 '10 at 22:30

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.

-
I would be enlightening to see, what these two concepts of reconstructability have to do with each other. –  Hans Stricker Jan 21 '10 at 10:02
Ah, I believe I can see it! –  Hans Stricker Jan 21 '10 at 10:06