Gordian Knot

[Martin Fuller]

Here are a couple of proposed sequences related to the
reconstruction conjecture and taken from the web. I'd
welcome some more references and comments, and a
cross-check! Also can anyone explain A006652-A006655
or give a link to the paper?

%I A000001
%S A000001 4, 8, 3, 34, 0, 0, 150, 4, 2, 0, 1044, 0,
0, 0, 0, 12334, 8, 2, 2, 0, 0, 274666, 0, 2, 0, 0, 0,
0, 12005156, 6, 4, 0, 2, 0, 0, 0
%N A000001 Triangle T(n,k) of the number of unlabeled
graphs on n nodes with existential reconstruction
number k, 3<=k<=n. ERN(G) is the minimum number of
vertex-deleted subgraphs of G required to uniquely
reconstruct G up to isomorphism.
%C A000001 The (vertex) Reconstruction Conjecture, due
to Kelly and Ulam, states that every graph with three
or more vertices is reconstructible up to isomorphism
given the multiset of vertex deleted subgraphs.
Equivalently, every graph has an ERN and so
sum(k=3,n,T(n,k))==A000088(n) for all n>=3.
%H A000001 B. McMullen, <a
href="http://hdl.handle.net/1850/2773">Graph
reconstruction numbers</a>.
%H A000001 P. J. Kelly, <a
href="http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674">A
congruence theorem for trees</a>, Pacific J. Math., 7
(1957), 961–968.
%H A000001 Wikipedia, <a
href="http://en.wikipedia.org/wiki/Reconstruction_conjecture">Reconstruction
conjecture</a>.
%e A000001 Triangle begins
4
8, 3
34, 0, 0
150, 4, 2, 0
1044, 0, 0, 0, 0
12334, 8, 2, 2, 0, 0
274666, 0, 2, 0, 0, 0, 0
12005156, 6, 4, 0, 2, 0, 0, 0
%Y A000001 A000002, A000088, A006652-A006655
%O A000001 3
%K A000001 ,hard,more,nice,nonn,tabl,
%A A000001 Martin Fuller
(martin_n_fuller at btinternet.com), Dec 08 2006

%I A000002
%S A000002 3, 2, 9, 7, 19, 8, 8, 56, 90, 2, 16, 496,
520, 12, 0, 266, 8308, 3584, 284, 4, 0, 45186, 199247,
28781, 1434, 20, 0, 0, 6054148, 5637886, 301530,
10686, 914, 4, 0, 0
%N A000002 Triangle T(n,k) of the number of unlabeled
graphs on n nodes with universal reconstruction number
k, 3<=k<=n. URN(G) is the minimum size for which all
multisubsets of vertex-deleted subgraphs of G can
uniquely reconstruct G up to isomorphism.
%C A000002 The (vertex) Reconstruction Conjecture, due
to Kelly and Ulam, states that every graph with three
or more vertices is reconstructible up to isomorphism
given the multiset of vertex deleted subgraphs.
Equivalently, every graph has an URN and so
sum(k=3,n,T(n,k))==A000088(n) for all n>=3.
%H A000002 B. McMullen, <a
href="http://hdl.handle.net/1850/2773">Graph
reconstruction numbers</a>.
%H A000002 P. J. Kelly, <a
href="http://projecteuclid.org/getRecord?id=euclid.pjm/1103043674">A
congruence theorem for trees</a>, Pacific J. Math., 7
(1957), 961–968.
%H A000002 Wikipedia, <a
href="http://en.wikipedia.org/wiki/Reconstruction_conjecture">Reconstruction
conjecture</a>.
%e A000002 Triangle begins
3
2, 9
7, 19, 8
8, 56, 90, 2
16, 496, 520, 12, 0
266, 8308, 3584, 284, 4, 0
45186, 199247, 28781, 1434, 20, 0, 0
6054148, 5637886, 301530, 10686, 914, 4, 0, 0
%Y A000002 A000001, A000088, A006652-A006655
%O A000002 3
%K A000002 ,hard,more,nice,nonn,tabl,
%A A000002 Martin Fuller
(martin_n_fuller at btinternet.com), Dec 08 2006

--- Jon Awbrey <jawbrey at att.net> wrote:

>
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> 
> yes, (though i think it's usually attributed to
> ulam), that
> was part of the attraction, since pt-deleted
> subgraphs are
> like taking derivatives, reconstruction is analogous
> to the
> integration problem, and the holographic metaphor
> was there,
> too, or radon-nikodym, and catscans, etc.  but it
> has to be
> group orbits of matrices, so as not to be labeled
> graphs.
> 
> i will look up some old notes and try to
> remember how the enumerative angle went.
> 
> ja
> 
> > I was working on Harary's Graph Reconstruction
> Hypothesis
> > while and undergraduate at caltech, and wrote an
> internal
> > grant proposal.  It has been solved for bigger and
> bigger
> > subsets of graphs, but is still unsolved in
> general.  What
> > seemed bizarre to me was the identical problem
> expressed in
> > terms of the adjacency matrices.  Given an nxn
> binary (0-1)
> > matrix, one is given the set of all (n-1)x(n-1)
> submatrices.
> > Can one reconstruct the original matrix?  If so,
> then (loosely
> > speaking) all information in the matrix is local. 
> If not, then
> > in some weird holographic way, there is some
> information in some
> > matrices which is entirely global.
> > 
> > -- Jonathan Vos Post
> 
>
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> inquiry e-lab: http://stderr.org/pipermail/inquiry/
> zhongwen wp:
> http://zh.wikipedia.org/wiki/User:Jon_Awbrey
> wikinfo:
> http://wikinfo.org/wiki.php?title=User:Jon_Awbrey
> meta:
>
http://www.getwiki.net/wiki.php?title=User:Jon_Awbrey
> wp review:
> http://wikipediareview.com/index.php?showuser=398
>
o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o
> 
>