# 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): (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?)

• Why is this 'mathematics-education'? Jan 21, 2010 at 17:46
• I don't follow. Why do you have any reason to suspect that this can be done uniquely? Jan 21, 2010 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. Jan 21, 2010 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. Jan 21, 2010 at 18:13
• For the tag "math education" to be useful, it needs to be reserved for questions with a specifically pedagogical slant. (In some sense this whole site is concerned with "math education", but that's not taxonomically helpful!) I removed the tag and replaced it with order-theory. Jan 22, 2010 at 10:08

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? Jan 21, 2010 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. Jan 21, 2010 at 10:02
• Ah, I believe I can see it! Jan 21, 2010 at 10:06